Обхват (теория графов)

Длина кратчайшего цикла, содержащегося в графике

В теории графов обхват неориентированного графа — это длина кратчайшего цикла , содержащегося в графе. ^[1] Если граф не содержит циклов (то есть это лес ), его обхват определяется как бесконечность . ^[2] Например, 4-цикл (квадрат) имеет обхват 4. Сетка также имеет обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре или более не содержит треугольников .

Клетки

Кубический граф (все вершины имеют степень три) с обхватом g , который является наименьшим из возможных, известен как g - клетка (или как (3, g ) - клетка). Граф Петерсена является уникальной 5-клеточной (это наименьший кубический граф с обхватом 5), граф Хивуда является уникальной 6-клеточной, граф Макги является уникальной 7-клеточной, а восьмеричная клетка Татта является уникальной 8-клеточной. ^[3] Может существовать несколько клеток для данного обхвата. Например, существует три неизоморфных 10-клетки, каждая с 70 вершинами: 10-клетка Балабана , граф Харриса и граф Харриса–Вонга .

• 
  Граф Петерсена имеет обхват 5
• 
  Граф Хивуда имеет обхват 6
• 
  Граф Макги имеет обхват 7.
• 
  Граф Тутта-Коксетера ( восьмеричная клетка Тутта ) имеет обхват 8.

Раскраска обхвата и графика

Для любых положительных целых чисел g и χ существует граф с обхватом не менее g и хроматическим числом не менее χ ; например, граф Грётша не содержит треугольников и имеет хроматическое число 4, а повторение конструкции Мыцельского, использованной для формирования графа Грётша, дает графы без треугольников с произвольно большим хроматическим числом. Пауль Эрдёш был первым, кто доказал общий результат, используя вероятностный метод . ^[4] Точнее, он показал, что случайный граф на n вершинах, образованный независимым выбором того, включать ли каждое ребро с вероятностью n ^{(1– g )/ g} , имеет с вероятностью, стремящейся к 1, когда n стремится к бесконечности, не более n ⁄ 2 циклов длины g или меньше, но не имеет независимого множества размера n ⁄ 2 k . Таким образом, удаление одной вершины из каждого короткого цикла оставляет меньший граф с обхватом больше g , в котором каждый цветовой класс раскраски должен быть небольшим и который, следовательно, требует не менее k цветов в любой раскраске.

Явные, хотя и большие, графы с большим обхватом и хроматическим числом могут быть построены как определенные графы Кэли линейных групп над конечными полями . ^[5] Эти замечательные графы Рамануджана также имеют большой коэффициент расширения .

Связанные концепции

Нечетный обхват и четный обхват графа — это длины кратчайшего нечетного цикла и кратчайшего четного цикла соответственно.

TheДлина окружности графа — это длина самогодлинного(простого) цикла, а не самого короткого.

Рассматриваемый как наименьшая длина нетривиального цикла, обхват допускает естественные обобщения в виде 1-систолы или более высоких систол в систолической геометрии .

Обхват — это двойственное понятие к связности ребер , в том смысле, что обхват планарного графа — это связность ребер его двойственного графа , и наоборот. Эти концепции объединены в теории матроидов обхватом матроида , размером наименьшего зависимого множества в матроиде. Для графического матроида обхват матроида равен обхвату базового графа, тогда как для ко-графического матроида он равен связности ребер. ^[6]

Вычисление

Обхват неориентированного графа можно вычислить, запустив поиск в ширину из каждого узла со сложностью, где — число вершин графа, а — число ребер. ^[7] Практическая оптимизация заключается в ограничении глубины BFS глубиной, которая зависит от длины наименьшего цикла, обнаруженного на данный момент. ^[8] Известны лучшие алгоритмы в случае, когда обхват четный ^[9] и когда граф плоский. ^[10] С точки зрения нижних границ вычисление обхвата графа по крайней мере так же сложно, как решение задачи поиска треугольника на графе. ${\displaystyle O(nm)}$ ${\displaystyle n}$ ${\displaystyle m}$

Ссылки

1. Р. Дистель, Теория графов , стр. 8. 3-е издание, Springer-Verlag, 2005 г.
2. Вайсштейн, Эрик В. , «Обхват», MathWorld
3. Брауэр, Андрис Э. , Кейджис. Электронное приложение к книге Distance-Regular Graphs (Брауэр, Коэн и Ноймайер, 1989, Springer-Verlag).
4. Эрдёш, Пол (1959), «Теория графов и вероятность», Канадский математический журнал , 11 : 34–38, doi : 10.4153/CJM-1959-003-9 , S2CID  122784453.
5. Давидофф, Джулиана ; Сарнак, Питер ; Валетт, Ален (2003), Элементарная теория чисел, теория групп и графы Рамануджана , Студенческие тексты Лондонского математического общества, т. 55, Cambridge University Press, Кембридж, doi : 10.1017/CBO9780511615825, ISBN 0-521-82426-5, г-н  1989434
6. Чо, Юнг Джин; Чэнь, Йонг; Дин, Юй (2007), «О (со)обхвате связного матроида», Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR  2365057.
7. "Вопрос 3: Вычисление обхвата графа" (PDF) . Архивировано из оригинала (PDF) 29 августа 2017 г. . Получено 22 февраля 2023 г. .
8. Фёлкель, Кристоф Дюрр, Луи Абрахам и Финн (6 ноября 2016 г.). «Кратчайший цикл». Попробуйте Алго . Проверено 22 февраля 2023 г.{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
9. "ds.algorithms - Оптимальный алгоритм для нахождения обхвата разреженного графа?". Theoretical Computer Science Stack Exchange . Получено 2023-02-22 .
10. Чанг, Сянь-Чи; Лу, Сюэ-И. (2013). «Вычисление обхвата планарного графа за линейное время». SIAM Journal on Computing . 42 (3): 1077–1094. arXiv : 1104.4892 . doi : 10.1137/110832033. ISSN  0097-5397. S2CID  2493979.