НОУ ІНТУІТ, Лекція, Розфарбовування графів

Гіпотеза про чотири фарби

Вже сто років математики намагаються довести гіпотезу чотирьох фарб. У цьому напрямі було досягнуто значного прогресу. У пресі з'явилося повідомлення (K.Appel, W.Haken, Every planar map is four colorable, Bull. of Amer. Math . Soc ., 82, \No\,5 (sept. 1976)), що гіпотезу чотирьох фарб вдалося обгрунтувати з використанням ЕОМ.

Сформулюємо без доказу результатів, які належать до цієї проблеми.

Якщо гіпотеза чотирьох фарб не вірна, то будь-який приклад, що її спростовує, буде дуже складним. Відомо, наприклад, що кожен планарний граф, що має менше вершин, 4-розмальовуємо.
Будь-який не містить трикутників планарний граф 3-розфарбовуємо (теорема Греча).
Якщо спробувати довести гіпотезу чотирьох фарб, достатньо довести її для гамільтонових планарних графів (досить несподіваний результат Вітні).

Розфарбовування карт

Виникнення гіпотези чотирьох фарб історично пов'язані з розфарбовуванням географічних карт. Якщо є карта із зображенням кількох країн, то цікаво дізнатися, скільки знадобиться кольорів для такого розфарбування цих країн, щоб жодні дві сусідні країни не були забарвлені в той самий колір. Можливо, найзвичніша форма гіпотези чотирьох фарб така: будь-яку карту можна розфарбувати за допомогою чотирьох фарб.

Щоб зробити це твердження точним, слід визначити, що означає слово "карта". Оскільки в розглянутих нами завданнях розмальовки потрібно, щоб країни, розташовані по обидва боки ребра, були різного кольору, доведеться виключити карти, що мають мост. Таким чином, зручно визначити карту як зв'язковий плоский граф, що не містить мостів. Зауважимо, що за такого визначення карти невиключаємо петель або кратних ребер.

Назвемо карту - розфарбовується, якщо її грані можна розфарбувати фарбами так, щоб жодні дві суміжні грані, тобто грані, межі яких мають спільне ребро, не були одного кольору. Там, де можна заплутатися, будемо використовувати термін вершинно - що розфарбовується, маючи на увазі розфарбовуваність в описаному вище сенсі. Наприклад, зображений нижче граф є 3-розфарбовується і вершинно 4-розфарбовується.

Тепер сформулюємо гіпотезу чотирьох фарб для карт: будь-яка карта 4-розмальовується.

Теорема 8.3. Карта є 2-розфарбовується тоді і тільки тоді, якщо є ейлерів граф .

ДоказБудь-яку вершину має оточувати парне число граней, так як їх можна розфарбувати в два кольори. Звідси випливає, що ступінь кожної вершини парний, і тому граф ейлерів.

Жорданової кривої, або жорданової дугою, на площині називається безперервна крива, яка не має самоперетинів; замкнутою жерданової кривою називається жерданова крива, початок і кінець якої збігаються.

Опишемо спосіб, що дає необхідне забарвлення граней графа. Виберемо довільну грань та пофарбуємо її у червоний колір. Проведемо криву Жорданову з точки грані в деяку точку будь-якої грані, причому так, щоб ця крива не проходила ні через яку вершину графа. Якщо на шляху від точки до точки грані наша крива перетне парне число ребер, пофарбуємо грань у червоний колір; в іншому випадку - в синій.

Неважко показати, що розфарбовування визначено коректно: беремо "цикл", що складається з двох таких кривих жорданових (тобто замкнуту криву жорданову), і показуємо, що він перетинає парне число ребер графа (треба використовувати індукцію за кількістю вершин, що знаходяться всередині циклу, і тойфакт, що на кожній вершині графа інцидентно парне число ребер).