K-дерево
У теорії графів k-дерево — це неорієнтований граф, який утворюється з (k + 1)-вершинного повного графа, до якого послідовно додаються вершини таким чином, що кожна додана вершина v має точно k сусідів U таких, що разом k + 1 вершин, утворених з v і U, утворюють кліку[1][2].
Характеристики[ред. | ред. код]
K-дерева — це в точності максимальні графи зі заданою деревною шириною, графи, до яких не можна додати більше ребер без збільшення ширини їхніх дерев.[2] Вони також є хордальними графами, всі максимальні кліки яких мають однаковий розмір k + 1 і всі мінімальні клікові сепаратори також мають однаковий розмір k.[1]
Будь-яке k-дерево однозначно розфарбовується в (k + 1) колір. Однозначно розфарбовуються в 4 кольори планарні графи — це точно графи Аполлонія, тобто планарні 3-дерева[3].
Зв'язні класи графів[ред. | ред. код]
1-дерева — це то саме, що і некореневі дерева. 2-дерева — це максимальні послідовно-паралельні графи, [4] і вони включають також максимальні зовніпланарні графи. Планарні 3-дерева є також відомі як графи Аполлонія.[5]
Графи, що мають ширину дерева не більшу, ніж k, є в точності підграфами k-дерева, і з цієї причини їх називають частковими k-деревами.[2]
Графи, утворені ребрами і вершинами k-вимірних блокових многогранників, які у свою чергу утворені починаючи з симплекса, потім послідовно симплекси приклеєні на грані многогранника, є k-деревами, якщо k ≥ 3.[6] Цей процес склеювання імітує побудову k-дерев, додаючи вершини до кліки.[7] k-дерево є графом блокового многогранника тоді і тільки тоді, коли ніякі три кліки з (k + 1)-вершинами не мають k спільних вершин.[8]
Посилання[ред. | ред. код]
- ↑ а б Patil, H. P. (1986), On the structure of k-trees, Journal of Combinatorics, Information and System Sciences, 11 (2-4): 57—64, MR 0966069
- ↑ а б в Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), Structural Properties of Sparse Graphs (PDF), у Grötschel (ред.), Building Bridges: between Mathematics and Computer Science, Bolyai Society Mathematical Studies, т. 19, Springer-Verlag, с. 390, ISBN 978-3-540-85218-6, архів оригіналу (PDF) за 22 липня 2018, процитовано 23 червня 2019.
- ↑ Thomas Fowler. Unique Coloring of Planar Graphs. — Georgia Institute of Technology Mathematics Department, 1998. — (Ph.D. thesis)
- ↑ Hwang, Frank; Richards, Dana; Winter, Pawel (1992), The Steiner Tree Problem, Annals of Discrete Mathematics (North-Holland Mathematics Studies), т. 53, Elsevier, с. 177, ISBN 978-0-444-89098-6.
- ↑ Distances in random Apollonian network structures [Архівовано 21 липня 2011 у Wayback Machine.], talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06.
- ↑ Koch, Etan; Perles, Micha A. (1976), Covering efficiency of trees and k-trees, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., с. 391–420. Congressus Numerantium, No. XVII, MR 0457265. Див. стор. 420.
- ↑ Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. The Complexity of Finding Small Triangulations of Convex 3-Polytopes.
- ↑ Kleinschmidt, Peter (1 грудня 1976). Eine graphentheoretische Kennzeichnung der Stapelpolytope. Archiv der Mathematik. 27 (1): 663—667. doi:10.1007/BF01224736.