Просмотр кода страницы K-дерево

[[Файл:Goldner-Harary graph.svg|thumb|[[Граф Голднера — Харари]], пример планарного 3-дерева.]]
'''''k''-Дерево''' — это [[неориентированный граф]], образованный из [[Полный граф|полного графа]] с (''k''&nbsp;+&nbsp;1) вершинами с последовательным добавлением вершин так, что каждая добавленная вершина ''v'' имеет в точности ''k'' соседей ''U'', таких, что ''k''&nbsp;+&nbsp;1 вершин (вершина ''v'' + вершины ''U'') образуют [[Клика (теория графов)|клику]]{{sfn|Patil|1986|с=57–64}}{{sfn|Nešetřil, Ossona de Mendez|2008|с=390}}.

==Описания==
''k''-Деревья — это в точности [[Максимальные и минимальные элементы|максимальные]] графы с заданной [[Древесная ширина (теория графов)|древесной шириной]], то есть графы, к которым нельзя добавить ребро без увеличения древесной ширины графа{{sfn|Nešetřil, Ossona de Mendez|2008|с=390}}.
Это также в точности [[Хордальный граф|хордальные графы]], все [[Клика (теория графов)#Определения|максимальные клики]] которых имеют один и тот же размер <math>k + 1</math> и все [[Хордальный граф#Минимальные сепараторы|минимальные кликовые сепараторы]] которых имеют также одинаковый размер ''k''{{sfn|Patil|1986|с=57–64}}.

==Связные классы графов ==
1-Деревья — это то же самое, что и некорневые [[Дерево (теория графов)|деревья]]. 2-деревья являются максимальными [[Параллельно-последовательный граф|параллельно-последовательными графами]]{{sfn|Hwang, Richards, Winter|1992}}, и они включают также максимальные [[Внешнепланарный граф|внешнепланарные графы]]. [[Планарный граф|Планарные]] 3-деревья известны также как [[Сетка Аполлония|сети Аполлония]]{{r|BDS}}.

Графы, которые имеют древесную ширину, не превосходящую ''k'', это в точности [[подграф]]ы ''k''-деревьев, и по этой причине они называются [[Частичное k-дерево|частичными ''k''-деревьями]]{{sfn|Nešetřil, Ossona de Mendez|2008|с=390}}.

Графы, образованные рёбрами и вершинами ''k''-мерных [[Блоковый многогранник|блоковых многогранников]], то есть [[многогранник]]ов, образованных, начиная с [[симплекс]]а, последовательным склеиванием граней симплексов, являются ''k''-деревьями, если <math>k \geqslant 3</math>{{sfn|Koch, Perles|1976|с=420}}. Этот процесс склеивания имитирует построение  ''k''-деревьев путём добавления вершин в клику{{sfn|Below, De Loera, Richter-Gebert}}. ''k''-Дерево является графом блокового многогранника тогда и только тогда, когда никакие три клики с (''k''&nbsp;+&nbsp;1) вершинами не имеют ''k'' общих вершин {{sfn|Kleinschmidt|1976|с=663–667}}.

==Примечания==
{{примечания|2|refs=
<ref name="BDS">[http://www.cirm.univ-mrs.fr/videos/2008/exposes/325/Darrasse.pdf Distances in random Apollonian network structures] {{Wayback|url=http://www.cirm.univ-mrs.fr/videos/2008/exposes/325/Darrasse.pdf |date=20110721023259 }}, talk slides by Olivier Bodini, Alexis Darrasse, Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06</ref>
}}
==Литература==
{{refbegin|colwidth=30em}}
*{{статья
|ref=Patil
|автор=Patil H. P.
|mr=966069
|выпуск=2-4
|издание=Journal of Combinatorics, Information and System Sciences
|страницы=57–64
|заглавие=On the structure of ''k''-trees
|том=11
|год=1986
}}
*{{книга
|страницы=177
|заглавие=The Steiner Tree Problem
|том=53
|серия=Annals of Discrete Mathematics (North-Holland Mathematics Studies)
|автор=Frank Hwang, Dana Richards, Pawel Winter
|ref=Hwang, Richards, Winter
|издательство=Elsevier
|год=1992
|isbn=978-0-444-89098-6
}}
*{{книга
|страницы=390
|часть=Structural Properties of Sparse Graphs
|автор=Jaroslav Nešetřil, Patrice Ossona de Mendez
|ref=Nešetřil, Ossona de Mendez
|заглавие=Building Bridges: between Mathematics and Computer Science
|том=19
|серия=Bolyai Society Mathematical Studies
|ответственный=Martin Grötschel, Gyula O. H. Katona
|издательство=Springer-Verlag
|год=2008
|isbn=978-3-540-85218-6
|contribution-url=http://kam.mff.cuni.cz/~kamserie/serie/clanky/2008/s863.pdf
}}
*{{книга
|автор=Etan Koch, Micha A. Perles 
|ref=Koch, Perles 
|часть=Covering efficiency of trees and ''k''-trees
|mr=0457265
|страницы=391–420. Congressus Numerantium, No. XVII
|издательство=Utilitas Math., Winnipeg, Man.
|заглавие=Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976)
|год=1976
}}
*{{статья
|заглавие=The Complexity of Finding Small Triangulations of Convex 3-Polytopes
|автор=Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert
|ref=Below, De Loera, Richter-Gebert
|eprint=math/0012177
 }}
*{{статья
|автор=Peter Kleinschmidt
|ref=Kleinschmidt
|заглавие=Eine graphentheoretische Kennzeichnung der Stapelpolytope
|издание=Archiv der Mathematik
|месяц=December
|год=1976
|том=27
|выпуск=1
|страницы=663–667
|doi=10.1007/BF01224736
}}
{{refend}}

[[Категория:Теория миноров графов]]
[[Категория:Деревья (графы)]]
[[Категория:Совершенные графы]]
{{rq|checktranslate|style}}