K-дерево

У теорії графів k-дерево — це неорієнтований граф, який утворюється з (k + 1)-вершинного повного графу, до якого послідовно додаються вершини таким чином, що кожна додана вершина v має точно k сусідів U таких, що разом k + 1 вершин, утворених з v і U, утворюють кліку[1][2].

Граф Голднера – Харарі є прикладом планарного 3-дерева.

Характеристики

K-дерева — це в точності максимальні графи зі заданою деревною шириною, графи, до яких не можна додати більше ребер без збільшення ширини їхніх дерев.[2] Вони також є хордальними графами, всі максимальні кліки яких мають однаковий розмір k + 1 і всі мінімальні клікові сепаратори також мають однаковий розмір k.[1]

Зв'язні класи графів

1-дерева — це то саме, що і некореневі дерева. 2-дерева — це максимальні послідовно-паралельні графи, [3] і вони включають також максимальні зовніпланарні графи. Планарні 3-дерева є також відомі як графи Аполлонія.[4]

Графи, що мають ширину дерева не більшу, ніж k, є в точності підграфами k-дерева, і з цієї причини їх називають частковими k-деревами.[2]

Графи, утворені ребрами і вершинами k-вимірних блокових багатогранників, які у свою чергу утворені починаючи з симплекса, потім послідовно симплекси приклеєні на грані багатогранника, є k-деревами, якщо k ≥ 3.[5] Цей процес склеювання імітує побудову k-дерев, додаючи вершини до кліки.[6] k-дерево є графом блокового багатогранника тоді і тільки тоді, коли ніякі три кліки з (k + 1)-вершинами не мають k спільних вершин.[7]

Посилання
  1. Patil, H. P. (1986). On the structure of k-trees. Journal of Combinatorics, Information and System Sciences 11 (2-4): 57–64. MR 966069.
  2. Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008). Structural Properties of Sparse Graphs. У Grötschel. Building Bridges: between Mathematics and Computer Science. Bolyai Society Mathematical Studies 19. Springer-Verlag. с. 390. ISBN 978-3-540-85218-6..
  3. 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..
  4. 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.
  5. 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.. See in particular p. 420.
  6. Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. The Complexity of Finding Small Triangulations of Convex 3-Polytopes.
  7. Kleinschmidt, Peter (1 грудня 1976). Eine graphentheoretische Kennzeichnung der Stapelpolytope. Archiv der Mathematik 27 (1): 663–667. doi:10.1007/BF01224736.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.