Меню
Главная
Случайная статья
Настройки
|
Птолемеев граф — это неориентированный граф, в котором расстояния по кратчайшему пути удовлетворяют неравенству Птолемея.
Птолемеевы графы — это в точности графы, которые одновременно являются и хордальными, и дистанционно наследуемыми.
Эти графы включают блоковые графы[1] и являются подклассом совершенных графов.
Содержание
Описание
Граф является птолемеевым тогда и только тогда, когда он удовлетворяет следующим эквивалентным условиям:
- Расстояния по кратчайшему пути удовлетворяют неравенству Птолемея — для любых четырёх вершин u,
- Для любых перекрывающихся максимальных клик их пересечение является сепаратором, который разделяет разность этих двух клик[2]. Для графа-изумруда на иллюстрации это не так — клики
- Любой цикл с
- Граф является и хордальным (любой цикл с длиной, превосходящей три, имеет диагональ), и дистанционно-наследуемым (любой связный порождённый подграф имеет те же расстояния, что и весь граф)[2]. Граф-изумруд является хордальным, но не дистанционно-наследуемым — в подграфе, порождённом
- Граф хордален и не содержит изумрудов — графов, образованных добавлением двух непересекающихся диагоналей в пятиугольник [3].
- Граф является дистанционно-наследуемым и не содержит порождённых 4-циклов[4].
- Граф может быть построен из единственной вершины последовательностью операций, при которых добавляется новая вершина степени 1 (висячая) или дублируется существующая вершина (образуя близняшки или двойняшки), с условием, что операция удвоения, в которой дубликат вершины не смежен своей паре (двойняшки), только если соседи этих удвоенных вершин образуют клику. Эти три операции, если не применять указанное условие, образуют все дистанционно-наследуемые графы. Для образования птолемеевых графов недостаточно использовать образование висячих вершин и близняшек, образование двойняшек (при соблюдении указанных выше условий) тоже иногда требуется[5].
- Диаграмма Хассе подмножества отношений непустого пересечения максимальных клик образует ориентированное дерево[англ.][6].
- Выпуклые подмножества вершин (подмножества, содержащие все кратчайшие пути между двумя вершинами в подмножестве) образуют выпуклую геометрию[англ.]. То есть любое выпуклое множество может быть получено из полного набора вершин последовательным удалением крайних вершин, то есть не принадлежащих какому-либо кратчайшему пути между оставшимися вершинами[7]. В изумруде выпуклое множество uxy не может быть получено таким способом, поскольку ни v, ни w не являются крайними.
Вычислительная сложность
Основываясь на описании ориентированными деревьями, птолемеевы графы можно распознать за линейное время[6].
Примечания
- 1 2 Kay, Chartrand, 1965, p. 342–346.
- 1 2 3 Howorka, 1981, p. 323–331.
- 1 2 Graphclass: ptolemaic, Information System on Graph Classes and their Inclusions, Архивировано из оригинала 30 марта 2016, Дата обращения: 5 июня 2016.
- McKee, 2010, p. 651–661.
- Bandelt, Mulder, 1986, p. 182–208.
- 1 2 Uehara, Uno, 2009, p. 1533–1543.
- Farber, Jamison, 1986, p. 433–444.
Литература
|
|