Введение

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

Клетки

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

Окружность и окраска графика

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

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

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

Вычисления

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