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

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

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

C_ij=

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

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

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

П_G = (X₁+Х₂)*(Х₁+Х_З)*(Х₂+Х_З)*(Х₂+Х₅)*(Х₂+Х₇)*(Х_З+Х₅)*(Х_З+Х₆)* *(Х_З+X₇)*(Х₄+Х₅)*(Х₄+Х₆)*(Х₄+Х₇)=(Х₁+Х₂Х_З)*(Х₂+Х_ЗХ₅Х₇)*(Х_З+Х₅Х₆Х₇)* *(Х₄+Х₅Х₆Х₇)=(Х₁Х₂+Х₁Х_ЗХ₅Х₇+Х₂Х_З+Х₂Х_ЗХ₅Х₇)*(Х_ЗХ₄+Х_ЗХ₅Х₆Х₇+ +Х₄Х₅Х₆X₇+Х₅Х_бХ₇)=Х₁Х₂Х₃Х₄+Х₁Х₂Х₅Х_бХ₇+Х₁Х₃Х₄Х₅X₇+Х₁Х₃Х₅Х₆Х₇+Х₂Х_ЗХ₄+Х₂Х_ЗХ₅Х₆Х₇. Р_i= Х₁Х₂Х_ЗХ₄ поглощается подмножеством Р₅ =Х₂Х_ЗХ₄.

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

МВУП F={F₁,F₂,F₃,F₄,F₅}: F₁=X\{X₁,X₂,X₅,X₆,X₇}={X₃,X₄}; F₂={X₂,X₆}; F₃={X₂,X₄}; F₄={X₁,X₅,X₆,X₇}; F₅={X₁,X₄}.

Составляем матрицу C (рисунок 3)

Рисунок 3 – матрица С

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

П_С=(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₄={Х_З,Х₄;Х₂;Х₁,Х₅,Х₆,Х₇} или

F₁F₂F₄={ Х_З,Х₄;Х₂X₆;Х₁,Х₅,Х₇};

F₁F₃F₄={X₃;X₂,Х₄;Х₁,Х₅,Х₆,Х₇}

или F₁F₃F₄={X_З,X₄;X₂;X₁,X₅,X_б,X₇}.

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