K-Дерево: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Дерево''' (''[[k-Tree|<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>-деревья можно также определить следующим образом: | ||
| Строка 9: | Строка 9: | ||
какой-либо <math>k</math>-клики. | какой-либо <math>k</math>-клики. | ||
==Литература== | ==Литература== | ||
* Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903. | |||
Текущая версия от 13:03, 4 февраля 2011
[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]-клики.
Литература
- Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903.