увати ту компоненту двокольорового графа , яка містить вершину ;
. забарвити вершину в колір ;
. кінець
. іначеначало
15. ;
. забарвити вершину в колір ;
. кінець
. кінець
. кінець циклу;
кінець
Пояснимо деякі терміни, які зустрічаються в алгоритмі:
Двоцвітна ланцюг - це ланцюг графаG, яка пофарбована тільки в два кольори. Двоцвітна компонента - це подграф графа G, який пофарбований тільки в два кольори. p align="justify"> Розглянемо роботу даного алгоритму на прикладі.
Основні позначення:
Вершини -
Кольори -
m - найменший номер кольору, відсутнього на вершинах, суміжних з вершиною
В
Малюнок 2
1 крок:
j = 1;
i = 1;
m = 1;
Перевіряємо умову . Воно виконується, тому ми офарблюємо вершину в колір .
Переходимо на наступну вершину.
крок:
j = 1;
i = 2;
m = 1;
Перевіряємо умову . Воно виконується, тому ми офарблюємо вершину в колір .
Переходимо на 3-ю вершину.
крок:
j = 1;
i = 3;
m = 2;
Перевіряємо умову : . Воно не виконується. Запишемо безліч цветовK = { }. Це безліч складається з одного кольору, тобто, у нас немає пари . Тому ми дану вершину офарблюємо в мінімальний вільний колір, відсутній на сусідніх вершинах, :
В
Малюнок 3
крок:
j = 2;
i = 4;
m = 3;
Переві...
