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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(еще нерешенные задачи по математике)

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

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

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

[ore-1] Jump up to: Перейти обратно: ^а ^б Оре, Эйстейн (1962), Теория графов , Публикации коллоквиума, том. 38, Провиденс, Род-Айленд: Американское математическое общество, с. 104, ISBN 9780821810385 , МР 0150753

[cghks-2] Корнельсен, Сабина; Пфистер, Максимилиан; Ферстер, Генри; Гронеманн, Мартин; Хоффманн, Майкл; Кобуров, Стивен; Шнек, Томас (2020), «Рисование кратчайших путей на геодезических графиках», Труды 28-го Международного симпозиума по рисованию графиков и сетевой визуализации , arXiv : 2008.07637

[gc-3] Jump up to: Перейти обратно: ^а ^б ^с ^д «Геодезические графики» , Информационная система по классам графов и их включениям , получено 14 сентября 2020 г.

[sw-4] Jump up to: Перейти обратно: ^а ^б Стемпл, Джоэл Г.; Уоткинс, Марк Э. (1968), «О плоских геодезических графах», Журнал комбинаторной теории , 4 (2): 101–117, doi : 10.1016/S0021-9800(68)80035-3 , MR 0218267

[ps-5] Партасарати, КР; Сринивасан, Н. (1982), «Некоторые общие конструкции геодезических блоков», Журнал комбинаторной теории , серия B, 33 (2): 121–136, doi : 10.1016/0095-8956(82)90063-6 , MR 0685061

[plesnik-6] Плесник, Ян (1977), «Две конструкции геодезических графов», Mathematica Slovaca , 27 (1): 65–71, MR 0460179

[stemple-7] Стемпл, Джоэл Г. (1979), «Геодезические графы, гомеоморфные полному графу», Вторая международная конференция по комбинаторной математике (Нью-Йорк, 1978) , Анналы Нью-Йоркской академии наук , том. 319, стр. 512–517, doi : 10.1111/j.1749-6632.1979.tb32829.x , MR 0556062

[bb-8] Jump up to: Перейти обратно: ^а ^б ^с Блокхейс, А .; Брауэр, А.Е. (1988), «Геодезические графики второго диаметра», Geometriae Dedicata , 25 (1–3): 527–533, doi : 10.1007/BF00191941 , MR 0925851 , S2CID 189890651

[bm-9] Белоусов И.Н.; Махнев А.А. (2006), "О сильно регулярных графах с $\mu =1$ и их автоморфизмы», Доклады Академии наук , 410 (2): 151–155, МР 2455371.

[df-10] Дойч, Дж.; Фишер, П.Х. (2001), "О сильно регулярных графах с $\mu =1$ ", Европейский журнал комбинаторики , 22 (3): 303–306, doi : 10.1006/eujc.2000.0472 , MR 1822718.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]