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

Описание

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

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

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

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

Примечания

Литература

• Hans-Jürgen Bandelt, Henry Martyn Mulder. Distance-hereditary graphs // Journal of Combinatorial Theory . — 1986. — Vol. 41, no. 2. — P. 182–208. — doi : .
• Martin Farber, Robert E. Jamison. Convexity in graphs and hypergraphs // . — 1986. — Vol. 7, no. 3. — P. 433–444. — doi : .
• Edward Howorka. A characterization of Ptolemaic graphs // . — 1981. — Vol. 5, no. 3. — P. 323–331. — doi : .
• David C. Kay, Gary Chartrand. // . — 1965. — Vol. 17. — P. 342–346. — doi : .
• Terry A. McKee. Clique graph representations of Ptolemaic graphs // Discussiones Mathematicae Graph Theory. — 2010. — Vol. 30, no. 4. — P. 651–661. — doi : .
• Ryuhei Uehara, Yushi Uno. Laminar structure of Ptolemaic graphs with applications // . — 2009. — Vol. 157, no. 7. — P. 1533–1543. — doi : .