Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Клетки [ править ]

Кубический граф (все вершины имеют степень три) Обхват г , который как можно меньше известен как г - клетки (или в виде (3, г ) -cage). Граф Петерсена - это уникальная 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] Эти замечательные графы Рамануджана также имеют большой коэффициент расширения .

Понятия, связанные с данным [ править ]

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

Окружности графа называется длина самой длинной (простой) цикла, а не самый короткий.

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

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

Ссылки [ править ]

  1. ^ Р. Дистель, Теория графов , стр.8. 3-е издание, Springer-Verlag, 2005 г.
  2. ^ Вайсштейн, Эрик В. , "Обхват" , MathWorld
  3. ^ Брауэр, Andries Е. , Садки. Электронное приложение к книге Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
  4. ^ Erdős, Павел (1959), "Теория графов и вероятность", Canadian Journal математики , 11 : 34-38, DOI : 10,4153 / CJM-1959-003-9.
  5. ^ Давидов, Джулиана ; Сарнак, Питер ; Валетт, Ален (2003), элементарная теория чисел, теория групп и графы Рамануджана , Студенческие тексты Лондонского математического общества, 55 , Cambridge University Press, Кембридж, DOI : 10.1017 / CBO9780511615825 , ISBN 0-521-82426-5, Руководство по ремонту  1989434
  6. ^ Чо, Юнг Джин; Чен, Юн; Дин, Ю. (2007), "О (со) обхватом связной матроиды", Дискретная прикладная математика , 155 (18): 2456-2470, DOI : 10.1016 / j.dam.2007.06.015 , МР 2365057 .