Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов геодезический граф - это неориентированный граф, такой, что существует уникальный (невзвешенный) кратчайший путь между каждыми двумя вершинами.

Геодезические графы были введены в 1962 году Ойстейном Оре , который заметил, что они обобщают свойство деревьев (в которых существует уникальный путь между каждыми двумя вершинами независимо от расстояния), и попросил дать их характеристику. [1] Хотя эти графики можно распознать за полиномиальное время , «более шестидесяти лет спустя полная характеристика все еще неуловима». [2]

Примеры [ править ]

Каждое дерево , [1] каждый полный граф , [3] и каждый граф цикла нечетной длины являются геодезическими. [4]

Если это геодезический граф, то замена каждого ребра на путь такой же нечетной длины приведет к созданию другого геодезического графа. [5] В случае полного графа возможна более общая схема замены путями: выберите неотрицательное целое число для каждой вершины и разделите каждое ребро , добавив к нему вершины. Тогда результирующий разбитый полный граф является геодезическим, и каждый геодезически разбитый полный граф может быть получен таким образом. [6] [7]

Связанные классы графов [ править ]

Блок - диаграмма , частный случай геодезического графа
Граф Петерсена , один из геодезических графов диаметра два

Если каждый двусвязный компонент графа является геодезическим, то сам граф является геодезическим. В частности, каждый блочный граф (графы, в которых двусвязные компоненты завершены ) является геодезическим. [3] Точно так же, поскольку граф циклов является геодезическим, когда он имеет нечетную длину, каждый граф кактусов, в котором циклы имеют нечетную длину, также является геодезическим. Эти графы кактусов представляют собой в точности связные графы, в которых все циклы имеют нечетную длину. Более того, плоский граф является геодезическим тогда и только тогда, когда все его двусвязные компоненты являются либо циклами нечетной длины, либо геодезическими подразделениями клики с четырьмя вершинами. [4]

Вычислительная сложность [ править ]

Геодезические графы можно распознать за полиномиальное время , используя вариант поиска в ширину, который может обнаруживать несколько кратчайших путей, начиная с каждой вершины графа. Геодезические графы не могут содержать индуцированный граф циклов с четырьмя вершинами или индуцированный ромбовидный граф , потому что эти два графа не являются геодезическими. [3] В частности, как подмножество графов без ромбов, геодезические графы обладают тем свойством, что каждое ребро принадлежит уникальной максимальной клике ; в этом контексте максимальные клики также называются линиями . [8] Отсюда следует, что задача нахождения максимальных клик, или клики с максимальным весом, могут быть решены за полиномиальное время для геодезических графов, перечислив все максимальные клики. Более широкий класс графов, не имеющих индуцированного 4-цикла или ромба, называется «слабо геодезическим»; это графы, в которых вершины, находящиеся на расстоянии ровно два друг от друга, имеют уникальный кратчайший путь. [3]

Диаметр два [ править ]

Для графов диаметра два (то есть графов, в которых все вершины находятся на расстоянии не более двух друг от друга) геодезические графы и слабо геодезические графы совпадают. Каждый геодезический граф диаметра два бывает трех типов:

  • блочный граф, в котором все максимальные клики соединены в одной общей вершине, включая графы ветряных мельниц ,
  • сильно регулярный граф с параметром (число общих соседей для каждой несмежной пары вершин) равно единице, или
  • граф с ровно двумя разными степенями вершины .

Сильно регулярные геодезические графики включают в себя график 5-вершины цикла, граф Петерсена , а граф Хоффман-Singleton . Несмотря на дополнительные исследования свойств, которыми должен обладать такой граф, [9] [10] неизвестно, существует ли больше таких графов или их бесконечно много. [8]

Нерешенная задача по математике :

Существует ли бесконечно много сильно регулярных геодезических графов?

(больше нерешенных задач по математике)

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

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

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