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

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

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

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

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

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

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

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

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

Пов'язані концепції[ред. | ред. код]

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

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

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


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

  1. а б R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
  2. Girth – Wolfram MathWorld. 
  3. Brouwer, Andries E.. Cages. . Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
  4. Erdős, Paul (1959). Graph theory and probability. Canadian Journal of Mathematics 11: 34–38. doi:10.4153/CJM-1959-003-9. .