Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Граф Птолемея
Граф драгоценных камней или 3-веерный не птолемеев.
Блок - диаграмма , частный случай графа Птолемеевого
Три операции, с помощью которых можно построить любой дистанционно-наследственный граф. Для графов Птолемея соседи ложных близнецов ограничены образованием клики, что препятствует построению показанного здесь 4-цикла.

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

Характеристика [ править ]

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

  • Расстояние кратчайшего пути подчиняется неравенству Птолемея : для любых четырех вершин u , v , w и x выполняется неравенство d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) ≥ 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]

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

Ссылки [ править ]

  1. ^ а б Кей, Дэвид К .; Chartrand, Гэри (1965), "Характеристика некоторых Птолемеев графов", Canadian Journal математики , 17 : 342-346, DOI : 10,4153 / CJM-1965-034-0 , ЛВП : 10338.dmlcz / 126208 , MR  0175113.
  2. ^ Б с Howorka, Эдвард (1981), "Характеризация графов птолемеевских", Журнал теории графов , 5 (3): 323-331, DOI : 10.1002 / jgt.3190050314 , МР 0625074 .
  3. ^ a b "Graphclass: ptolemaic" , Информационная система по классам графов и их включениям , получено 5 июня 2016 г. CS1 maint: обескураженный параметр ( ссылка ).
  4. ^ Макки, Терри А. (2010), "Clique график представления графов птолемеевских", Discussiones Mathematicae Теория графов , 30 (4): 651-661, DOI : 10,7151 / dmgt.1520 , МР 2761626 .
  5. ^ Бандельт, Ханс-Юрген; Малдер, Генри Мартин (1986), "Дистанционно-наследственная графы", Журнал комбинаторной теории , серии B, 41 (2): 182-208, DOI : 10,1016 / 0095-8956 (86) 90043-2 , MR 0859310 .
  6. ^ а б Уэхара, Рюхей; Uno, Yushi (2009), "Ламинарная структура птолемеевских графов с приложениями", Дискретная прикладная математика , 157 (7): 1533-1543, DOI : 10.1016 / j.dam.2008.09.006 , МР 2510233 .
  7. ^ Фарбер, Мартин; Джемисон, Роберт Е. (1986), "выпуклость в виде графиков и гиперграфах", SIAM журнал на алгебраических и дискретных методов , 7 (3): 433-444, DOI : 10,1137 / 0607049 , ЛВП : 10338.dmlcz / 127659 , MR 0844046 .
  8. ^ Бахрани, Марьям; Лумброзо, Жереми (2018), «Перечисления, характеризация запрещенных подграфов и расщепление» , Электронный журнал комбинаторики , 25 (4)