K-Дерево: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''<math>k</math>-Дерево''' (''<math>k</math>-Tree'') - граф, который может быть сведен к полному...) |
(нет различий)
|
Версия от 14:09, 13 октября 2009
[math]\displaystyle{ k }[/math]-Дерево ([math]\displaystyle{ k }[/math]-Tree) - граф, который может быть сведен к полному графу на [math]\displaystyle{ k }[/math] вершинах последовательным удалением вершин степени [math]\displaystyle{ k }[/math], окрестности которых образуют клики.
[math]\displaystyle{ k }[/math]-деревья можно также определить следующим образом:
а) клика с [math]\displaystyle{ k+1 }[/math] вершиной есть [math]\displaystyle{ k }[/math]-дерево;
б) [math]\displaystyle{ k }[/math]-дерево с [math]\displaystyle{ n+1 }[/math] вершиной получается из [math]\displaystyle{ k }[/math]-дерева с [math]\displaystyle{ n }[/math] вершинами добавлением новой вершины, смежной со всеми вершинами какой-либо [math]\displaystyle{ k }[/math]-клики.
Литература
[WG'94]