Задача про чотири фарби. Правильне розфарбування графа
В основу теорії розфарбування графа лягла задача “Про чотири фарби”. Полягала вона в тому, щоб на політико-адміністративній карті розфарбувати країни так, щоб ніякі дві країни, що мають спільний кордон, не були розфарбовані однаковою фарбою, чотирма фарбами. При цьому спільний кордон, який зображений точкою, я не лінією, не враховувався.
Ця задача зводилася до задачі про розфарбування плоского графа: маючи деяку кількість фарб, розфарбувати кожну вершину (грань) так, щоб довільні дві суміжні вершини мали різний колір.
Це одна з перших задач теорії графів. Гіпотезу про чотири фарби вперше було висунуто в 1840р. На лекціях Мьобіуса. Нею займався Де Морган (1850р.). У 1878р. Келей не зміг отримати строгого доведення цієї гіпотези. У 1890р. Хівуд довів суперечність і показав, що необхідно п’ять кольорів.
Надалі вважатимемо, що граф G – плоский, не має кратних ребер і неорієнтований.
Крім розфарбування граней графа існує його реберне і вершинне розфарбування.
Означення 2.4.1. Реберним k-розфарбуванням графа називають присвоєння ребрам графа k різних фарб.
Означення 2.5.2. Граф G(Х,Г) називають правильно реберно розфарбованим k фарбами, якщо кожне його ребро розфарбоване однією з k фарб і з того що два ребра ui і uj є суміжними слідує, що вони розфарбовані різними фарбами.
Означення 2.5.3. Хроматичний індекс або реберне хроматичне число Х’(G) графа G – це мінімальне число k, для якого граф має правильне реберне k-розфарбування.
Теорема Візинга. Якщо G(Х,Г) – простий граф, то або Х’(G)=D, або Х’(G)=D+1, де D - максимальний степінь вершини у графі G (для дводольного графа Х’(G)=D).
Наприклад, у заданого графа максимальний степінь вершини 6, тобто 6 ребер є суміжними і повинні бути розфарбовані різними фарбами, тому менше, ніж 6 фарб неможливо використати для правильного розфарбування. На рисунку наведено один із способів правильного реберного розфарбування заданого графа.
Означення 2.5.4. Граф G(Х,Г) називають правильно вершинно розфарбованим l фарбами, якщо кожна його вершина розфарбована однією з l фарб і якщо з (хi,xj)ÎГ слідує, що хi і xj розфарбовані різними фарбами.
Означення 2.5.5. Граф G(Х,Г) називають р-хроматичним, якщо існує правильне розфарбування вершин графа G р фарбами. Мінімальне з таких р називають хроматичним числом графа.
Дата добавления: 2014-12-22; просмотров: 1370;