льоровими класами. Розмальовка називається правильною, якщо кожен кольоровий клас є незалежною безліччю. Інакше кажучи, в правильній розмальовці будь-які дві суміжні вершини повинні мати різні кольори. Завдання про розфарбовування полягає в знаходженні правильної розмальовки даного графа в найменше число кольорів. Це число називається хроматичним числом графа і позначається. p> Приклад:
Правильна розмальовка графа G може виглядати наступним чином:
В
Рисунок 3 - Приклад розмальовки графа
Функцією Гранді називається функція на вершинах графа, що відображає вершини в безліч {1,2, ..., a}, причому якщо вершина xi пофарбована в колір з номером k, то функція Гранді h (xi) = k. Ясно, що для даного графа хроматичної число є єдиним, але функцій Гранді може бути дуже багато. Природно, що знайти хоча б одну функцію Гранді - це означає, знайти одну з можливих найкращих розмальовок (таких розмальовок може бути багато). Зауважимо, що якщо даний граф є повним, тобто будь-які дві вершини є суміжними, то хроматичної число такого графа одно п, де п - число вершин. br/>
.4 Тестовий приклад
Як приклад візьмемо граф представлений на малюнку 1:
Кольори позначимо:
червоний: 1,
зелений: 2,
синій: 3. br/>В
Рисунок 4 - Приклад графа
Неявний перебір
. Розфарбовуємо вершини по порядку в мінімально можливі кольори: 1-червоний, 2 - зелений, 3 - зелений, 4 - червоний, 5 - синій. p>. Вершина номер 5 має максимальний колір (з номером 3). Спробуємо від нього позбутися: робимо крок повернення з вершини 5. p>. Суміжна вершина з максимальним номером, які менше 5 - це 3. Перефарбувати її в колір більший її (2) і менший, ніж максимальний (3) - не можна. Робимо крок повернення з вершини 3. p>. Суміжна вершина з максимальним номером, які менше 3 - це 1. Ми досягли першу вершину і завершуємо алгоритм. p> Евристичний метод
. Сортуємо вершини за ступенем: 1, 3, 2, 4, 5. p>. Офарблюємо в перший колір (червоний). Ми можемо пофарбувати вершини 1. Вершини 2 і 3 забарвити не можна, оскільки вони суміжні з 1. Вершина 4 Не
інідентна, так що може бути пофарбована в червоний. Суміжну з першої вершину 5 забарвити не можна. p align="justify"> 3. Сортуємо вершини за кількістю суміжних нефарбованих вершин: 3, 2, 5. p align="justify">. Вибираємо наступний колір - зелений. Ми можемо забарвити в нього вершини 2 і 3. p align="justify">. Сортуємо вершини за кількістю суміжних нефарбованих вершин: залишається тільки 5. p align="justify">. Вибираємо наступний колір - синій (3). p align="justify">. Офарблюємо последую вершину 5 в синій колір. br/>
2. Постановка завдання
Задача: розробка програми, яка б забезпечила введення графа і його розмальовку. Розмальовка графа - присвоєння кожній вершині графа значення (кольору), так щоб вершини з однаковим значенням перестав були ін...
