Лучшие вопросы
Таймлайн
Чат
Перспективы

Птолемеев граф

неориентированный граф, в котором расстояния по кратчайшему пути удовлетворяют неравенству Птолемея Из Википедии, свободной энциклопедии

Птолемеев граф
Remove ads

Птолеме́ев граф — это неориентированный граф, в котором расстояния по кратчайшему пути удовлетворяют неравенству Птолемея. Птолемеевы графы — это в точности графы, которые одновременно являются и хордальными, и дистанционно наследуемыми. Эти графы включают блоковые графы[1] и являются подклассом совершенных графов.

Thumb
Птолемеев граф
Thumb
Граф-изумруд (или 3-веер) не птолемеев.
Thumb
Блоковый граф, специальный вид птолемеевых графов
Thumb
Три операции, с помощью которых может быть построен любой дистанционно-наследуемый граф. Для птолемеевых графов соседи двойняшек должны образовывать клику, чтобы предотвратить построение 4-цикла, показанного здесь.
Remove ads

Описание

Суммиров вкратце
Перспектива

Граф является птолемеевым тогда и только тогда, когда он удовлетворяет следующим эквивалентным условиям:

  • Расстояния по кратчайшему пути удовлетворяют неравенству Птолемея — для любых четырёх вершин u, v, w и x выполняется неравенство d(u,v)d(w,x) + d(u,x)d(v,w) ≥ d(u,w)d(v,x)[1]. Например, граф-изумруд (3-веер) на рисунке не является птолемеевым, поскольку в этом графе d(u,w)d(v,x) = 4 больше, чем d(u,v)d(w,x) + d(u,x)d(v,w) = 3.
  • Для любых перекрывающихся максимальных клик их пересечение является сепаратором, который разделяет разность этих двух клик[2]. Для графа-изумруда на иллюстрации это не так — клики uvy и wxy не разделяются их пересечением y, поскольку существует ребро vw, соединяющее клики.
  • Любой цикл с k вершинами имеет по меньшей мере 3(k 3)/2 диагоналей[2].
  • Граф является и хордальным (любой цикл с длиной, превосходящей три, имеет диагональ), и дистанционно-наследуемым (любой связный порождённый подграф имеет те же расстояния, что и весь граф)[2]. Граф-изумруд является хордальным, но не дистанционно-наследуемым — в подграфе, порождённом uvwx, расстояние от u до x равно 3, что больше, чем расстояние между теми же вершинами в полном графе. Поскольку как хордальные, так и дистанционно-наследуемые графы являются совершенными, таковыми же являются и птолемеевы графы [3].
  • Граф хордален и не содержит изумрудов — графов, образованных добавлением двух непересекающихся диагоналей в пятиугольник [3].
  • Граф является дистанционно-наследуемым и не содержит порождённых 4-циклов[4].
  • Граф может быть построен из единственной вершины последовательностью операций, при которых добавляется новая вершина степени 1 (висячая) или дублируется существующая вершина (образуя близняшки или двойняшки), с условием, что операция удвоения, в которой дубликат вершины не смежен своей паре (двойняшки), только если соседи этих удвоенных вершин образуют клику. Эти три операции, если не применять указанное условие, образуют все дистанционно-наследуемые графы. Для образования птолемеевых графов недостаточно использовать образование висячих вершин и близняшек, образование двойняшек (при соблюдении указанных выше условий) тоже иногда требуется[5].
  • Диаграмма Хассе подмножества отношений непустого пересечения максимальных клик образует ориентированное дерево[англ.][6].
  • Выпуклые подмножества вершин (подмножества, содержащие все кратчайшие пути между двумя вершинами в подмножестве) образуют выпуклую геометрию[англ.]. То есть любое выпуклое множество может быть получено из полного набора вершин последовательным удалением крайних вершин, то есть не принадлежащих какому-либо кратчайшему пути между оставшимися вершинами[7]. В изумруде выпуклое множество uxy не может быть получено таким способом, поскольку ни v, ни w не являются крайними.
Remove ads

Вычислительная сложность

Основываясь на описании ориентированными деревьями, птолемеевы графы можно распознать за линейное время[6].

Примечания

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads