Материал: discrete_mathematics

Завдання для самостійної роботи

1.Скільком граням може належати вершина степеня k плоского графа?

2.Довести, що будь-яке дерево є планарним графом. Скільки граней має дерево?

3.Чому дорівнює степінь єдиної грані дерева з n вершинами?

4.Довести, що кількість граней будь-якого плоского укладання зв'язного планарного графа з n вершинами та m ребрами є вели-

чиною сталою й дорівнює m − n + 2, тобто

| P | = | E | − |V | + 2.

Отже, число | P | – це інваріант для заданого планарного графа G, тобто воно не залежить від способу укладання графа на площині.

5.Знайти зв'язний плоский граф із n вершинами та m ребрами, для якого m > 3n − 6.

6.Довести, що для довільного плоского графа G = (V, E) із k компонентами зв'язності виконується рівність

|V | − | E | + | P | = k + 1 (узагальнена формула Ейлера).

7.Довести, що кількість внутрішніх граней довільного плоского графа G дорівнює цикломатичному числу ν(G) графа G.

8.Чи існує планарний граф, який має: (а) 7 вершин і 15 ребер; (б) 8 вершин і 19 ребер?

9.Чи існує плоский граф із шістьма вершинами, що має де- в'ять граней?

10.Довести, що для зв'язного плоского графа з n вершинами

(n ≥ 3) і m ребрами, який не містить трикутників, виконується нерівність m ≤ 2n − 4.

11. Довести, що граф є максимальним плоским графом тоді й тільки тоді, коли він є тріангуляцією.

4.9. Розфарбування графів

Нехай G = (V, E) – довільний граф, а Nk = {1, 2, …, k }. Будь-яке відображення f : V → Nk, яке кожній вершині v V

ставить у відповідність деяке натуральне число f (v) Nk, називають розфарбуванням графа G. Число f (v) називають кольо ром, або номером фарби, вершини v.

186

Розфарбування f графа G називають правильним, якщо для будь-яких його суміжних вершин v і w виконується f (v) ≠ f (w).

Мінімальне число k, для якого існує правильне розфарбування графа G, називають хроматичним числом графа G і позначають χ(G).

Мінімальним правильним розфарбуванням графа G нази-

вають правильне розфарбування для k = χ(G).

Для певних типів графів визначити хроматичні числа нескладно. Наприклад, 1-хроматичними є порожні графи G = (V, ) і тільки вони. Хроматичне число повного графа Kn дорівнює n, а хроматичне число довільного двочасткового графа − 2. 2-хрома- тичні графи часто називають біхроматичними.

Неважко обґрунтувати такі твердження.

Якщо кожна зв'язна компонента графа G потребує для свого правильного розфарбування не більше k фарб, то χ(G) ≤ k.

Граф є біхроматичним тоді й тільки тоді, коли він двочастковий. Зокрема, усі дерева та прості цикли парної довжини C2k біхроматичні. Водночас χ(C2k + 1) = 3.

Приклад 4.17. Доведемо, що для довільного графа G виконується нерівність χ(G) ≤ (G) + 1, де (G) – найбільший зі степенів вершин графа G.

Доведення проведемо індукцією за кількістю n вершин графа G. Для тривіального графа (n = 1) і графів із двома вершинами нерівність виконується.

Нехай твердження теореми виконується для всіх графів із кількістю вершин t (t ≥ 2). Розглянемо довільний граф G із t + 1 вершиною. Вилучимо з нього деяку вершину v. Дістанемо граф G′, степені всіх вершин якого не перевищують (G). Отже, за припущенням індукції для правильного розфарбування G′ потрібно не більше ніж (G) + 1 фарб. Правильне розфарбування для G дістанемо з правильного розфарбування графа G′, якщо пофарбуємо вершину v у колір, відмінний від кольорів усіх суміжних із v вершин. Оскільки таких вершин не більше ніж (G), то для правильного розфарбування графа G достатньо (G) + 1 фарб. ◄

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

в'язано зі відомою проблемою (гіпотезою) чотирьох фарб.

187

Грані плоскої карти назвемо суміжними, якщо їхні межі мають принаймні одне спільне ребро.

Гіпотеза чотирьох фарб виникла у зв'язку з розфарбуванням друкованих географічних карт (звідси й термін плоска карта) і

була сформульована так: грані довільної плоскої карти можна

розфарбувати не більше ніж чотирма фарбами так, що будь які суміжні грані матимуть різні кольори.

Згодом з'явилось інше, рівносильне, формулювання гіпотези чотирьох фарб: для правильного розфарбування вершин довіль ного планарного графапотрібно небільше чотирьохфарб.

Ця гіпотеза виникла в середині ХIХ ст. Більше ста років дослідники намагалися її довести чи спростувати. У результаті багаторічних досліджень виявилось, що для розв'язання проблеми чотирьох фарб потрібно перевірити її справедливість для скінченної кількості графів певного вигляду. Кількість варіантів, які потрібно було перебрати, була настільки великою, що тільки за допомогою потужної ЕОМ, яка неперервно працювала протягом більше двох місяців, у 1976 р. справедливість гіпотези чотирьох фарб було підтверджено. Однак такий фізичний, експериментальний спосіб доведення не зовсім влаштовує багатьох професіональних математиків, тому вони продовжують пошуки аналітичного доведення гіпотези.

Набагато простіше можна отримати такі результати. Приклад 4.18. Довести, що для правильного розфарбування

довільного планарного графа потрібно не більше шести фарб. Доведення виконаємо індукцією за кількістю n вершин гра-

фа. Для n ≤ 6 твердження очевидне.

Припустимо, що хроматичне число всіх планарних графів із t вершинами не перевищує 6 (t ≥ 6). Розглянемо довільний планарний граф G із t + 1 вершиною. Згідно із прикладом 4.15(5) у графі G існує вершина v, степінь якої не більше 5. Вилучимо вершину v із графа G. Отримаємо граф G′, вершини якого за припущенням індукції можна правильно розфарбувати не більше ніж у шість кольорів. Тоді правильне розфарбування для G отримаємо з одержаного правильного розфарбування графа G′, надаючи вершині v колір, відмінний від кольорів усіх суміжних із нею вершин. Оскільки таких вершин не більше п'яти, то для виконання цієї процедури достатньо шести фарб. Отже,

χ(G) ≤ 6. ◄

188

Пропонуємо самостійно переконатись у справедливості такого твердження: для довільного планарного графа G виконується

χ(G) ≤ 5.

Граф G називають критичним, якщо хроматичне число підграфа G', отриманого в результаті вилучення будь-якої вершини із G, строго менше, ніж хроматичне число графа G.

Критичний граф G, для якого k = χ(G), називають k-кри тичним.

Приклад 4.19.

1. Доведемо, що будь-який повний граф є критичним.

χ(Kn) = n, а після вилучення довільної вершини з Kn (див. п. 4.2) отримаємо повний граф Kn – 1, хроматичне число якого дорівнює n – 1.

2. Довести, що довільний критичний граф є зв'язним. Припустимо, що деякий критичний граф G є незв'язним і має

кілька компонент зв'язності. Вилучимо довільну вершину з тієї компоненти зв'язності графа G, хроматичне число якої не перевищує хроматичні числа решти компонент зв'язності. Отримаємо суперечність, оскільки після такого вилучення хроматичне число графа G не зміниться. ◄

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

Різноманітні алгоритми відшукання правильних розфарбувань графів можна знайти у підручниках з теорії графів.

Завдання для самостійної роботи

1. Визначити хроматичне число: (а) повного графа Kn;

(б) повного двочасткового графа Kn,m; (в) довільного двочасткового графа; (г) простого циклу довжиною 2k;

(д) простого циклу довжиною 2k + 1, k N; (е) дерева.

2. Довести, що для правильного розфарбування довільного кубічного графа достатньо чотирьох фарб.

189

3.Чому дорівнює хроматичне число повного графа Kn, з якого вилучено одне ребро?

4.Довести, що граф G біхроматичний тоді й тільки тоді, коли він не містить циклів непарної довжини.

5.Довести, що для довільного планарного графа G викону-

ється нерівність χ(G) ≤ 5.

6.Знайти графи, які мають різні хроматичні числа й у яких: (а) кількість вершин степеня k однакова для всіх k ≥ 0;

(б) кількість простих циклів довжиною l однакова для всіх l; (в) виконуються обидві умови з п. (а) та (б).

7.Знайти всі 2-критичні й 3-критичні графи.

4.10. Обходи графів

Появу теорії графів як розділу математики пов'язують із задачею про кенігсберзькі мости. Сім мостів міста Кенігсберга було розташовано на р. Прегель так, як зображено на рис. 4.11, а (B і C – береги, А та D – острови).

СС

аб

Задача полягає в тім, чи можна, починаючи з будь-якої точки (А, B, C або D), здійснити прогулянку (обхід) через усі мости так, щоб пройти кожен міст тільки один раз і повернутися у вихідну точку.

Оскільки істотними є тільки переходи через мости, то план міста можна зобразити у вигляді графа G (із кратними ребрами), вершинами якого є береги й острови (точки А, В, С і D), а ребрами − мости (рис. 4.11, б). Тоді задачу про кенігсберзькі мости мовою теорії графів можна сформулювати так: чи існує в графі G цикл, який містить усі ребра графа? Інше відоме формулювання проблеми: чи можна накреслити фігуру, що зображає граф G, не відриваючи олівця від паперу й не повторюючи ліній

190