В теории графов геодезический граф - это неориентированный граф, такой, что существует уникальный (невзвешенный) кратчайший путь между каждыми двумя вершинами.
Геодезические графы были введены в 1962 году Ойстейном Оре , который заметил, что они обобщают свойство деревьев (в которых существует уникальный путь между каждыми двумя вершинами независимо от расстояния), и попросил дать их характеристику. [1] Хотя эти графики можно распознать за полиномиальное время , «более шестидесяти лет спустя полная характеристика все еще неуловима». [2]
Примеры [ править ]
Каждое дерево , [1] каждый полный граф , [3] и каждый граф цикла нечетной длины являются геодезическими. [4]
Если это геодезический граф, то замена каждого ребра на путь такой же нечетной длины приведет к созданию другого геодезического графа. [5] В случае полного графа возможна более общая схема замены путями: выберите неотрицательное целое число для каждой вершины и разделите каждое ребро , добавив к нему вершины. Тогда результирующий разбитый полный граф является геодезическим, и каждый геодезически разбитый полный граф может быть получен таким образом. [6] [7]
Связанные классы графов [ править ]
Если каждый двусвязный компонент графа является геодезическим, то сам граф является геодезическим. В частности, каждый блочный граф (графы, в которых двусвязные компоненты завершены ) является геодезическим. [3] Точно так же, поскольку граф циклов является геодезическим, когда он имеет нечетную длину, каждый граф кактусов, в котором циклы имеют нечетную длину, также является геодезическим. Эти графы кактусов представляют собой в точности связные графы, в которых все циклы имеют нечетную длину. Более того, плоский граф является геодезическим тогда и только тогда, когда все его двусвязные компоненты являются либо циклами нечетной длины, либо геодезическими подразделениями клики с четырьмя вершинами. [4]
Вычислительная сложность [ править ]
Геодезические графы можно распознать за полиномиальное время , используя вариант поиска в ширину, который может обнаруживать несколько кратчайших путей, начиная с каждой вершины графа. Геодезические графы не могут содержать индуцированный граф циклов с четырьмя вершинами или индуцированный ромбовидный граф , потому что эти два графа не являются геодезическими. [3] В частности, как подмножество графов без ромбов, геодезические графы обладают тем свойством, что каждое ребро принадлежит уникальной максимальной клике ; в этом контексте максимальные клики также называются линиями . [8] Отсюда следует, что задача нахождения максимальных клик, или клики с максимальным весом, могут быть решены за полиномиальное время для геодезических графов, перечислив все максимальные клики. Более широкий класс графов, не имеющих индуцированного 4-цикла или ромба, называется «слабо геодезическим»; это графы, в которых вершины, находящиеся на расстоянии ровно два друг от друга, имеют уникальный кратчайший путь. [3]
Диаметр два [ править ]
Для графов диаметра два (то есть графов, в которых все вершины находятся на расстоянии не более двух друг от друга) геодезические графы и слабо геодезические графы совпадают. Каждый геодезический граф диаметра два бывает трех типов:
- блочный граф, в котором все максимальные клики соединены в одной общей вершине, включая графы ветряных мельниц ,
- сильно регулярный граф с параметром (число общих соседей для каждой несмежной пары вершин) равно единице, или
- граф с ровно двумя разными степенями вершины .
Сильно регулярные геодезические графики включают в себя график 5-вершины цикла, граф Петерсена , а граф Хоффман-Singleton . Несмотря на дополнительные исследования свойств, которыми должен обладать такой граф, [9] [10] неизвестно, существует ли больше таких графов или их бесконечно много. [8]
Существует ли бесконечно много сильно регулярных геодезических графов?
Геодезические графы с диаметром два и двумя разными степенями не могут иметь треугольник, состоящий из вершин обеих степеней. Их можно построить из любой конечной аффинной плоскости , добавив к графу инцидентности плоскости точка-линия дополнительных ребер между вершинами, соответствующими каждой из двух параллельных прямых. Для бинарной аффинной плоскости с четырьмя точками и шестью двухточечными линиями в трех параллельных парах результатом этой конструкции является граф Петерсена, но для конечных аффинных плоскостей высшего порядка он дает графы с двумя разными степенями. Известны и другие родственные конструкции геодезических графов из конечных геометрий, но не известно, исчерпывают ли они все возможные геодезические графы с диаметром два и двумя разными степенями. [8]
Ссылки [ править ]
- ^ a b Ore, Øystein (1962), Теория графов , Публикации коллоквиума, 38 , Провиденс, Род-Айленд: Американское математическое общество, стр. 104, ISBN 9780821810385, Руководство по ремонту 0150753
- ^ Корнельсен, Сабина; Пфистер, Максимилиан; Ферстер, Генри; Гронеманн, Мартин; Хоффманн, Майкл; Кобуров, Стивен; Шнек, Томас (2020), «Рисование кратчайших путей в геодезических графах», Труды 28-го Международного симпозиума по рисованию графиков и визуализации сети , arXiv : 2008.07637
- ^ a b c d "Геодезические графы" , Информационная система по классам графов и их включениям , получено 14 сентября 2020 г. CS1 maint: обескураженный параметр ( ссылка )
- ^ a b Stemple, Джоэл Дж .; Уоткинс, Марк Э. (1968), «О плоских геодезических графах», Журнал комбинаторной теории , 4 (2): 101–117, DOI : 10.1016 / S0021-9800 (68) 80035-3 , MR 0218267
- ^ Parthasarathy, KR; Сринивасан, Н. (1982), "Некоторые общие конструкции геодезических блоков", Журнал комбинаторной теории , Series B, 33 (2): 121-136, DOI : 10,1016 / 0095-8956 (82) 90063-6 , МР 0685061
- ^ Плесник, Ян (1977), "Две конструкции геодезических графов", Mathematica Slovaca , 27 (1): 65–71, MR 0460179
- ^ Стемпл, Джоэл Г. (1979), «Геодезические графы, гомеоморфные полному графу», Вторая международная конференция по комбинаторной математике (Нью-Йорк, 1978) , Анналы Нью-Йоркской академии наук , 319 , стр. 512–517, DOI : 10.1111 / j.1749-6632.1979.tb32829.x , МР 0556062
- ^ a b c Blokhuis, A .; Брауэр, А. Е. (1988), "Геодезический граф диаметра два", Geometriae Dedicata , 25 (1-3): 527-533, DOI : 10.1007 / BF00191941 , МР 0925851 , S2CID 189890651 CS1 maint: обескураженный параметр ( ссылка )
- ^ Белоусов И.Н.; Махнев А.А. (2006), "О сильно регулярных графах с автоморфизмами и их автоморфизмами", Докл. Академии наук , 410 (2): 151–155, MR 2455371.
- ^ Deutsch, J .; Фишер, PH (2001), "О сильно регулярных графов с ", Европейский журнал комбинаторике , 22 (3): 303-306, DOI : 10,1006 / eujc.2000.0472 , MR 1822718