K-Дерево

$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.