K-дерево - K-tree

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

В теория графов, а k-дерево является неориентированный граф образованный, начиная с (k + 1) -вертекс полный график а затем несколько раз добавляя вершины таким образом, чтобы каждая добавленная вершина v точно k соседи U так что вместе k +1 вершина, образованная v и U сформировать клика.[1][2]

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

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