ближені алгоритми показують досить точні результати, було вирішено використовувати саме їх. У програмі реалізовано два наближених алгоритму:
. Неявний перебір;
. Евристичний метод. p> Неявний перебір
Визначимо кожній вершині свій номер (xi - i-я вершина). Отримуємо первісну розмальовку:
. Забарвити xi в колір 1. p>. Кожну з решти вершин фарбувати послідовно: вершина xi забарвлюється в колір з найменшим можливим В«номеромВ» (тобто обираний колір повинен бути першим у даному впорядкування кольором, що не використаним при забарвленні якої-небудь вершини, инцидентной xi). Далі покращуємо розмальовку. Відшукуємо першу за номером вершину з максимальним кольором. З неї робимо крок повернення:
. Знаходимо суміжну вершину з максимальним номером, який менше, ніж у неї. p>. Намагаємося перефарбувати її в колір більший власного, але менший, ніж максимальний колір у графі. p>. Якщо це не вдається, то робиш крок повернення з цієї вершини. p>. Якщо це вдається, то за правилом першої фази перефарбовувати вершини з великим номером. p>. Якщо при перефарбування якась вершина зажадала максимальний колір, від якого ми намагаємося позбутися, то робимо крок повернення з неї. p>. Якщо досягнута перша вершина, то завершуємо роботу. p> Далі покращуємо розмальовку. Відшукуємо першу за номером вершину з максимальним кольором. З неї робимо крок повернення:
. Знаходимо суміжну вершину з максимальним номером, який менше, ніж у неї. p>. Намагаємося перефарбувати її в колір більший власного, але менший, ніж максимальний колір у графі. p>. Якщо це не вдається, то робиш крок повернення з цієї вершини. p>. Якщо це вдається, то за правилом першої фази перефарбовувати вершини з великим номером. p>. Якщо при перефарбування якась вершина зажадала максимальний колір, від якого ми намагаємося позбутися, то робимо крок повернення з неї. p>. Якщо досягнута перша вершина, то завершуємо роботу. p> Евристичний метод
Спочатку вибираємо перший колір.
. Сортуємо вершини за кількістю нефарбованих суміжних вершин. p>. Послідовно офарблюємо вершини у вибраний колір. Якщо у вершини вже є суміжна вершини з вибраний кольором, то залишаємо її неокрашенной. p>. Якщо залишилися незабарвлені вершини, то вибираємо наступний колір і переходимо до пункту 1. p> Теоретичне обгрунтування
Алгоритм неявного перебору в більшості випадку повинен давати правильний рішення, оскільки під час кроку повернення відбувається рух по дереву пошуку в ширину.
Евристичний метод дає прийнятний результат, оскільки спочатку забарвлює вершини з максимальним ступенем.
.2 Розмальовка графа
розмальовки вершин графа називається призначення квітів його вершин. Зазвичай кольору - це числа. Тоді розмальовка є функцією, визначеною на множині вершин графа і приймаючої значення в множині. Розмальовки можна також розглядати як розбиття множини вершин, де - безліч вершин кольору. Безлічі називають ко...
