Задача про чотири фарби. Правильне розфарбування графа

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

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

Це одна з перших задач теорії графів. Гіпотезу про чотири фарби вперше було висунуто в 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;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.