анцюг - лінія, что поєднує точки І, І вона винна перетнуті цикл C як замкнуту лінію, оскількі один з точок, находится Всередині, а Інша - поза області, обмеженої циклом С . Оскількі граф G плоский, Спільна точка ланцюга и циклу может буті лишь вершина графа. Альо в ціклі С немає жодної вершини кольору 2 або 4, мі дійшлі протіріччя.
Звідсі слідує и лежати в різніх компонентах звязності графа. Аналогічно випадка 1, перефарбуємо компоненту звязності цього графа, что містіть вершину, помінявші кольори 2 і 4 місцямі.
Отримання при цьом розфарбування буде правильним 5-розфарбування графа G - v, при цьом среди суміжніх з v вершин не буде вершини кольору 2. Розфарбувавші v в колір 2, отрімаємо правильне 5-розфарбування графа G .
Теорема доведена. ?
Теорема про Чотири кольори
Теорема Хівуда булу доведена в 1890 р. Понізіті верхню планку для хроматична числа будь-которого планарного графа з 5 до 4, тобто підтвердіті гіпотезу про Чотири кольори, не вдаватися ще почти 90 років. У 1969 р. задача булу звед до РОЗГЛЯДУ кінцевого, но й достатньо великого числа коннкретніх віпадків, пізніше їх число Було скорочено до «Всього лиш» 1482. Нарешті, в 1976 р. К.Аппель и В.Хейкен помощью компьютерної програми розібралі всі ЦІ конкретні випадка (витрати на це примерно 2000 годин роботи потужного на тій годину Комп`ютер). У результате смороду довели Наступний теорему.
Теорема про Чотири кольори
хроматична число будь-которого планарного графа НЕ перевіщує 4.
Доведення цієї теореми стало Першів випадка «комп`ютерний» вирішенню важкої и давно стоявшої суто математичної проблеми. Повторити доведення К.Аппеля и В.Хейкена в рамках даного курсу Неможливо, тому приводимо ее без доведення.
.3 Алгоритми розв`язання задач розфарбування графів
Алгоритм розфарбування графу методом неявного перебору
Робота алгоритму поділяється на две фази.
Во время Першої будується початкова припустима розфарбування графа за Наступний правилом: перша вершина фарбується в перший колір, а далі для кожної вершини вібірається мінімальній за номером колір, такий щоб ніяка Із суміжніх з даною Ранее забарвленіх вершин не мала цього кольору.
Во время Другої фази, если це можливо, виходим кращe розфарбування, что вікорістовує менше число кольорів. На Першому кроці Другої фази відшукується перша за номером вершина, пофарбована у колір, від которого ми Хочемо позбутіся. І з неї здійснюється так звань крок повернення, а самє - в множіні вершин, суміжніх з даною, з меншими, чем у неї, номером знаходімо максимально (он булу пофарбована пізніше за других, нехай це x-а вершина) i намагаємося перефарбуваті ее в Інший допустимих колір з номером більшім за ее власний, но меншим номера Зайве кольору. Если це вдається, то далі за правилом Першої фази перефарбовуються следующие вершини з (х +1) -ої до кінця. Если Жодна з них не потребують кольору, від которого ми позбавляємося, отже ми досяглі оптімальніше розфарбування з меншими кількістю кольорів и зупіняемося або почінаемо роботові за алгоритмом з качана.
А если якась вершина зажадає - здійснімо крок повернення з неї. У ситуации, коли та сама х-а вершини не может буті перефарбована в Інший допустимих колір - відразу ж робимо крок повернення з неї. Алгоритм завершує роботу, если на кроці повернення досягається перша вершина.
Як видно, во время такого перебору вершин здійснюється рух по дереву пошуку в глибино. Незважаючі на ті, что алгоритм переборну, ВІН анітрохі НЕ гірше других відоміх методів и Цілком Ефективний.
.4 Деякі задачі, что зводяться до задачі розфарбування графів
Завдання скаладання Розкладая
Для вирішенню цієї задачі нужно найти хроматична число и оптімальне розфарбування графа. Потрібно Прочитати кілька лекцій декільком групам студентов. Деякі з лекцій НЕ могут Читатье одночасно - например, того, что їх читає одна и тієї ж лектор, або їх треба читати одній и тієї ж групи студентов, або смороду повінні проходити в одному и тому ж Комп'ютерний класі. Потрібно Скласти розклад так, щоб читання всех лекцій зайнять мінімально можливий годину (як «одиниці часу» в даній задачі природно розглядаті одну пару). Перекладемо це Завдання на мову графів. Побудуємо граф G, в якому вершини відповідають лекціям та две Різні вершини суміжні тоді и только тоді, коли відповідні лекції НЕ могут Читатье одночасно. Очевидно, что будь-яка правильне розфарбування графа G візначає допустимих розклад (если при цьом розфарбовуванні Використано k кольорів, то для всякого i =1, 2, ..., < i> k вершини, розфарбовані i -м Кольорах, дають список лекцій, Які треба читати на i -й Парі). І навпаки, будь-який допустимих розклад візначає правильне роз...
