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

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

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

• 1 Характеристика
• 2 Вычислительная сложность
• 3 Перечисление
• 4 Ссылки

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

• кратчайший путь расстояния подчиняются неравенству Птолемея : для каждых четырех вершины 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-цикла.
• Граф может быть построен из одной вершины с помощью последовательности операций, которые добавляют новая вершина степени один (висячая) или дублирование (двойник) существующей вершины, за исключением того, что двойная операция, в которой новая повторяющаяся вершина не смежна со своим двойником (ложные двойники), может применяться только тогда, когда соседи близнецы образуют клику. Эти три операции без исключения образуют весь дистанционно-наследственный граф. Чтобы сформировать все графы Птолемея, недостаточно использовать висячие вершины и истинные близнецы; иногда также требуется исключительный случай ложных близнецов.
• диаграмма Хассе отношения подмножеств на непустых пересечениях максимальных клик образует ориентированное дерево.
• Выпуклые подмножества вершины (подмножества, содержащие каждый кратчайший путь между двумя вершинами в подмножестве) образуют выпуклую геометрию. То есть, к каждому выпуклому множеству можно добраться из всего множества вершин путем многократного удаления крайней вершины, которая не принадлежит ни одному кратчайшему пути между оставшимися вершинами. В драгоценном камне выпуклое множество uxy не может быть достигнуто таким образом, потому что ни v, ни w не являются экстремальными.

Основываясь на характеристике ориентированными деревьями, графы Птолемея могут быть распознаны в линейное время.

Производящая функция для графиков Птолемея может быть описана символически, что позволяет быстро вычислять номера этих графиков. На основе этого метода количество графов Птолемея с n помеченными вершинами для $n\; =\; 1,\; 2,\; 3,\dots \; \{\backslash \; displaystyle\; n\; =\; 1,2,3,\; \backslash \; dots\}$имеет было обнаружено, что это

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