Реферат Алгоритм розмальовки графа з перефарбою двоцвітних компонент

Тема: Курсовые обзорные

ведення теореми.

Алгоритм з перефарбою двоцвітних компонент

Задача про мінімальну розфарбуванні графа, як було сказано вище, є NP - важкою [2], тому великий інтерес представляють поліноміальні алгоритми, вирішальні завдання наближено. Одним з таких алгоритмів є алгоритм розмальовки вершин графа з перефарбою двоцвітних компонент [3]. p align="justify"> Основна ідея цього алгоритму полягає в тому, що вершини упорядковуються довільним чином і при розфарбуванні чергової вершини графа G аналізується околиця цієї вершини.

Припустимо, що подграф , породжений вершинами , , ... , пофарбований квітами. Тоді, якщо в околиці відсутній один з квітів, то цей колір приписуємо . В іншому випадку, якщо в околиці вершини не міститься кліка потужності , можлива перефарбування графа , така, що на розмальовку округа буде витрачено менше ніж квітів

Наведемо псевдокод даного алгоритму.

Вхід: Граф G з ПН - впорядкованими вершинами.

Вихід: субоптимального розмальовка вершин.

початок

1. ;

. для від до крок 1 цикл

. початок

4. m: = найменший номер кольору, відсутнього на вершинах, суміжних з вершиною ;

. якщо m <= j то

. забарвити вершину в колір ;

. інакше початок

. К: = безліч квітів, представлених рівно один раз на вершинах, суміжних з вершиною ;