Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 6 )

N шага	Список минимальных деревьев	добавляемое ребро	Добавить?	вес ребер
1	{x1 },{x2 },{x3 },{x4 },{x5 }	(х3 ,х5 )	да	2
2	{x1 },{x2 },{x3 ,х5 },{x4 }	(х1 ,х3 )	да	5
3	{x1 ,x3 ,х5 },{x2 },{x4 }	(х1 ,х4 )	да	9
4	{x1 ,x3 ,х4 ,х5},{x2 }	(х1 ,х5 )	нет	9
5	{x1 ,x3 ,х4 ,х5},{x2 }	(х4 ,х5 )	нет	9
6	{x1 ,x3 ,х4 ,х5},{x2 }	(х1 ,х2 )	да	16
	{x1 ,x2 ,х3 ,х4 ,x5 }			16

2.4.  Тема № 4 «Внутренняя и внешняя устойчивость в графе»

Устойчивость в графе может быть вершинная и реберная, внутренняя и внешняя. Большее прикладное значение имеет вершинная внутренняя устойчивость, поэтому далее мы будем рассматривать понятия устойчивости в этом смысле.

Наибольшее внутренне устойчивое подмножество (НВУП) – такое подмножество вершин в графе, которое является самым большим по количеству вершин среди всех ВУП (подмножеств несвязанных между собой вершин) графа.

Мощность (количество вершин) НВУП определяет экстремальное число внутренней устойчивости (неплотности) графа - a 0(G).

Каждое ВУП определяет пустой подграф в графе, т. е. подграф без ребер. Часто в задачах интересуют не пустые, а полные подграфы (ПП). Эти две задачи – задача поиска пустых и задача поиска полных подграфов – являются дополнительными друг к другу. Решая задачу поиска ВУП для графа G(X, U*), который получается из исходного путем замены ребер U на U*=Uполн.\U (Uполн. – множество ребер полного графа на множестве Х), мы получим ПП исходного графа. Поэтому приведенные здесь методы могут быть использованы как для поиска ВУП, та и для поиска ПП.

Наибольший полный подграф (НПП) – наибольший по количеству вершин полный подграф графа. Кликой графа будет любой максимальный ПП, т. е. подграф, который нельзя увеличить за счет других вершин без нарушения свойства полноты.

Количество вершин в НПП определяет экстремальное кликовое число (число плотности) графа – j (G).

Метод Магу-Вейсмана для поиска НВУП

Данный метод основан на булевой алгебре и дает точное решение задачи поиска НВУП, а также обратной к этой задаче – задаче поиска клик в графе. В методе Магу - Вейссмана по матрице инциденций S=||Sij||nxm, где n - число вершин графа, m - число ребер графа G=(X, U) вычисляется произведение Пg :

,

в котором j-й сомножитель представляет собой сумму вершин, инцидентных ребру uj ÎU.

Теорема. Подмножество вершин Fg является внутренне устойчивым тогда и только тогда, когда произведение Пg равно 1 для системы переменных {Xi}, определяемых следующим образом:

Xi = 1, если Xi ÎFg

Xi = 0, если Xi ÏFg.

В полученном произведении раскрывают скобки и для полученной суммы выполняют минимизацию по законам булевой алгебры [9]:

Хi = Xi;

Хi + Хi +...+ Хi = Хi;

Хi + 1 = 1;

Хi * Хi *...* Хi = Хi;

Хi * 1 = Хi.

В полученной минимальной форме записи Пg каждому слагаемому Кg соответствует внутренне устойчивое подмножество Fg = X \ Kg, где Kg - слагаемое из полученного Пg.

Пример: Рассмотрим в качестве примера следующий граф на 7-ми вершинах для нахождения максимальных ВУП (МВУП) [14]:

Используем в качестве сомножителей суммы пар вершин, инцидентных ребрам графа:

Пg = (Х1+Х3)*(Х1+Х5)*(Х1+Х7)*(Х2+Х3)*(Х2+Х4)*(Х4+Х6)*(Х5+Х6)=

(Х1+Х3*Х5*Х7)*(X2+X3*Х4)*(Х6+Х4*Х5)= (Х1*Х2+Х1*Х3*Х4+Х2*Х3*Х5*Х7+Х3*Х4*Х5*Х7)*(Х6+Х4*Х5)=

Х1*Х2*Х6 + Х1*Х2*Х4*Х5 + Х1*Х3*Х4*Х6 + Х1*Х3*Х4*Х5 +

Х2*Х3*Х5*Х6*Х7 +Х3*Х4*Х5*Х7 + X2*X3*X5*X7*X4 +

X3*X4*X5*X7*X6

