4635
правок
K-Дерево: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''<math>k</math>-Дерево''' (''<math>k</math>-Tree'') - граф, который может быть сведен к полному...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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] | ||