Обхват (теория графов)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Клетки[править | править исходный текст]

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

Обхват и раскраска графа[править | править исходный текст]

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

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

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

Близкие концепции[править | править исходный текст]

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

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

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

Примечания[править | править исходный текст]

  1. 1 2 Рейнгард Дистель Теория графов. — Новосибирск, 2002.
  2. Girth -- Wolfram MathWorld.
  3. Andries E. Brouwer Cages. Электронное приложение к книге Distance-Regular Graphs (Brouwer, Cohen, Neumaier 1989, Springer-Verlag).
  4. Paul Erdős Graph theory and probability // Canadian Journal of Mathematics. — 1959. — Т. 11. — С. 34–38. — DOI:10.4153/CJM-1959-003-9.