График Птолемея
В теории графов граф Птолемея — это неориентированный граф которого , кратчайшие пути подчиняются неравенству Птолемея , которое, в свою очередь, было названо в честь греческого астронома и математика Птолемея . Графы Птолемея — это в точности графы, которые одновременно являются хордальными и дистанционно-наследственными ; они включают в себя блок-графы [1] и являются подклассом идеальных графов .
Характеристика
[ редактировать ]Граф является птолемеевским тогда и только тогда, когда он удовлетворяет любому из следующих эквивалентных условий:
- Расстояния кратчайшего пути подчиняются неравенству Птолемея : для каждых четырех вершин u , v , w и x неравенство d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) ≥ d ( ты , ш ) d ( v , x ) имеет место. [1] Например, граф драгоценных камней (3-веер) на иллюстрации не является птолемеевским, потому что в этом графе d ( u , w ) d ( v , x ) = 4 , больше, чем d ( u , v ) d ( w , x ) + d ( ты , Икс ) d ( v , ш ) знак равно 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]
- 1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... (последовательность A28788 6 место в OEIS )
Ссылки
[ редактировать ]- ^ Jump up to: а б Кей, Дэвид С.; Чартран, Гэри (1965), «Характеристика некоторых птолемеевых графов», Canadian Journal of Mathematics , 17 : 342–346, doi : 10.4153/CJM-1965-034-0 , MR 0175113 .
- ^ Jump up to: а б с Ховорка, Эдвард (1981), «Характеристика графов Птолемея», Журнал теории графов , 5 (3): 323–331, doi : 10.1002/jgt.3190050314 , MR 0625074 .
- ^ Jump up to: а б «Графкласс: птолемеев» , Информационная система по классам графов и их включениям , получено 5 июня 2016 г.
- ^ Макки, Терри А. (2010), «Представления графов Птолемея кликовыми графами», Дискуссии 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 .
- ^ Jump up to: а б Уэхара, Рюхей; Уно, Юши (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)