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

ПG=(F4+F5)(F2+F3)F1х(F1+F3+F5)F4х(F2+F4)F4=(F2+F3F4)F1F4=F1F2F4 + F1F3F4.

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

Раскроем слагаемые и удалим дублирующие вершины.

В результате получаем два варианта минимальной раскраски вершин графа:

F1F2F4={X3,X4;X2;X1,X5,X6,X7} или F1F2F4={X3,X4;X2,X6;X1,X5,X7};

F1F3F4={X3;X2,X4;X1,X5,X6,X7} или F1F3F4={X3,X4;X2;X1,X5,X6,X7}.

На рисунке приведен первый вариант раскраски:

2.5.2.  Алгоритм раскраски А1.

Данный алгоритм является представителем большой группы эвристических алгоритмов минимальной раскраски и основан на процедуре упорядочения вершин. Идея этой эвристики легко раскрывается в следующем пошаговом описании алгоритма:

1.  Составим упорядоченный список вершин графа по убыванию значений их локальных степеней. Пусть цвет p = 1.

2.  Раскрасим первую неокрашенную вершину xi из упорядоченного списка в цвет p.

3.  Просмотрим все последующие неокрашенные вершины из упорядоченного списка и раскрасим в цвет p те вершины, которые не смежны с xi и между собой.

4.  Удалим окрашенные вершины вместе с инцидентными им ребрами.

5.  Если в упорядоченном списке есть неокрашенные вершины, то увеличим p=p+1 и переходим к п.2.

Пример: Рассмотрим работу алгоритма А1 для графа [14]:

Определяем локальные степени вершин r(xi) :

Xi	X1	X2	X3	X4	X5	X6	X7
r(xi)	2	4	5	3	3	2	3

Упорядоченный список имеет вид :

Xi	X3	X2	X4	X5	X7	X1	X6
r(xi)	5	4	3	3	3	2	2

Выбираем первую неокрашенную вершину - x3 и раскрашиваем в цвет p = 1.

Далее просматриваем список:

-  вершина x2 смежна с x3, пропускаем ее;

-  вершину x4 окрашиваем в цвет p=1;

-  оставшиеся вершины x5,x7,x1 и x6 смежны x2, пропускаем их.

Удаляем вершины x3 и x4 из графа G :

p=p+1 => p=2; Возвращаемся к п.2.

Выбираем вершину x2 и окрашиваем в цвет p=2. В этот же цвет можно окрасить x6. Оставшиеся вершины окрашиваются в цвет p=3.

Таким образом, получаем три цвета и следующую раскраску вершин:

2.5.3. Алгоритм раскраски А2.

Еще одна эффективная эвристика для минимальной раскраски, основанная на последовательном удалении вершин из графа:

1.  Введем счетчик цветов p и положим: р=1.

2.  Определяем локальные степени вершин.

3.  Выбираем вершину xi с максимальной локальной степенью и удаляем еe из графа вместе с инцидентными ребрами.

4.  Если множество ребер U ¹ Æ, то переходим к п.3. В противном случае вершины, которые не удалялись, окрашиваем в цвет p.

5.  Если в графе есть неокрашенные вершины, то p=p+1 и переходим к п.2.

Пример [14]:

Установим p=1. Определяем локальные степени вершин:

Xi	X1	X2	X3	X4	X5	X6	X7
r(xi)	2	4	5	3	3	2	3

Выбираем и удаляем из графа вершину x3, т. к. r(x3)=5 - максимум:

Так как U ¹ Æ, - переходим к п.3.

Выбираем и удаляем вершину x2:

Так как U ¹ Æ , переходим к п.3.

Выбираем и удаляем вершину x4.

Условие U = Æ выполняется, поэтому в цвет p = 1(красный) окрашиваем все неудаленные вершины - X1,X5 ,X6,X7.

Так как в графе имеются неокрашенные вершины, то p=2 и переходим к п.2.

Определяем локальные степени вершин:

Xi	X2	X3	X4
r(xi)	1	1	0

Выбираем и удаляем вершину x2:

Т. к. U = Æ, то в синий цвет р=2 окрашиваем вершины х3 и х4.

Устанавливаем новый (черный) цвет р:=р+1=3.

Осталась одна вершина x2, окрашиваем ее в черный цвет.

Решение задачи по алгоритму А2 выглядит следующим образом:

2.6.  Тема № 6 «Изоморфизм графов». Метод на основе локальных характеристик вершин.

Два графа G(X, U) и H(Y, R) называются изоморфными, когда существует отображение t: X ®Y такое, что для любых вершин xi и xj графа G их образы t (xi ) и t (xj ) смежны в Н тогда и только тогда, когда xi и xj смежны в G.

Математическая запись для обозначения изоморфизма двух графов: G @H.

Из определения изоморфизма двух графов следует, что:

·  Изоморфизм – отношение эквивалентности на множестве графов.

·  Изоморфные орграфы отличаются лишь обозначением вершин.

·  В псевдографах изоморфизм устанавливается с учетом кратности ребер.

·  Для того чтобы два графа были изоморфными необходимо, чтобы количество вершин и ребер у них совпадало, а также было равное количество вершин с одинаковыми степенями.

Ниже приведен пример двух изоморфных графов, для которых отображение t: хi ® y i

Граф G(X, U) Граф H(Y, R)

Метод на основе локальных характеристик вершин

В методе формируются так называемые интегральные характеристики вершин графов, каждая из которых в рамках принятого исходного множества локальных характеристик (ЛК) полностью определяет структуру отношений данной вершины со всеми другими вершинами графа с учетом их локальных и промежуточных интегральных характеристик. Определение изоморфизма графов осуществляется на основе анализа процессов обобщения характеристик, выполняемых одновременно для обоих графов, и сопоставления вершин с одинаковыми интегральными характеристиками.

Для определения отношений между упорядоченной парой вершин (xi, xj) псевдографа G=(X, U) введем следующие обозначения:

-  Eij - число дуг, исходящих из вершины xi и входящих в вершину xj,

причем i¹j;

-  Oij - число ребер, связывающих вершины xi и xj,

-  Zij - число петель при вершине xi.

Обобщенную количественную характеристику отношений между упорядоченной парой вершин (xi, xj) определим следующим образом:

(1)

где q - число десятичных разрядов величины Qij; i, j=1, 2, ..., n.

Матрица S0(G) = ½½ S0ij ½½ называется обобщенной матрицей связности. Каждая i-я строка этой матрицы является ЛХ i-й вершины, определяющей отношения i-й вершины с другими вершинами графа.

Пусть на графе G определена некоторая функция S0(I), значения которой представляют собой числа натурального ряда в интервале 1, 2 ,..., n и кодирует значения совокупности ЛХ вершин множества X. Кодирование осуществляется последовательно по каждой ЛХ таким образом, что вершинам с различными значениями ЛХ присваиваются числа из ряда 1, 2 ,..., n. Процесс кодирования заканчивается, когда все ЛХ будут перебраны или когда все вершины графа получат различные кодовые числа. Таким образом, каждой вершине графа будет поставлено в соответствие некоторое число s0i функции S0(I), а каждой дуге (xi, xj) Î G будет поставлено в соответствие значение s(1)ij, вычисленное по формуле:

s(1)ij = s0ij * 102*w + s0i *10w + s0j, (2)

где w - число десятичных разрядов величины n.

Характеристики s(1)ij дуг графа G записываются в S1(G)= ½½ S(1)ij ½½nxn, эту матрицу назовем характеристической. Вектор-строку s(1)i матрицы S1(G) будем называть характеристическим вектором вершины xi.

Два характеристических вектора s(1)i и s(1)k вершин хi и xk будем считать равными s(1)i = s(1)k, если между их элементами s(1)i и s(1)k можно установить взаимно-однозначное соответствие, т. е справедливо равенство s(1)ij = s(1)kl.

Если в матрице S1(G) имеются совпадающие характеристические векторы, то делается попытка дифференциации соответствующих вершин путем построения матриц S2(G),..., Sf(G).

Каждому вектору S(f)i ставится в соответствие интегральная характеристика s(f)i такая, что при S(f)i = S(f)k, s(f)i = s(f)k. В качестве значений характеристик s(f)i принимаются числа натурального ряда 1,2,...,n (так же, как и при кодировании ЛХ). Элементы sfij матрицы Sf(G) определяются по формуле:

