Геодезический график - Geodetic graph

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

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

Примеры

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

Если ${\displaystyle G}$ является геодезическим графом, то заменяя каждое ребро ${\displaystyle G}$ по пути такой же нечетной длины получится другой геодезический граф.^[5]В случае полный график, возможна более общая схема замены путями: выбираем неотрицательное целое число ${\displaystyle f(v)}$ для каждой вершины ${\displaystyle v}$, и разделить каждое ребро ${\displaystyle uv}$ добавляя ${\displaystyle f(u)+f(v)}$ вершины к нему. Тогда результирующий разбитый полный граф является геодезическим, и каждый геодезически разбитый полный граф может быть получен таким образом.^[6][7]

Связанные классы графов

А блочный граф, частный случай геодезического графа

В Граф Петерсена, один из геодезических графиков диаметра два

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

Вычислительная сложность

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

Диаметр два

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

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

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

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

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

Рекомендации

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