K-Дерево

Материал из WikiGrapp
Перейти к:навигация, поиск

k-Дерево (k-Tree) — граф, который может быть сведен к полному графу на k вершинах последовательным удалением вершин степени k, окрестности которых образуют клики.

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

а) клика с k+1 вершиной есть k-дерево;

б) k-дерево с n+1 вершиной получается из k-дерева с n вершинами добавлением новой вершины, смежной со всеми вершинами какой-либо k-клики.

Литература

  • Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903.