sfij = s0ij * 102*w + s(f-1)i * 10w + s(f-1)j (3)

Построение последовательности матриц заканчивается, если после очередной f-й итерации обобщения мы получили устойчивые характеристические матрицы. Если они не совпадают, то графы не изоморфны. Если совпадают, то тогда возможны следующие варианты:

a)  Матрицы не содержат однородных групп (характеристик с одинаковыми значениями) и множества интегральных характеристик совпадают. В этом случае графы изоморфны и можно установить соответствия между вершинами графов. Вершина xi соответствует вершине yk, если sfi = sfk.

b)  Матрицы содержат однородные группы и являются устойчивыми характеристическими матрицами. При наличии однородных групп выполняются операции по их дифференциации путем введения дополнительной локальной характеристики I* для одной вершины xi из X и последовательно для вершин соответствующей группы в графе H.

Пpоцесс обобщения ЛХ выполняется аналогично рассмотренному ранее. пересчет величин sfij и sfkl по формуле (2) в этом случае можно выполнить лишь для строк, соответствующих вершинам однородной группы. дифференциация вершин оставшихся однородных групп осуществляется аналогично. Если после введения некоторой группы ЛХ дифференциация вершин не происходит, то это означает, что имеет место несвязная однородная группа, которая состоит из нейтральных вершин, либо она связана с нейтральными вершинами. Соответствия вершин xi и yk данных групп могут выбираться произвольно.

Описание алгоритма

1.  Создаются обобщенные матрицы связности для каждого графа S0(G) и S0(H) по формуле (1). Каждая i-я строка в матрице S0 является локальной характеристикой i-й вершины, однозначно определяющей ее связность со всеми другими вершинами.

2.  В каждой строке матриц S0(G) и S0(H) выпишем в отдельные множества элементы s0ij и s0kl > 0, соответственно, и внутри каждого множества упорядочиваем элементы по убыванию их значений. Полученные множества обозначим: S(0)i ={s0ij} для i-й строки графа G и S(0)k ={s0kl} для k-й строки графа Н. Считаем, что xi и yk имеют одинаковые ЛХ, если S(0)i = S(0)k. Вершинам xi из X и yk из Y поставим в соответствие значения s(0)i и s(0)k, представляющие собой числа натурального ряда так, что: если S(0)i= S(0)k, то s(0)i = s(0)k. На основе анализа всех ЛХ получим функции S0q(I)={s(0)i} и S0h(I)={s(0)k} .

3.  Проанализируем функции S0q(I) и S0h(I). Возможны следующие результаты:

а) S0q(I) ¹ S0h(I). Вывод: графы не являются изоморфными.

б) S0q(I) = S0h(I). В этом случае возможны два варианта.

Вариант 1: Произошла полная дифференциация вершин, т. е. не существуют xi и xk для которых si =sk (каждой вершине соответствуют различные числа). В этом случае графы изоморфны и можно установить соответствие между вершинами двух графов следующим образом: xi из X соответствует yk из Y, если s(0)i=s(0)k.

Вариант 2: Не достигнута полная дифференциация вершин, т. е. существуют вершины xi и xk из множества X, для которых s(0)i=s(0)k. Переходим к п. 4.

4.  Строим матрицы Sf(G) и Sf(H) по формуле (3). На очередной f-й итерации обобщения характеристик каждому вектору-строке ставится в соответствие значение интегральной характеристики. Создаются функции Sf(I) и Sf(H) по аналогии с функциямиS0(G) и S0(H) (см. п. 2).

5.  Итерация обобщения характеристик осуществляется до получения устойчивой характеристической матрицы, т. е. Sf-1(I)=Sf(I). После чего переходим к п.6 или если Sf-1(I)¹ Sf(I) и не вводилась дополнительная характеристика, то графы не изоморфны и исследование на изоморфность прекращается.

6.  Если характеристические матрицы не имеют однородных групп, то графы изоморфны и можно установить соответствие между вершинами таким образом, что xi соответствует yk, если s(f)i = s(f)k. Если не произошло дифференциации вершин, то графы также изоморфны, но для установления соответствия между вершинами необходимо ввести дополнительную характеристику для одной вершины xi Î X из однородной группы графа G и последовательно для вершин yk Î Y графа H соответствующей группы. Процесс обобщения после введения дополнительной характеристики выполняется аналогично рассмотренному ранее методу обобщения. Пересчет Sf*i и Sf*k по формуле (3) можно выполнить лишь для строк, соответствующих вершинам однородных групп. Дифференциация вершин оставшихся однородных групп осуществляется аналогично. Если после введения дополнительной характеристики дифференциации вершин не произошло, то устанавливаем произвольное соответствие между вершинами данной однородной группы.

Пример [14]: Даны два графа G и H.

Граф G	Граф Н

В таблице 1 представлены результаты работы алгоритма – обобщенные матрицы связности для трех итераций, выполненных для дифференциации вершин. Рассмотрим поэтапно построение этой таблицы.

Шаг 0.

Составим обобщенные матрицы связности S0(G) и S0(H) по формуле (1).

Разбиваем вершины на две группы:

·  для графа G {x0,x2,x3,x4,x6,x7} -> s(0)i = 1 и {x1,x5} -> s(0)i = 2,

·  для графа H {y1,y2,y3,y5,y6,y7} -> s(0)k = 1 и {y0,y4} -> s(0)k = 2.

Функции S0g (I)=(1,2,1,1,1,2,1,1) и S0h (I)=(2,1,1,1,2,1,1,1) совпадают, но они не привели к полной дифференциации вершин, так как есть вершины с совпадающими характеристиками.

Шаг 1.

Продолжаем процесс обобщения, но уже по формуле (2). Вторая итерация также не привела к полной дифференциации вершин. Получены S1i (I) = (1,2,1,3,4,2,3,5) и

S1k (I) = (2,5,1,1,2,3,4,3). Так как S1i (I) = S1k (I), то продолжаем процесс обобщения.

Шаг 2.

После третьей итерации получили устойчивую характеристическую матрицу, причем все значения в S2 (I) различны. Сравнивая две функции S2i (I) и S2k (I), получаем таблицу соответствия между вершинами двух графов :

Граф G	0	1	2	3	4	5	6	7
Граф H	2	0	3	7	6	4	5	1

Обобщенные матрицы связности для графов G (слева) и H (справа) для шагов итераций f = 0, 1, 2

Табл. 1

f=0

i\ j	0	1	2	3	4	5	6	7	S0 i		k\ j	0	1	2	3	4	5	6	7	S0 k
0					10	1		10	1		0	1	10	10	1	2				2
1	10	1	1			2		10	2		1				10		10		1	1
2	10	1		10					1		2		10			1		10		1
3					10	10		1	1		3	1		10					10	1
4		10				10	1		1		4	2		1	10	1	10			2
5	1	2	10			1	10		2		5	10						1	10	1
6		10		10	1				1		6	10				10	1			1
7			10	1			10		1		7		1			10		10		1
f=1									S1 i											S1 k
0					1011	112		1011	1		0	122	1021	1021	121	122				2
1	1021	122	121			222		1021	2		1				1021		1011		111	5
2	1011	112		1011					1		2		1011			112		1011		1
3					1011	1012		111	3		3	112		1011					1011	1
4		1012				1012	111		4		4	222		121	1021	122	1021			2
5	121	222	1021			122	1021		2		5	1012						111	1011	3
6		1012		1011	111				3		6	1012				1012	111			4
7			1011	111			1011		5		7		111			1012		1011		3
f=2									S2 i											S2 k
0					1014	112		1015	1		0	122	1025	1021	121	222				2
1	1021	122	121			222		1025	2		1				1051		1053		153	8
2	1011	112		1013					3		2		1015			112		1014		1
3					1034	1032		135	4		3	112		1011					1013	3
4		1042				1042	143		5		4	222		121	1021	122	1023			6
5	121	222	1021			122	1023		6		5	1032						134	1033	7
6		1032		1033	134				7		6	1042				1042	143			5
7			1051	153			1053		8		7		135			1032		1034		4

2.7. Тема № 7 «Транспортная задача»