Меню
Главная
Случайная статья
Настройки
|
k-Дерево — это неориентированный граф, образованный из полного графа с (k + 1) вершинами с последовательным добавлением вершин так, что каждая добавленная вершина v имеет в точности k соседей U, таких, что k + 1 вершин (вершина v + вершины U) образуют клику[1][2].
Содержание
Описания
k-Деревья — это в точности максимальные графы с заданной древесной шириной, то есть графы, к которым нельзя добавить ребро без увеличения древесной ширины графа[2].
Это также в точности хордальные графы, все максимальные клики которых имеют один и тот же размер и все минимальные кликовые сепараторы которых имеют также одинаковый размер k[1].
Связные классы графов
1-Деревья — это то же самое, что и некорневые деревья. 2-деревья являются максимальными параллельно-последовательными графами[3], и они включают также максимальные внешнепланарные графы. Планарные 3-деревья известны также как сети Аполлония[4].
Графы, которые имеют древесную ширину, не превосходящую k, это в точности подграфы k-деревьев, и по этой причине они называются частичными k-деревьями[2].
Графы, образованные рёбрами и вершинами k-мерных блоковых многогранников, то есть многогранников, образованных, начиная с симплекса, последовательным склеиванием граней симплексов, являются k-деревьями, если [5]. Этот процесс склеивания имитирует построение k-деревьев путём добавления вершин в клику[6]. k-Дерево является графом блокового многогранника тогда и только тогда, когда никакие три клики с (k + 1) вершинами не имеют k общих вершин [7].
Примечания
- 1 2 Patil, 1986, с. 57–64.
- 1 2 3 Neetil, Ossona de Mendez, 2008, с. 390.
- Hwang, Richards, Winter, 1992.
- Distances in random Apollonian network structures Архивная копия от 21 июля 2011 на Wayback Machine, talk slides by Olivier Bodini, Alexis Darrasse, Michle Soria from a talk at FPSAC 2008, accessed 2011-03-06
- Koch, Perles, 1976, с. 420.
- Below, De Loera, Richter-Gebert.
- 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.
- Alexander Below, Jess A. De Loera, Jrgen 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.
|
|