ряємо умову : . Воно не виконується. Запишемо безліч K = { }. Шукаємо пару , таку, що вершини і суміжні < span align = "justify"> і пофарбовані у кольори , що не з'єднані двуцветной ланцюгом. Беремо вершини і і розглянемо цю пару. Вона не з'єднана двуцветной ланцюгом. За алгоритмом, вершину офарблюємо в колір вершини , тобто в . А вершину перефарбовувати в колір .
В
Малюнок 4
5 крок:
j = 2;
i = 5;
m = 3;
Перевіряємо умову : . Воно не виконується. Запишемо безліч . Шукаємо пару , таку, що вершини і суміжні з і пофарбовані у кольори , що не з'єднані двуцветной цепью.Берем вершини і < span align = "justify">, які пофарбовані у кольори і відповідно. Вони з'єднані двуцветной ланцюгом { }. Отже, і вершину окашіваем в колір .
В
Малюнок 5
Граф пофарбований.
Відомо, що даний алгоритм розмальовки вершин графа з перефарбою двоцвітних компонент, застосований для розмальовки вершин графа з максимальним ступенем вершин , гарантує розфарбовування цього графа, за умови, що не містить в якості зв'язкових компонент і простих непарних циклів при .
Істотним недоліком тут є те, що , може бути набагато менше . Зазначимо, однак, що при , зазначений алгоритм дає мінімальну розмальовку .
Дійсно, нехай . Перевірка того, чи є 2-розфарбовуваним, вимагає кроків, де - відповідно число вершин, ребер графа. Якщо - не двочастковий, алгоритм ...
