Птолеме́ев граф — это неориентированный граф, в котором расстояния по кратчайшему пути удовлетворяют неравенству Птолемея. Птолемеевы графы — это в точности графы, которые одновременно являются и хордальными, и дистанционно наследуемыми. Эти графы включают блоковые графы и являются подклассом совершенных графов.
Описание Граф является птолемеевым тогда и только тогда, когда он удовлетворяет следующим эквивалентным условиям: Расстояния по кратчайшему пути удовлетворяют неравенству Птолемея — для любых четырёх вершин , , и выполняется неравенство . Например, граф-изумруд (3-веер) на рисунке не является птолемеевым, поскольку в этом графе больше, чем . Для любых перекрывающихся максимальных клик их пересечение является сепаратором, который разделяет разность этих двух клик. Для графа-изумруда на иллюстрации это не так — клики и не разделяются их пересечением , поскольку существует ребро , соединяющее клики. Любой цикл с вершинами имеет по меньшей мере диагоналей. Граф является и хордальным (любой цикл с длиной, превосходящей три, имеет диагональ), и дистанционно-наследуемым (любой связный порождённый подграф имеет те же расстояния, что и весь граф). Граф-изумруд является хордальным, но не дистанционно-наследуемым — в подграфе, порождённом , расстояние от до равно 3, что больше, чем расстояние между теми же вершинами в полном графе. Поскольку как хордальные, так и дистанционно-наследуемые графы являются совершенными, таковыми же являются и птолемеевы графы . Граф хордален и не содержит изумрудов — графов, образованных добавлением двух непересекающихся диагоналей в пятиугольник .. Граф является дистанционно-наследуемым и не содержит порождённых 4-циклов. Граф может быть построен из единственной вершины последовательностью операций, при которых добавляется новая вершина степени 1 (висячая) или дублируется существующая вершина (образуя близняшки или двойняшки), с условием, что операция удвоения, в которой дубликат вершины не смежен своей паре (двойняшки), только если соседи этих удвоенных вершин образуют клику. Эти три операции, если не применять указанное условие, образуют все дистанционно-наследуемые графы. Для образования птолемеевых графов недостаточно использовать образование висячих вершин и близняшек, образование двойняшек (при соблюдении указанных выше условий) тоже иногда требуется. Диаграмма Хассе подмножества отношений непустого пересечения максимальных клик образует . Выпуклые подмножества вершин (подмножества, содержащие все кратчайшие пути между двумя вершинами в подмножестве) образуют . То есть любое выпуклое множество может быть получено из полного набора вершин последовательным удалением крайних вершин, то есть не принадлежащих какому-либо кратчайшему пути между оставшимися вершинами. В изумруде выпуклое множество не может быть получено таким способом, поскольку ни , ни не являются крайними.
Вычислительная сложность Основываясь на описании ориентированными деревьями, птолемеевы графы можно распознать за линейное время.
Примечания
Литература
Категория:Семейства графов Категория:Совершенные графы