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

Граф гемм или 3-веер не является графом Птолемея.

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

Характеристика

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

Кратчайшие расстояния пути подчиняются неравенству Птолемея : для каждых четырех вершин $u$ , $v$ , $w$ и $x$ выполняется неравенство $d (u, v) d (w, x) + d (u, x) d (v, w) \geq 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]
Граф может быть построен из одной вершины с помощью последовательности операций, которые добавляют новую вершину степени один (висящую) или дублируют (двойника) существующую вершину, за исключением того, что операция близнеца, в которой новая дублирующая вершина не является смежной со своим близнецом (ложными близнецами), может быть применена только тогда, когда соседи близнецов образуют клику. Эти три операции без исключения образуют все дистанционно-наследственные графы. Чтобы сформировать все птолемеевские графы, недостаточно использовать висячие вершины и истинные близнецы; иногда также требуется исключительный случай ложных близнецов. ^[5]
Диаграмма Хассе отношения подмножества на непустых пересечениях максимальных клик образует ориентированное дерево . ^[6]
Выпуклые подмножества вершин (подмножества, которые содержат каждый кратчайший путь между двумя вершинами в подмножестве) образуют выпуклую геометрию . То есть, каждое выпуклое множество может быть достигнуто из всего множества вершин путем многократного удаления крайней вершины, которая не принадлежит ни одному кратчайшему пути между оставшимися вершинами. ^[7] В драгоценном камне выпуклое множество $uxy$ не может быть достигнуто таким образом, потому что ни $v,$ ни $w$ не являются крайними.

Сложность вычислений

На основе характеристики ориентированных деревьев птолемеевские графы могут быть распознаны за линейное время . ^[6]

Перечисление

Производящая функция для графов Птолемея может быть описана символически , что позволяет быстро вычислять количество этих графов. На основе этого метода было найдено количество графов Птолемея с $n$ помеченными вершинами для ^[8] $n=1,2,3,\точки$

1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... (последовательность A287886 в OEIS )

Ссылки

^ ab Kay, David C.; Chartrand, Gary (1965), "Характеристика некоторых птолемеевых графов", Canadian Journal of Mathematics , 17 : 342–346, doi : 10.4153/CJM-1965-034-0 , MR 0175113.
^ abc Howorka, Edward (1981), «Характеристика птолемеевых графов», Journal of Graph Theory , 5 (3): 323–331, doi :10.1002/jgt.3190050314, MR 0625074.
^ ab "Graphclass: ptolemaic", Информационная система по классам графов и их включениям , получено 2016-06-05.
^ Макки, Терри А. (2010), «Представления птолемеевых графов в виде кликовых графов», Discussiones Mathematicae Graph Theory , 30 (4): 651–661, doi :10.7151/dmgt.1520, MR 2761626.
^ Бандельт, Ханс-Юрген; Малдер, Генри Мартин (1986), «Дистанционно-наследственные графы», Журнал комбинаторной теории , Серия B, 41 (2): 182–208, doi :10.1016/0095-8956(86)90043-2, MR 0859310.
^ ab Uehara, Ryuhei; Uno, Yushi (2009), «Ламинарная структура птолемеевых графов с приложениями», Discrete Applied Mathematics , 157 (7): 1533–1543, doi :10.1016/j.dam.2008.09.006, MR 2510233.
^ Фарбер, Мартин; Джеймисон, Роберт Э. (1986), «Выпуклость в графах и гиперграфах», SIAM Journal on Algebraic and Discrete Methods , 7 (3): 433–444, doi : 10.1137/0607049, hdl : 10338.dmlcz/127659 , MR 0844046.
^ Бахрани, Марьям; Ламброзо, Жереми (2018), «Перечисления, характеристики запрещенных подграфов и расщепление-разложение», Электронный журнал комбинаторики , 25 (4)