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