K-Дерево: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''<math>k</math>-Дерево''' (''<math>k</math>-Tree'') - граф, который может быть сведен к полному...)
 
Нет описания правки
Строка 1: Строка 1:
'''<math>k</math>-Дерево''' (''<math>k</math>-Tree'') -  
'''<math>k</math>-Дерево''' (''[[k-Tree|<math>k</math>-Tree]]'') - [[граф]], который может быть сведен к [[полный граф|полному графу]] на <math>k</math> [[вершина|вершинах]] последовательным удалением вершин [[степень вершины|степени]] <math>k</math>, окрестности которых образуют [[клик|клики]].
граф, который может быть сведен к полному
графу на <math>k</math> вершинах последовательным удалением вершин степени <math>k</math>,
окрестности которых образуют клики.


<math>k</math>-деревья  можно также определить следующим образом:
<math>k</math>-деревья  можно также определить следующим образом:


а) клика с <math>k+1</math> вершиной есть <math>k</math>-дерево;
а) клика с <math>k+1</math> вершиной есть <math>k</math>-[[дерево]];


б) <math>k</math>-дерево с <math>n+1</math> вершиной получается из <math>k</math>-дерева с <math>n</math>
б) <math>k</math>-дерево с <math>n+1</math> вершиной получается из <math>k</math>-дерева с <math>n</math>
вершинами добавлением новой вершины, смежной со всеми вершинами
вершинами добавлением новой вершины, [[смежные вершины|смежной]] со всеми вершинами
какой-либо <math>k</math>-клики.
какой-либо <math>k</math>-клики.
==Литература==
==Литература==
[WG'94]
[WG'94]

Навигация