розфарбування графа
Розфарбовувати можна як ребра графа, так і вершини. Торкнемося спочатку завдання про розфарбовування вершин. при цьому вважаємо, що граф не орієнтований і не є мультиграфом.
Завдання. Розфарбувати вершини графа так, щоб будь-які дві суміжні вершини були розфарбовані в різні квіти, при цьому число використаних кольорів повинно бути найменшим. Це число називається хроматичним (кольоровим) числом графа, будемо його позначати a = a (G) (якщо G - даний граф). Якщо число k и a. то граф називається k-розфарбовуваним.
Функцією Гранді називається функція на вершинах графа, що відображає вершини в безліч, причому якщо вершина xi забарвлена в колір з номером k. то функція Гранді h (xi) = k.
Ясно, що для даного графа хроматичної число є єдиним, але функцій Гранді може бути дуже багато. Природно, що знайти хоча б одну функцію Гранді - це значить, знайти одну з можливих "найкращих" розмальовок (таких розмальовок може бути багато).
Зауважимо, що якщо даний граф є повним, т. Е. Будь-які дві вершини є суміжними, то хроматичної число такого графа одно п. Де п - число вершин.
Для подальшого знадобиться наступне визначення.
Набір вершин графа називається максимальною незалежною системою (МНС), якщо будь-які дві вершини з цього набору не є суміжними і не можна включити в цей набір іншу вершину, щоб ця умова збереглося. Зауважимо, що знаходження МНС в графі досить просто: беремо довільну вершину, потім знаходимо будь-яку вершину, що не суміжну з нею, потім знаходимо вершину, що не суміжну з відібраними вершинами і т. Д. Природно, що МНС в даному графі може бути багато і вони можуть містити різну кількість вершин.
Перейдемо до опису алгоритму знаходження найкращої розмальовки вершин графа. Нехай маємо граф G. знайдемо в ньому будь-яку МНС, яку позначимо S1. і все вершини, що входять в цю МНС, забарвимо в колір № 1. Далі, видалимо з даного графа всі вершини, що входять в цю МНС (разом з ребрами), і для нового графа знову знайдемо МНС, яку позначимо S2. Ці нові вершини забарвимо в колір № 2, потім видалимо ці вершини з графа разом з відповідними ребрами і знову знаходимо МНС, яку забарвимо в колір № 3, і т. Д. Можна довести, що при будь-якому способі здійснення цієї процедури прийдемо до найкращої розфарбуванні і знайдемо деяку функцію Гранді і хроматичної число даного графа.
Приклад. У графа (рис. 9) є 3 максимально незалежних систем вершин:, і. Ясно, що при будь-якій процедурі знаходження хроматичного числа в цьому графі, отримаємо число 3.
Теорема .Якщо максимальний ступінь вершин в графі дорівнює r. то хроматичної число цього графа не перевищує r + 1. При цьому хроматичної число графа одно r + 1 тільки в двох випадках: по-перше, якщо граф є повним і, по-друге, якщо r = 2 і при цьому даний граф містить контур непарної довжини (такий граф зображений на рис. 10, максимальний ступінь його вершин - 2, а хроматичної число - 3). У всіх інших випадках хроматичної число графа не перевищує максимально вершин.
Примітка. Оцінка хроматичного числа, що дається цією теоремою, є досить грубою. Особливо наочно це виглядає на прикладі дерева (розд. 14), для якого ступінь вершин може бути як завгодно велика, а хроматичної число дорівнює 2.
Розглянуті питання пов'язані з відомою проблемою чотирьох фарб. Для того щоб її сформулювати, нам знадобляться ще кілька визначень.
Граф називається плоским, якщо він намальований на площині, причому будь-які 2 ребра можуть перетинатися тільки в вершині.
Графи називаються ізоморфними. якщо існує така нумерація вершин в цих графах, що вони мають одну і ту ж матрицю суміжності (фактично ізоморфні графи - це однакові графи, які відрізняються тільки іншим зображенням).
Граф називається планарним. якщо він ізоморфний плоскому графу. Таким чином, планарний граф можна зобразити на площині як плоский. На рис. 11 зображені 2 ізоморфних (однакових) графа, причому перший з них планарний, а другий є плоским.
Відзначимо найвідомішу інтерпретацію проблеми про чотирьох фарбах. Нехай є географічна карта. Чи можна, використовуючи тільки 4 фарби, зобразити цю карту так, щоб сусідні країни (що мають спільний кордон) були пофарбовані в різний колір? Зрозуміло, що у відповідному графі вершинами є країни, а суміжними вершинами є сусідні країни. Ясно, що отриманий граф є планарним, і після 1976 р відповідь на це питання є позитивним.
Зауважимо, що в теорії графів ставиться часто питання про реберної розфарбуванні графів. Яку мінімальну кількість квітів (це число іноді називають реберно-хроматичним) потрібно, щоб розфарбувати ребра графа так, що будь-які 2 суміжних ребра (тобто. Е. 2 ребра, що мають спільну вершину) були б пофарбовані в різний колір? Для реберно-хроматичного числа графа справедлива набагато більш точна оцінка, ніж для просто хроматичного числа, а саме, вірна наступна, в якійсь мірі дивовижна, теорема.
Теорема Візінга. Якщо в графі максимальний ступінь вершин дорівнює r. то реберно-хроматичної число одно або r. або r +1.
Зауважимо, що до сих пір немає "хороших" критеріїв для графів, коли ж саме реберно-хроматичної число одно r. а коли r + 1.
Очевидно, що найпростіший алгоритм знаходження реберно-хроматичного числа (і відповідної розмальовки ребер) полягає в наступному: по даним графу будуємо так званий двоїстий граф: ребра графа відповідають вершинам нового (двоїстого) графа, причому, якщо 2 ребра мають загальну вершину, то вони є суміжними і в неоднозначному графі з'єднані ребром. Після цього розфарбовуємо щонайкраще вершини двоїстого графа і, переходячи до "старого" графу, отримуємо (одну з можливих) найкращих ребрових розмальовок графів.
На закінчення відзначимо, що хроматичний індекс часто застосовується при конструюванні різних пристроїв, де дроти, що з'єднуються в одній вершині, повинні (для зручності) мати різні кольори.