Последнее выражение состоит из 8-ми слагаемых K1, K2,…, K8 , каждое из которых определяет ВУП в графе. В результате получаем семейство МВУП:

F1=X\K1=Х\{X1,Х2,X6}={X3,X4,X5,X7};

F2={X3,X6,X7};

F3={X2,X5,X7};

F4={X2,X6,X7};

F5={X1,X4};

F6={X1,X6}.

НВУП здесь только одно - F1={X3,X4,X5,X7}.

Следовательно, число внутренней устойчивости графа a 0(G)=4.

Метод Брона-Кербоша для поиска НВУП

Данный метод относится к методам последовательного поиска с возвращением и дает точное решение задачи поиска НВУП. В процессе поиска на некотором k-м этапе все множество вершин разбивают на три подмножества: Sk, Qk+, Qk-, где:

·  Sk - вершины формируемого ВУП;

·  Qk+ - подмножество возможных вершин на включение в Sk+1;

·  Qk - - подмножество вершин, которые использовались для

расширения Sk.

Ветвление в дереве поиска включает в себя выбор вершин Xik ÎQk+ и выполнение следующих преобразований:

Sk+1 = Sk ÈXik

Q(k+1)- = Qk - \ ГXik (1)

Q(k+1)+ = Qk+ \ { ГXik ÈXik }

где ГXik - окрестность вершины Xik (вершины, смежные с Xik).

Из вершин Qk+ в подмножество Sk+1 следует включить вершину, для которой

D (Х*) = min |ГX ÇQk+|, X Î Qk+ (2)

Если |ГХ|= 0, то выбирают любую вершину из Qk+. Возврат в подмножество возникает в том случае, когда

X Î Qk-, ГX ÇQk+= Æ , (3)

т. е. существует вершина Х в подмножестве Qk+, такая, что в ее окрестности нет вершин, принадлежащих подмножеству Qk+ .

При этом возникают следующие преобразования:

Sk = Sk+1 \ Xik+1;

Qk+ = Qk+ \ Xik+1; (4)

Qk - = Qk - È Xik+1.

Необходимым и достаточным условием того, что Sk - НВУП, является выполнение равенства

Qk+ =Qk - = Æ (5)

Алгоритма Брона–Кэрбоша состоит из следующих шагов.

1.  Пусть S0 = Æ; Q0- = Æ; Q0+ = X; k=0.

2.  Выбираем вершину Xik ÎQk+, строим Sk+1, Q(k+1)-, Q(k+1)+. Присвоим k=k+1.

3.  Если выполняется условие (3), то переходим к п.5, иначе - к п.4

4.  Если Qk - = Qk+= Æ, то запоминаем Sk, которое является НВУП, и переходим к п.5. Если Qk+= Æ, Qk- ¹Æ, то переходим к п.5, иначе - к п.2.

Положим k=k-1. Выполняем преобразование (4). Если k=0 и Q0+= Æ, то решение получено; если k=0 и Q0+ ¹Æ, то переходим к п.2 и если k ¹0, переходим к п.3.

Пример: Проиллюстрируем работу алгоритма Брона-Кербоша на том же графе, что и в примере метода Магу-Вейсмана [14].

Сформируем первоначальные подмножества:

S0 =Æ; Q0- = Æ; Q0+={X1,X2,X3,X4,X5,X6,X7}; k=0.

Так как Qk - = Æ, то выбираем любую вершину из Q0+, например Х1; k:=k+1=1.

Построим S1={X1}; Q1- = Æ;

Q1+ = Q0+ \{ ГX1 ÈX1}={X1,X2,X3,X4,X5,X6,X7}\{X3,X5,X7} ÈX1}={X2,X4,X6}.

Проверяем условие (3), Так как Qk - = Æ, то условие не выполняется, переходим к п.4.

Проверяем условие (5). Оно не выполняется, поэтому переходим к п.2.

Выбираем вершину Xi2 ÎQ1+, k=k+1=2; Xi2 = X2.

Cтроим:

S2={X1,X2}; Q2- = Æ; Q2+= Q1+ \{ ГX2 ÈX2}= {X2,X4,X6}\{X3,X4} ÈX2}= {X2,X4,X6}\{X3,X4,X2}={X6}.

Проверяем условие (3). Так как условие не выполняется: Qk- = Æ, то переходим к п.4.

Проверяем условие (5), так как оно не выполняется, то переходим к п.2.

Выбираем вершину Xi3 ÎQ2+; k=k+1=3, Xi3=X6.

Строим:

S3 = {X1,X2,X6}; Q3- = Æ; Q3+ = Q2+ \{ ГX6 ÈX6}= {X6}\{X4,X5, X6} = Æ.

