В теории графов , A к -tree является неориентированный граф , образованный , начиная с ( к + 1) -vertex полного графа , а затем многократно добавления вершин таким образом , что каждый добавленный вершина v имеет ровно K соседей U таким образом , что вместе, в K + 1 вершин , образованных V и U образуют верхушку . [1] [2]
Характеристики [ править ]
В K -дерева в точности максимальные графы с заданной древесной шириной , графики , к которой нет больше ребер не могут быть добавлены без увеличения их древесной ширины. [2] Это также в точности хордовые графы, все максимальные клики которых имеют одинаковый размер k + 1 и все минимальные клики-разделители также имеют одинаковый размер k . [1]
Связанные классы графов [ править ]
1-деревья такие же, как деревья без корней . 2-деревья являются максимальными последовательно-параллельными графами , [3] и включают также максимальные внешнепланарные графы . Плоские 3-деревья также известны как аполлонические сети . [4]
Графики , которые имеют древесную ширину в большинстве к в точности подграфы из K -дерев, и по этой причине они называются частичными K -деревами . [2]
Графики , образованные ребра и вершинами к - мерные штабели многогранников , многогранники , образованные начиная с симплексным , а затем многократно приклеиванием симплексов на грани многогранника, являются к -деревам при K ≥ 3. [5] Этот процесс склеивания имитирует построение k -деревьев путем добавления вершин в клику. [6] к -tree не является графиком сложенного многогранника тогда и только тогда , когда никаких три ( к + 1) -vertex клик Have к общим вершинам. [7]
Ссылки [ править ]
- ^ a b Патил, HP (1986), «О структуре k -деревьев», Журнал комбинаторики, информации и системных наук , 11 (2–4): 57–64, MR 0966069.
- ^ a b c Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2008), «Структурные свойства разреженных графов» (PDF) , в Grötschel, Martin ; Катона, Дьюла Огайо (ред.), Наведение мостов: между математикой и информатикой , Математические исследования Общества Бойяи, 19 , Springer-Verlag, стр. 390, ISBN 978-3-540-85218-6.
- ^ Хван, Франк; Ричардс, Дана; Винтер, Павел (1992), Проблема дерева Штейнера , Annals of Discrete Mathematics (North-Holland Mathematics Studies), 53 , Elsevier, p. 177, ISBN 978-0-444-89098-6.
- ^ Расстояния в случайных сетевых структурах Аполлонии. Архивировано 21 июля 2011 г.на Wayback Machine , слайды выступлений Оливье Бодини, Алексис Даррасс и Мишель Сориа из выступления на FPSAC 2008, доступ осуществлен 06 марта 2011 г.
- ^ Кох, Этан; Перлес, Мика А. (1976), «Эффективность покрытия деревьев и k -деревьев», Труды Седьмой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, штат Луизиана, 1976 г.) , Utilitas Math., Winnipeg, Man., Стр. 391–420. Congressus Numerantium, № XVII, MR 0457265 . См., В частности, стр. 420.
- ↑ Ниже, Александр; Де Лоэра, Хесус А .; Рихтер-Геберт, Юрген. «Сложность поиска малых триангуляций выпуклых 3-многогранников». arXiv : math / 0012177 ..
- Перейти ↑ Kleinschmidt, Peter (1 декабря 1976). "Eine graphentheoretische Kennzeichnung der Stapelpolytope". Archiv der Mathematik . 27 (1): 663–667. DOI : 10.1007 / BF01224736 .
