К-дерево

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

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

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

K -деревья - это в точности максимальные графы с шириной дерева 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. Патил, HP (1986), «О структуре k -деревьев», Журнал комбинаторики, информации и системных наук , 11 (2–4): 57–64, MR  0966069.
2. Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2008), «Структурные свойства разреженных графов» (PDF) , в Гретшеле, Мартине ; Катона, Дьюла О.Г. (ред.), «Наведение мостов: между математикой и информатикой» , Математические исследования Общества Боляи, том. 19, Шпрингер-Верлаг, с. 390, ISBN 978-3-540-85218-6.
3. Хван, Фрэнк; Ричардс , Дана; Винтер, Павел (1992), Проблема дерева Штейнера , Анналы дискретной математики (математические исследования Северной Голландии), том. 53, Эльзевир, с. 177, ISBN 978-0-444-89098-6.
4. Расстояния в случайных структурах аполлонической сети. Архивировано 21 июля 2011 г. в Wayback Machine , слайды доклада Оливье Бодини, Алексиса Даррасса и Мишель Сориа из выступления на FPSAC 2008, доступ осуществлен 06 марта 2011 г.
5. Кох, Итан; Перлз, Миша А. (1976), «Эффективность покрытия деревьев и k -деревьев», Труды Седьмой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, Луизиана, 1976) , Utilitas Math., Виннипег, Ман., стр. 391–420. Конгресс Нумерантиум, № XVII, MR  0457265. См., в частности, стр. 420.
6. Ниже, Александр; Де Лоэра, Хесус А .; Рихтер-Геберт, Юрген (февраль 2004 г.), «Сложность поиска малых триангуляций выпуклых 3-многогранников», Journal of Algorithms , 50 (2): 134–167, arXiv : math/0012177 , doi : 10.1016/s0196-6774 (03)00092-0
7. Кляйншмидт, Питер (1 декабря 1976 г.), «Eine Graphentheoretische Kennzeichnung der Stapelpolytope», Archiv der Mathematik , 27 (1): 663–667, doi : 10.1007/BF01224736