Условие (3) не выполняется, - переходим к п.4. Q3+ =Q3- = Æ.

Запоминаем S3={X1,X2,X6} в F1. Переходим к п.5. k=k-1=2.

Выполняем преобразование (4):

S2=S3\Xi3 = {X1,X2,X6}\{X6}={X1,X2}; Q2+ = Q2+ \ Xik = {X6}\{X6} = Æ; Q2- = Q2- ÈXi3 = {X6}.

Так как k=0, то переходим к п.3.

Проверяем условие (3): Х6 ÎQ2- и ГX2ÇQ2+ = Æ.

Оно выполняется, - переходим к п.5. k=k-1=1.

Выполняем преобразование (4):

S1=S2\Xi2 ={X1,X2}\{X2}; Q1+ = Q1+ \ Xi2 ={X2,X4,X6}\{X2}= {X4,X6}; Q1- = Q1- ÈXi2 = {X2}.

Так как k 0 , то переходим к п.3.

ГX2Ç Q1+ = {X3,X4}Ç {X4,X6}= {X4}.

Q1+ ¹Q1-. Переходим к п.2.

Выбираем вершину Xi2 ÎQ1+, Xi2= {X4}.

Строим новые множества:

S2 =S1 È{X4}={X1}È {X4}={X1,X4}; Q2- = Q1-\ГXik= {X2}\Г{X4}= {X2}\{X2,X6} = Æ; Q2+ = Q1+\{ГXi2Ç Xi2}={X4,X6}\{X2,X4,X6} = Æ; k=2.

Проверяем условие (3). Оно не выполняется, - переходим к п.4. Q2+ = Q2- = Æ.

Подмножество S2={X1,X4} запоминаем в F2.

Переходим к п.5. k=1;

Определяем:

S1=S2\Xi2 = {X1,X4}\{X4}={X1}; Q1- = Q1- ÈXi2= {X4,X2}; Q1+ ={X4,X6}\{X4}={X6}.

Проверяем условие (3):

X4 ÎQ1- и Г{X4}ÇQ1+ = Г{X4}Ç{X6} ={X2,X6}Ç{X6}={X6}; X2 ÎQ1- и Г{X3}ÇQ1+ ={X3,X4}Ç{X6} = Æ.

Оно выполняется, - переходим к п.5.

k=0;

S0=S1\{X1} = Æ; Q0+ = Q0+ \ {Xik}={X2,X3,X4,X5,X6,X7}; Q0- ={X1}.

Выбираем Xik из Q0+ по условию (2).

DX* = Г{X2}Ç Q0+ = {X3,X4}; DX* = Г{X3}Ç Q0+ ={X2}; DX* = Г{X4}Ç Q0+ ={X2,X6}; DX* = Г{X5}Ç Q0+ ={X6}; DX* = Г{X6}Ç Q0+ ={X4,X5}; DX* = Г{X7}Ç Q0+ = { }.

Минимальное значение DX*у вершины Xi0= {X7}.

Строим новые подмножества (1):

S1={X7}; Q1- = Q0- \ Г{X7} = Æ; Q1+ = Q0+ \ { Г{X7} È{X7}}={X2,X3,X4,X5,X6,X7}\{X1 ÈX7}={X2,X3,X4,X5,X6}; k=k+1=1.

Проверяем условие (3).

Оно не выполняется так как Q1- = Æ; Qk+ ¹Æ; k=0.

Переходим к п.2.

Выбираем вершину Xi2 ÎQ1+ по условию (2). Это вершина Х3.

Определяем:

S2=S1 ÈXi2 = {X7,X3}; Q2- = Æ; Q2+ = Q1+ \{ГXi2 ÈXi2}={X2,X3,X4,X5,X6}\{X1,X2, X3}={X4,X5,X6}.

Проверяем условие (3).

Оно не выполняется, - переходим к п.4.

Так как Q2+ ¹Æ, то переходим к п.2.

Выбираем Xi3 из Q2+ по условию (2):

DX* = Г{X4}Ç Q2+ = {X6}; DX* = Г{X5}Ç Q2+ = {X6}; DX* = Г{X6}Ç Q2+ = {X5}.

Можно выбрать любую вершину из подмножества Q2+.

Выбираем Xik ={X4} , тогда:

S3=S2 ÈXi3={X7,X3, X4}; Q3- = Æ; Q3+ = {X4,X5,X6}\{X2,X6,X4}={X5}; k=3.

Проверяем условие (3), так как оно не выполняется, то переходим к п.4.

Q3- = Æ; Q3+ = Æ; k=0, поэтому переходим к п.2.

Выбираем:

Xi4 ÎQ3+; Xi4 ={X5}; S4=S3, Xi4= {X7,X3,X4,X5}; Q4- = Æ; Q4+ = Æ, k=4.

Проверяем условие (3).

Так как Qk-=Æ, то переходим к п.4.

Так как Q4- = Q4+ = Æ, то запоминаем новое ВУП: S4={X7,X3,X4,X5} в F3.

Подобный процесс продолжается до тех пор, пока не будут получены все ВУП графа.

Метод разборки графа для поиска НПП

Рассмотрим еще один алгоритм этой группы, предназначенный для поиска НПП, основанный на операции разборки f(G) обыкновенного графа G=(X, U), определяемый следующим образом:

Gi+1= f(Gi - Xi),

·  f(Gi - Xi) - процедура удаления вершины Xi, имеющей минимальную степень в графе Gi 0 на i-ом шаге разборки;

·  k - такой первый шаг разборки (i=1,2,...,k), на котором Gi+1 = Fn-k,

·  Fn-k - полный подграф с числом вершин (n-k),

·  n - число вершин графа G.

В результате однократного выполнения операции разборки получаем решение задачи определения НПП в первом приближении. Значение плотности (G) исходного графа G в этом случае удовлетворяет неравенству:

(n-k) < j(G) < max S(Xi) + 1,

где S(Xi)- степень вершины Xi, удаляемой на i-м шаге разборки; i-1,2,...,k.

Для получения точного решения задачи определения НПП в графе операцию разборки f(G) последовательно применяем к окрестностям всех вершин, которые удалялись в процессе разборки и степень которых удовлетворяет неравенству при их удалении:

S(Xi) > j (G) – 1.

Для получения всего множества НПП операцию разборки f(G) необходимо применить к окрестностям всех вершин, степень которых S(Xi) в момент удаления их из графа удовлетворяет неравенству:

S(Xi) > j (G) - 1

А для получения множества всех МПП коррекцию необходимо применять для всех удаленных вершин.

Для сокращения числа вершин, к которым применяется операция разборки в процессе коррекции, и исключения повторного получения одинаковых НПП воспользуемся теоремами.

Теорема 1. Если для вершины Хi получены все НПП (МПП), то на шаге коррекции m необходимо исключить ее из окрестности вершин, для которых проводится коррекция.

Теорема 2. Если для вершины Xi на шаге коррекции l (1< l < m) уже получены все НПП, то данная вершина на шаге m может не рассматриваться.

Приближенный алгоритм поиска НПП на основе операции разборки.

1.  k:=1, k-шаг разборки; nk - количество вершин в графе G=(X, U) на k-м шаге разборке. Первоначально nk :=n, X'=X.

2.  Для каждой вершины xi ÎX' определяем значение ее степени S(xI) =|Г xi|, i=1,2,...,nk.

3.  Проверяем условие: S(xi) = n-1, для всех i=1,2,...,nk, определяющее полный подграф. Если условие выполняется, то k:=k-1 и переходим к п.6, в противном случае - к п.4.

4.  Определяем вершину xj ÎX', имеющую минимальное значение степени S(xj). Удаляем xj вместе с инцидентными ей ребрами. X'=X'\{xj}, nk+1 :=nk-1

5.  S(xj):=0. Степень каждой вершины xt ÎГ xj уменьшаем на 1. S(xt):=S(xt)-1; k:=k+1. Переходим к п.3.

6.  Все неудаленные вершины образуют полный подграф Fn-k=(X',U') с числом вершин |X'|=n-k. Плотность j (G)=n-k.

Пример:

Рассмотрим работу алгоритма на примере разборки графа G* - дополнительного к исходному графу G из предыдущего примера [14].

Рис. 1.	Рис. 2.
Граф-дополнение G*(X, U*)	Исходный граф G(X,U)

Процесс разборки данного графа представлен в табл. 1 и на рис. а, б, в.

Процесс удаления вершин из графа заканчивается при условии, что значения степеней неудаленных вершин равны между собой и на единицу меньше числа оставшихся вершин. Все неудаленные вершины образуют первый полный подграф F1={X3,X4,X5,X7} графа G*, который точно соответствует ВУМ графа G. Плотность графа G* равна неплотности графа G, т. е. a 0(G), φ(G*)=4.

Таблица 1.

Вершины графа	X1	X2	X3	X4	X5	X6	X7
Изменение значений степеней	ƒ ¯	4 ƒ ¯	4 3	4 3	4 3	4 3 ‚ ¯	5 4 3

- процедура удаления вершины со степенью равной x из графа

