Page 72 - 4496

1. Виберемо вершину й привласнимо їй першу фарбу.
2. Виберемо з 2-околу цієї вершини будь-яку вершину
й привласнимо їй ту ж фарбу. Об'єднаємо ці дві вершини в
одну так, що всі ребра, що зв'язують не розфарбовані вершини
із цими вершинами, заміняються ребрами до цієї об'єднаної
вершини.
3. Для отриманого графа знаходимо нову
нерозфарбовану вершину з 2-околу, якщо така є, красимо її в
ту ж фарбу й поєднуємо з об'єднаною вершиною.
4. Пункти 2 і 3 виконуються доти, поки існують
нерозфарбовані вершини в 2 - околі об'єднаної вершини.
5. Потім із числа нерозфарбованих вершин
вибирається нова вершина й для неї процедура розфарбування
повторюється, і так доти, поки всі вершини не будуть
розфарбовані.
Алгоритм досить просто реалізується, якщо граф
представлений у вигляді матриці суміжності, однак наведені
приклади, коли розв'язок має не мінімальну кількість фарб.
Алгоритм А.П. Єршова ставиться до так званих евристичних
алгоритмів, побудованих на основі деяких розумних з погляду
здорового глузду методах, для яких гарантій оптимальності
немає. В алгоритмі Єршова виходять із того, що потрібно в ту
саму фарбу пофарбувати якнайбільше вершин. Для цього
пропонується вибирати наступну вершину для розфарбування
на мінімально можливій відстані від уже пофарбованих у ту ж
фарбу вершин, щоб забезпечити більше простору наступним
крокам вибору.
Якщо хроматичне число графа дорівнює двом, граф
називається біхроматичним. У таких графах усі вершини
діляться на дві непересічні підмножини А1 і А2, у кожній з
яких елементи не пов'язані між собою. Такі графи називають
ще двочастковими й позначаються як G=<A1,A2,U>, де А1
А2=, U A1x A2.
До завдань про двочасткових графів зводиться велика
кількість завдань, названих завданнями про призначення. До
них ставляться завдання:
 розподілу безлічі завдань по процесорах у
багатопроцесорній системі;
 розподілу деталей по обробних центрах у гнучких
автоматизованих системах;
69