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

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

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

C_ij=

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

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 поглощается подмножеством Р₅ =Х2ХЗХ4.

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

МВУП F={F₁,F₂,F₃,F₄,F₅}: F₁=X{X1,X2,X5,X6,X7}={X3,X4}; F₂={X2,X6}; F₃={X2,X4}; F₄={X1,X5,X6,X7}; F₅={X1,X4}.

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

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

П_С=(F₄+F₅)(F₂+F₃)F₁*(F₁+F₃+F₅)F₄*(F₂+F₄)F₄=(F₂+F₃F₄)F₁F₄=F₁F₂F₄+F₁F₃F₄.

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

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

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

F₁F₂F₄={ХЗ,Х4;Х2;Х1,Х5,Х6,Х7} или

F₁F₂F₄={ ХЗ,Х4;Х2X6;Х1,Х5,Х7};

F₁F₃F₄={X3;X2,Х4;Х1,Х5,Х6,Х7}

или F₁F₃F₄={XЗ,X4;X2;X1,X5,Xб,X7}.

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