Vjylku

Обхват в теории графов — длина наименьшего цикла, содержащегося в данном графе^[1]. Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности^[2].
Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников.

Клетки |

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

• 
  

  

  
  

  
  

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

  
  

  
  


• 
  

  

  
  

  
  

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

  
  

  
  


• 
  

  

  
  

  
  

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

  
  

  
  


• 
  

  

  
  

  
  

  Граф Татта — Коксетера (8-клетка Татта) имеет обхват 8
  

  
  

  
  

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

Для любого положительного целого k{displaystyle k} существует граф G{displaystyle G} с обхватом g(G)≥k{displaystyle g(G)geq k} и хроматическим числом χ(G)≥k{displaystyle chi (G)geq k}. Например, граф Грёча является графом без треугольников и имеет хроматическое число 4, а многократное повторение конструкции Мыцельскиана, используемой для создания графа Грёча, образует графы без треугольников со сколь угодно большим хроматическим числом. Пол Эрдёш доказал эту теорему используя вероятностный метод^[4].

План доказательства. Назовём циклы длиной не более k{displaystyle k} короткими, а множества с |G|/k{displaystyle |G|/k} и более вершин — большими. Для доказательства теоремы достаточно найти граф G{displaystyle G} без коротких циклов и больших независимых множеств вершин. Тогда множества цветов в раскраске не будут большими, и, как следствие, для раскраски потребуется k{displaystyle k} цветов.

Чтобы найти такой граф, будем фиксировать вероятность выбора p{displaystyle p} равной nϵ−1{displaystyle n^{epsilon -1}}. При малых ϵ{displaystyle epsilon } в G{displaystyle G} возникает лишь малое число коротких циклов. Если теперь удалить по вершине из каждого такого цикла, полученный граф H{displaystyle H} не будет иметь коротких циклов, а его число независимости будет не меньше, чем у графа G{displaystyle G}^[1].

Близкие концепции |

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

Окружность графа — это длина наибольшего по длине цикла, а не наименьшего.

Размышления о длине наименьшего нетривиального цикла можно рассматривать как обобщение 1-систолы или большей систолы в систолической геометрии^[en].

Примечания |

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.