Алгоритм раскраски графа (точный)

курсовая работа

Алгоритм, использующий метод Магу - Вейссмана

1. Для графа G (Х,U) построим семейство МВУП F={Fj}, где j= 1,... ,1; 1 - число МВУП.

1. 2. Составим матрицу

Cij=

3. Для. каждой вершины графа G =(Х,U) по матрице С находим суммы тех FjF, в которые она входит, и записываем произведение этих сумм.

4. Раскрываем скобки по правилам булевой алгебры и выбираем слагаемое, состоящее из наименьшего числа сомножителей.

Рассмотрим работу описанного алгоритма на примере графа (рис.16).Согласно алгоритму Магу - Вейссмана для поиска семейства МВУП составим произведение

ПG = (X1 +Х2) (Х1+ХЗ) (Х2+ХЗ) (Х2+Х5) (Х2+Х7) (ХЗ+Х5) (ХЗ+Х6) (ХЗ+X7)*

(Х4+Х5) (Х4+Х6) (Х4+Х7) = (Х1+Х2ХЗ)*(Х2+ХЗХ5Х7) (ХЗ+Х5Х6Х7) (Х4++Х5Х6Х7) = (Х1Х2+Х1ХЗХ5Х7+Х2ХЗ+Х2ХЗХ5Х7) (ХЗХ4+ХЗХ5Х6Х7+Х4Х5Х6X7++Х5ХбХ7) =Х1Х2Х3Х4+Х1Х2Х5ХбХ7+Х1Х3Х4Х5X7+Х1Х3Х5Х6Х7+Х2ХЗХ4+

+Х2ХЗХ5Х6Х7. Рi= Х1Х2ХЗХ4 поглощается подмножеством Р5 =Х2ХЗХ4.

Используя условие, что в ПG в качестве сомножителей будут вершины ХРj получаем следующее семейство

МВУП F={F1,F2,F3,F4,F5}: F1=X{X1,X2,X5,X6,X7}={X3,X4}; F2={X2,X6}; F3={X2,X4}; F4={X1,X5,X6,X7}; F5={X1,X4}.

Составляем матрица C

Для каждой вершины Хi Х по матрице С составим суммы тех FjF, в которые оно входит и запишем произведение этих сумм

ПС=(F4+F5)(F2+F3)F1*(F1+F3+F5)F4*(F2+F4)F4=(F2+F3F4)F1F4=F1F2F4+F1F3F4.

Каждое из двух полученных слагаемых содержит в неявном виде все вершины графа G =(Х,U), Таким

образом, для раскраски требуется минимум 3 цвета. Раскроем слагаемые и удалим дублирующие вершины.

В результате получаем два варианта решения:

F1F2F4={ХЗ,Х4;Х2;Х1,Х5,Х6,Х7} или

F1F2F4={ ХЗ,Х4;Х2X6;Х1,Х5,Х7};

F1F3F4={X3;X2,Х4;Х1,Х5,Х6,Х7}

или F1F3F4={XЗ,X4;X2;X1,X5,Xб,X7}.

Первый и последний варианты совпали. Получены три различных варианта минимальной раскраски вершин графа.

Делись добром ;)