Обхват (теория графов) - Girth (graph theory)

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

Клетки

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

• 

  Граф Петерсена имеет обхват 5

• 

  Граф хивуда имеет обхват 6

• 

  Граф МакГи имеет обхват 7

• 

  Тутта-граф Кокстер ( Тутта восемь клетка ) имеет обхват-

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

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

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

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

Нечетный обхват и даже обхват графа являются длинами кратчайшего нечетного цикла и даже кратчайшим цикл соответственно.

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

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

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

Рекомендации