Войти  |  Регистрация
Авторизация

K-дерево



k-Дерево — это неориентированный граф, образованный из полного графа с (k + 1) вершинами с последовательным добавлением вершин так, что каждая добавленная вершина v имеет в точности k соседей U, таких, что k + 1 вершин (вершина v + вершины U) образуют клику.

Описания

k-Деревья — это в точности максимальные графы с заданной древесной шириной, то есть графы, к которым нельзя добавить ребро без увеличения древесной ширины графа. Это также в точности хордальные графы, все максимальные клики которых имеют один и тот же размер k + 1 {displaystyle k+1} и все минимальные кликовые сепараторы которых имеют также одинаковый размер k.

Связные классы графов

1-Деревья — это то же самое, что и некорневые деревья. 2-деревья являются максимальными параллельно-последовательными графами, и они включают также максимальные внешнепланарные графы. Планарные 3-деревья известны также как сети Аполлония.

Графы, которые имеют древесную ширину, не превосходящую k, это в точности подграфы k-деревьев, и по этой причине они называются частичными k-деревьями.

Графы, образованные рёбрами и вершинами k-мерных блоковых многогранников, то есть многогранников, образованных, начиная с симплекса, последовательным склеиванием граней симплексов, являются k-деревьями, если k ⩾ 3 {displaystyle kgeqslant 3} . Этот процесс склеивания имитирует построение k-деревьев путём добавления вершин в клику. k-Дерево является графом блокового многогранника тогда и только тогда, когда никакие три клики с (k + 1) вершинами не имеют k общих вершин .


Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent