K-дерево

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

Граф Голднера — Харари, пример планарного 3-дерева.

Описания

k-Деревья — это в точности максимальные графы с заданной древесной шириной, то есть графы, к которым нельзя добавить ребро без увеличения древесной ширины графа[2]. Это также в точности хордальные графы, все максимальные клики которых имеют один и тот же размер и все минимальные кликовые сепараторы которых имеют также одинаковый размер k[1].

Связные классы графов

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

Графы, которые имеют древесную ширину, не превосходящую k, это в точности подграфы k-деревьев, и по этой причине они называются частичными k-деревьями[2].

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

Примечания

  1. Patil, 1986, с. 57–64.
  2. Nešetřil, Ossona de Mendez, 2008, с. 390.
  3. Hwang, Richards, Winter, 1992.
  4. Distances in random Apollonian network structures Архивная копия от 21 июля 2011 на Wayback Machine, talk slides by Olivier Bodini, Alexis Darrasse, Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06
  5. Koch, Perles, 1976, с. 420.
  6. Below, De Loera, Richter-Gebert.
  7. Kleinschmidt, 1976, с. 663–667.

Литература

  • Patil H. P. On the structure of k-trees // Journal of Combinatorics, Information and System Sciences. — 1986. Т. 11, вып. 2-4. С. 57–64.
  • Frank Hwang, Dana Richards, Pawel Winter. The Steiner Tree Problem. — Elsevier, 1992. — Т. 53. — С. 177. — (Annals of Discrete Mathematics (North-Holland Mathematics Studies)). — ISBN 978-0-444-89098-6.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Structural Properties of Sparse Graphs // Building Bridges: between Mathematics and Computer Science / Martin Grötschel, Gyula O. H. Katona. — Springer-Verlag, 2008. — Т. 19. — С. 390. — (Bolyai Society Mathematical Studies). — ISBN 978-3-540-85218-6.
  • Etan Koch, Micha A. Perles. 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., 1976. — С. 391–420. Congressus Numerantium, No. XVII.
  • Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. The Complexity of Finding Small Triangulations of Convex 3-Polytopes.
  • Peter Kleinschmidt. Eine graphentheoretische Kennzeichnung der Stapelpolytope // Archiv der Mathematik. — 1976. — Декабрь (т. 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.