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

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

Клетки

Основная статья: Кейдж (теория графов)

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

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

Обхват и раскраска графика

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

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

Связанные понятия

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

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

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

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

Вычисление

Обхват неориентированного графа можно вычислить, выполнив поиск в ширину из каждого узла со сложностью $O(nm)$ где $n$ - количество вершин графа и $m$ это количество ребер. Практическая оптимизация состоит в том, чтобы ограничить глубину BFS глубиной, которая зависит от длины наименьшего обнаруженного к настоящему моменту цикла. Лучшие алгоритмы известны в случае, когда обхват четный. и когда граф плоский. С точки зрения нижних оценок вычисление обхвата графа по меньшей мере так же сложно, как и решение задачи нахождения треугольника на графе.