Обхват в теорії графів — довжина найкоротшого циклу, що міститься в заданому графі. Якщо граф не містить циклів (тобто є ациклічним графом), його обхват за визначенням дорівнює нескінченності. Наприклад, 4-цикл (квадрат) має обхват 4. Квадратна ґратка має також обхват 4, а трикутна сітка має обхват 3. Граф з обхватом чотири і більше не містить трикутників.
Клітки
Кубічні графи (всі вершини мають степінь три) з якомога меншим обхватом відомі як
-клітка (або як (3,
)-клітка). Граф Петерсена — це єдина 5-клітка (найменший кубічний граф з обхватом 5), граф Хівуда — це єдина 6-клітка, (Граф Маꥳ) — це єдина 7-клітка, а (граф Татта — Коксетера) — це єдина 8-клітка. Може існувати кілька кліток для даного обхвату. Наприклад, існує три неізоморфних 10-клітки, кожна з 70 вершинами — [en], [en] і [en].
- Граф Петерсена має обхват 5
- Граф Хівуда має обхват 6
- (Граф Маꥳ) має обхват 7
- (Граф Татта — Коксетера) (8-клітка Татта) має обхват 8
Обхват і розфарбовування графа
Для будь-якого додатного цілого існує граф
з обхватом
і хроматичним числом
. Наприклад, (граф Ґрьоча) є графом без трикутників і має хроматичне число 4, а багаторазове повторення побудови (мичельськіана), що використовується для створення графа Ґрьоча, утворює графи без трикутників з як завгодно великим хроматичним числом. Пол Ердеш довів цю теорему, використовуючи імовірнісний метод.
План доведення. Назвемо цикли довжиною не більше короткими, а множини з
і більше вершин — великими. Для доведення теореми достатньо знайти граф
без коротких циклів і великих незалежних множин вершин. Тоді множина кольорів в розфарбовуванні не будуть більшими, і, як наслідок, для розфарбування потрібно
кольорів.
Щоб знайти такий граф, будемо фіксувати ймовірність вибору , що дорівнює
. При маленьких
в
виникає лише мале число коротких циклів. Якщо тепер видалити по вершині з кожного такого циклу, отриманий граф
не матиме коротких циклів, а його число незалежності буде не менше, ніж у графа
.
Пов'язані концепції
Непарний обхват і парний обхват графа — це коли довжина найменшого непарного циклу і найменшого парного циклу відповідно.
Окружність графа — це довжина найбільшого по довжині циклу, а не найменшого.
Спроби оцінити довжину найменшого нетривіального циклу можна розглядати як узагальнення 1-систоли або більшої систоли в [en].
Примітки
- R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
- , архів оригіналу за 4 серпня 2020, процитовано 30 жовтня 2015
- , , архів оригіналу за 4 серпня 2020, процитовано 30 жовтня 2015. Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
- (Erdős, Paul) (1959), Graph theory and probability, Canadian Journal of Mathematics, 11: 34—38, doi:10.4153/CJM-1959-003-9.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет