Читайте также:
|
|
Поскольку при любой допустимой раскраске графа G множество вершин, окрашиваемых в один и тот же цвет, должно быть независимым множеством, то всякую допустимую раскраску можно интерпретировать как разбиение всех вершин графа G на такие независимые множества. Далее, если каждое независимое множество расширить до максимального (путем добавления к нему других вершин), то раскраска графа G может быть тогда истолкована как покрытие вершин графа G максимальными независимыми множествами. Очевидно, что в последнем случае некоторые вершины графа G могут принадлежать более чем одному максимальному независимому множеству. Это говорит о возможности существования различных допустимых раскрасок (использующих одно и то же число цветов), так как вершину, принадлежащую разным максимальным множествам, можно окрасить в любой из цветов, соответствующих тем максимальным независимым множествам, которым она принадлежит.
Итак, пусть построены все максимальные независимые множества графа G (пусть таких множеств t), и пусть задана (n×t) матрица M = {mij}, у которой mij=1, если вершина xi принадлежит j-му максимальному независимому множеству, и mij=0 в противном случае. Если теперь каждому максимальному независимому множеству сопоставить единичную стоимость, то задача раскраски сведется просто к задаче нахождения наименьшего числа столбцов в матрице М, покрывающих все ее строки х). Каждый столбец из решения этой ЗНП соответствует определенному цвету, который может быть использован для окраски всех вершин максимального независимого множества, представленного этим столбцом.
Приведем пример (рисунок 1):
Рисунок 1
Для данного графа матрица M будет иметь следующий вид (рисунок 2):
Рисунок 2 – матрица графа
Решениями будут являться такие комбинации столбцов, чтобы столбец, состоящий из дизъюнкций соответствующих элементов представлял бы собой столбец из единиц. Например такими множествами будут {4,6,10,14}, {4,6,10,12}, {4,6,10,11}, {4,6,10,8} и {4,6,10,2}.
3.5 Алгоритм, использующий метод Магу – Вейссмана
1. Для графа G (Х,U) построим семейство МВУП F={Fj}, где j= 1,...,1; 1 - число МВУП.
2. Составим матрицу
Cij=
3. Для. каждой вершины графа G =(Х,U) по матрице С находим суммы тех FjÎF, в которые она входит, и записываем произведение этих сумм.
4. Раскрываем скобки по правилам булевой алгебры и выбираем слагаемое, состоящее из наименьшего числа сомножителей.
Рассмотрим работу описанного алгоритма на примере графа. Согласно алгоритму Магу - Вейссмана для поиска семейства МВУП составим произведение
П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 (рисунок 3)
Рисунок 3 – матрица С
Для каждой вершины Хi Î Х по матрице С составим суммы тех FjÎF, в которые оно входит и запишем произведение этих сумм
ПС=(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}.
Первый и последний варианты совпали. Получены три различных варианта минимальной раскраски вершин графа.
Дата добавления: 2015-05-05; просмотров: 22 | Поможем написать вашу работу | Нарушение авторских прав |