рис. А рис. б рис. в

Для получения всех МПП в графе G* проводим операцию разборки для тех вершин, которые удалялись в процессе первой разборки, т. е. для вершин Х1, Х2, Х6.

Выбираем вершину Х1 и строим подграф G1(рис. г) с множеством вершин X1=Г{X1}È{X1} ={X1,X2,X4,X6} и множеством ребер U1, инцидентным только вершинам из подмножества Х1 и принадлежащим множеству ребер исходного графа G*. Процесс разборки графа G1 представлен в табл.2.

Таблица 2

Вершины графа	X1	X2	X4	X6
Изменение значений степеней	3 2	2	 ¯	2

рис. г рис. д

Получили второй полный подграф F2= {X1, X2, X6}, но значение плотности не изменилось. В процессе разборки графа G1 была удалена вершина Х4, поэтому проводим коррекцию решения для этой вершины и строим подграф G2 на основе подграфа G1 (рис. д). Получаем F3={X1,X2}.

Выбираем следующую вершину для коррекции - Х2. Строим под граф с множеством вершин Х2={X2}ÈГ{X2}={X2,X1,X5,X6,X7}. Согласно теореме 1 вершина Х1 из множества Х2 исключается, так как для нее уже получены все полные подграфы на предыдущем шаге.

Удаляем из полученного подграфа (рис. е) вершину Х5, после чего получаем F4={X2,X6,X7}. Применяем операцию коррекции к вершине Х5 и строим для неё новый подграф на основе подграфа, изображенного на рис. е. Полученный подграф представлен на рис. ж. Получили еще один полный подграф F5={X2,X5,X7}.

рис. е рис. ж

Выбираем последнюю из удаленных в процессе первой разборки вершину - Х6. Строим подграф с множеством вершин X3={X6}ÈГ{X6}= {X6}È{X1,X2,X3,X7}= {X1,X2,X3,X6,X7}. Вершины Х1 и Х2 из рассматриваемого множества Х3 удаляем, так как они уже исследованы. Оставшиеся вершины образуют очередной полный подграф F6={X3,X6,X7} (рис. з). Решение закончено.

рис. з

2.5.  Тема № 5 «Операции над графами». Методы минимальной раскраски вершин.

Раскраской вершин графа G называется разбиение множества вершин X на l непересекающихся подмножеств

X1, X2 ,..., Xl: X = È Xi; Xi Ç Xj = Æ; i, j Î I={1,2,...,l},

таких, что внутри каждого подмножества Xi не должно содержаться смежных вершин (Xi - внутренне устойчивые подмножества).

Если каждому подмножеству Xi поставить в соответствие определенный цвет, то вершины внутри этого подмножества можно раскрасить в один цвет, вершины другого подмножества Xj - в другой цвет и т. д. по всем подмножествам. В этом случае граф называется l-раскрашиваемым. Методы, направленные на использовании минимума цветов для раскраски вершин графа, называются методами минимальной раскраски.

Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом c(G).

2.5.1.  Метод раскраски на основе метода Магу-Вейсмана

1.  Для графа G = (X, U) построим семейство МВУП:

F ={Fj}, где j = 1,...,l; l - число МВУП.

2.  Составим матрицу C =½½Cij½½nxn, где n = ½X½, l=½F½,

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

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

Пример: Рассмотрим работу алгоритма минимальной раскраски вершин для графа [14]:

По методу Магу - Вейссмана для поиска семейства МВУП составим произведение ПG :

ПG = (X1+X2)(X1+X3)(X2+X3)(X2+X5)(X2+X7)(X3+X5)(X3+X6)(X3+X7)х

х(X4+X5)(X4+X6)(X4+X7)=

(X1+X2X3)x(X2+X3X5X7)(X3+X5X6X7)(X4+X5X6X7)=

(X1X2+X1X3X5X7+X2X3+X2X3X5X7) (X3X4+X3X5X6X7+ +X4X5X6X7+X5X6X7)= X1X2X3X4+X1X2X5X6X7+X1X3X4X5X7+X1X3X5X6X7+X2X3X4+X2X3X5X6X7.

P1 = X1X2X3X4 поглощается подмножеством P5 = X2X3X4.

Используя условие, что в ПG в качестве сомножителей будут вершины X\Pj, получаем следующее семейство МВУП:

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:

	F1	F2	F3	F4	F5
X1				1	1
X2		1	1
X3	1
X4	1		1		1
X5				1
X6		1		1
X7				1

Для каждой вершины Xi Î X по матрице C составим суммы тех Fj Î F, в которые оно входит, и запишем произведение этих сумм: