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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Клітини[ред.ред. код]

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

Обхват і розфарбовування графа[ред.ред. код]

Для будь-якого додатнього цілого існує граф з обхватом і хроматичним числом . Наприклад, граф Грьоча[ru] є графом без трикутників і має хроматичне число 4, а багаторазове повторення конструкції Мицельскіана[ru], що використовується для створення графа Грьоча, утворює графи без трикутників з як завгодно великим хроматичним числом. Пол Ердеш довів цю теорему, використовуючи імовірнісний метод[4].

План доведення. Назвемо цикли довжиною не більше короткими, а множини з і більше вершин — великими. Для доведення теореми достатньо знайти граф без коротких циклів і великих незалежних множин вершин. Тоді безлічі кольорів в розфарбовуванні НЕ будуть більшими, і, як наслідок, для розмальовки потрібно кольорів.

Щоб знайти такий граф, будемо фіксувати ймовірність вибору , що дорівнює . При маленьких в виникає лише мале число коротких циклів. Якщо тепер видалити по вершині з кожного такого циклу, отриманий граф не матиме коротких циклів, а його число незалежності буде не менше, ніж у графа [1].

Близькі концепції[ред.ред. код]

Парний обхват и парний обхват графа — це довжини найменшого непарного циклу і парного циклу відповідно.

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

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


Примітки[ред.ред. код]

  1. а б Рейнгард Дистель {{{Заголовок}}}.
  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.