У теорії графів k-дерево — це неорієнтований граф, який утворюється з (k + 1)-вершинного повного графа, до якого послідовно додаються вершини таким чином, що кожна додана вершина v має точно k сусідів U таких, що разом k + 1 вершин, утворених з v і U, утворюють кліку..
Характеристики K-дерева — це в точності максимальні графи зі заданою деревною шириною, графи, до яких не можна додати більше ребер без збільшення ширини їхніх дерев. Вони також є хордальними графами, всі максимальні кліки яких мають однаковий розмір k + 1 і всі мінімальні клікові сепаратори також мають однаковий розмір k.
Будь-яке k-дерево однозначно розфарбовується в (k + 1) колір. Однозначно розфарбовуються в 4 кольори планарні графи — це точно графи Аполлонія, тобто планарні 3-дерева.
Зв'язні класи графів 1-дерева — це то саме, що і некореневі дерева. 2-дерева — це максимальні послідовно-паралельні графи, . і вони включають також максимальні зовніпланарні графи. Планарні 3-дерева є також відомі як графи Аполлонія.Distances in random Apollonian network structures , talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06.
Графи, що мають ширину дерева не більшу, ніж k, є в точності підграфами k-дерева, і з цієї причини їх називають частковими k-деревами.
Графи, утворені ребрами і вершинами k-вимірних блокових многогранників, які у свою чергу утворені починаючи з симплекса, потім послідовно симплекси приклеєні на грані многогранника, є k-деревами, якщо k ≥ 3.. Див. стор. 420. Цей процес склеювання імітує побудову k-дерев, додаючи вершини до кліки.Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. The Complexity of Finding Small Triangulations of Convex 3-Polytopes. k-дерево є графом блокового многогранника тоді і тільки тоді, коли ніякі три кліки з (k + 1)-вершинами не мають k спільних вершин.
Посилання