В теории графов обхват неориентированного графа — это длина кратчайшего цикла , содержащегося в графе. [1] Если граф не содержит циклов (то есть является лесом ), его обхват определяется как бесконечность . [2] Например, 4-цикл (квадрат) имеет обхват 4. Сетка также имеет обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не содержит треугольников .
Кубический граф (все вершины имеют степень три) минимально возможного обхвата g называется g - клеткой (или (3, g ) -клеткой). Граф Петерсена представляет собой уникальную 5-клеточную клетку (это наименьший кубический граф с обхватом 5), граф Хивуда представляет собой уникальную 6-клеточную, граф МакГи представляет собой уникальную 7-клеточную, а восьмеричная клетка Тутта представляет собой уникальную 8-клеточную. клетка. [3] Для данного обхвата может существовать несколько клеток. Например, существуют три неизоморфные 10-клетки, каждая из которых имеет 70 вершин: 10-клетка Балабана , граф Харриса и граф Харриса-Вонга .
Для любых натуральных чисел 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] С точки зрения нижних оценок, вычисление обхвата графа по меньшей мере так же сложно, как и решение задачи нахождения треугольника на графе.
{{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )