31

Пример 9.2. На рисунке 9.2 изображен граф, состоящий из четырех вершин x1 , x2 , x3 , x4 и пяти дуг. Рядом с изображением графа на рисунке изображена матрица инциндентций.

X1	X2	x1x3 x2x1 x2x4 x3x
	x1	1	1	0	0
	x2	0	1	1	1
	x3	1	0	0	1
	x4	0	0	1	0
X4	X3
	рис 9.2.
	Путь и маршрут.
Определение 9.8. Путь из вершины xH				к вершине xK -
последовательность	дуг, начинающаяся		в	вершине xH X ,

заканчивающаяся в вершине xK X , и такая, что конец очередной

дуги является началом следующей.

(xH ,xi1)(xi1,xi2 )(xi2, ,xil )(xik ,xK ) = (xH ,xK ).

Определение 9.9. Элементарный путь - в котором вершины не повторяются.

Определение 9.10: Простой путь - в котором дуги не повторяются.

Определение 9.11. Маршрут - последовательность ребер, составляющих, как и путь цепочку.

Определение 9.12. Длина пути - сумма весов его дуг - для взвешенного графа. Если граф не взвешен, то можно считать веса дуг

= 1.

Определение 9.13. Кратчайшим путем между выделенной парой вершин xH и xK называется путь, имеющий наименьшую длину среди всех возможных путей между этими вершинами.

При построении длиннейшего пути рассматриваются элементарные

или простые длиннейшие пути, длиннейшие пути с заданным числом выполненных циклов.

Определение 9.14. Длиннейший путь между xH и xK - путь,

имеющий наибольшую длину среди всех возможных путей между этими вершинами.

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

1. Вершина	X H получает вес VH = 0, ее номер вводится в массив М
номеров	вершин, изменивших вес. Остальные вершины Xi

получают вес Vi = ∞ и их номера не попадают в массив M.

2. Если массив М пуст, то выделяется пункт 3, иначе выбирается, с исключением из него очередная вершина Xi и пересчитываются веса вершин, принадлежащих исходу G( Xi ) вершины Xi :

X	j	G(X )V	= min V	,V + l	. Если вес V	j	уменьшается, то номер j
		i ( j	( j	i	ij ))

включается с приведением подобных в М. Снова выполняется пункт

2.

3. Если вес Vk = ∞,то делается вывод, что пути из вершины X H к вершине X k нет, иначе выполняется процедура выделения дуг, такая же, как в волновом алгоритме для не взвешенного графа, за исключением того, что разность весов вершин X j и Xi должна быть

равна lij .

4. После выделения дуг строятся кратчайшие пути, длины которых равны Vk .

Пример 9.3.:

		1						5
		X2						X4
1-0=1					3-1=2
0	x							8
			x
						x
XH=X1								x	6-5=1 X6=XK
					5-3=2
											8-6=2
										x
		X3							X5
		3						6

1. Ví =V1 = 0,V2 =V3 =V4 =V5 =V6 = ∞, M = {1}

2. M ≠ 0,i = 1, M = 0, G (X 1 ) = {X 2 , X 3 };V2 = min(∞,0 + 1) = 1; M={2}

V	3	(		)	= 4, M =			{	}
		= min ∞,0 + 4						2,3 ;
2.
		M={3};V4	= (∞,1+5)= 6, M = {3,4};
2.		M ≠ 0,i = 3, M = {4}, g(X 3 )= {X 4 , X5},V4								= min(6,3 + 2)= 5
		{ } 5			(	∞,3 + 4	)	=	{ }
M = 4 ;V			= min						7, M = 4,5 ;
2.		M ≠ 0,i = 4, M = {5},G(X 4 )= {X5 , X 6 },V5								= min(7,5 +1)= 6

M= {5};V6 = min(∞,5 + 4)= 9, M = {5,6}

2.M ≠ 0,i = 5, M = {6},G(X5 )= {X 6 },V6 = min(9,6 + 2)= 8,

M={6};

2. M ≠ 0,i = 6, M = 0,G(6) = 0

3.G −1(X 6 )= {X 4 , X5};VX 6 −VX 5 = 2,l5,6 = 2, VX 6 −VX 4 = 3,l4,6 = 4

G −1(X5 )= {X 3 , X 4 };VX 5 −VX 4 = 1,l4,5 = 1, VX 5 −VX 3 = 3,l5,3 = 4

G −1(X 4 )= {X 2 , X 3};VX 4 −VX 3 = 2,l3,4 = 2, VX 4 −VX 2 = 4,l2,4 = 5

G −1(X 3 )= {X1 , X 2 };VX 3 −VX 2 = 2,l2,3 = 2, VX 3 −VX 1 = 3,l1,3 = 4

G −1(X 2 )= {X1};V2 −V1 = 1,l1 = 1

Построен кратчайший путь (XH,XK) длиной 8:

(XH =X1,X2)(X2,X3)(X3,X4)(X4,X5)(X5,X6 =XK)

Процесс решения можно оформить в виде таблицы:

X X 2		X 3	X 4	X5	X 6	M
0	∞	∞	∞	∞	∞	1
0	1	4	∞	∞	∞	2,3
0	1	3	6	∞	∞	3,4
0	1	3	5	7	∞	4,5
0	1	3	5	6	9	5,6
0	1	3	5	6	8	6
0	1	3	5	6	8	0

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

1.В первом пункте волнового алгоритма нужно присвоить всем вершинам вес 0, тогда автоматически будут строиться длиннейшие пути.

2.Во втором пункте алгоритма VJ = max(Vj ,Vi + lij ).

			1				5						X4
					X2
									x						4
	1														x
																	xx
			x				2
0			2
										xx			1
		xx																		X6=XK
XH=X1															xxx
				xxx
	4														2
						X3		xxx					X5
							4
			1
											X1		X 2	X 3			X 4			X5	X 6	M
							0						0	0	0					0	0	1
							0						1	4	0					0	0	2,3
							0						1	4	6					0	0	3,4
							0						1	4	6					8	0	4,5
							0						1	4	6					8	10	5,6
							0						1	4	6					8	10	6
							0						1	4	6					8	10	0

		VX 6 −VX 5		= l5,6 = 2 (X5 , X 6 )
		VX 6 −VX 4		= l4,6 = 4 (X 4 , X 6 )
	Обратный ход:	VX 4 −VX 3 = l3,4 = 2 (X 3 , X 4 )
		VX 4	−VX 2 = l2,4 = 5 (X 2 , X 4 )
		VX 2	−VX 1	= l1,2 = 1 (X1 , X 2 )
		VX 3	−VX 1 = l1,3 = 4 (X1 , X 3 )

Построены три длиннейшие пути:

1.(X1 , X 2 )(X 2 , X 4 )(X 4 , X 6 )

2.(X1 , X 3 )(X 3 , X 4 )(X 4 , X 6 )

3.(X1 , X 3 )(X 3 , X5 )(X5 , X 6 )

Контрольные задачи.

1.Определить кратчайший путь во взвешенном графе с помощью волнового алгоритма. Граф задан матрицей отношения, элемент матрицы задает вес соответствующей дуги.

1	X1	X2	X3	X4	X5	X6	X7	X8
Xx		2	3	5			4
X2					2		1
X3					3	4
X4						4	2
X5								6
X6								4
X7								4
X8
1	X1	X2	X3	X4	X5	X6	X7	X8
Xx		2	3	3			4
X2					3		4
X3					2	3
X4						1	3
X5								3
X6								2
X7								5
X8
1	X1	X2	X3	X4	X5	X6	X7	X8
Xx		3	4	2			5
X2					1		2
X3					4	3
X4						3	4
X5								6
X6								3
X7								5
X8

2	X1	X2	X3	X4	X5	X6	X7	X8
X1		3	3	2			5
X2					4		2
X3					1	5
X4						1	5
X5								4
X6								2
X7								5
X8
2	X1	X2	X3	X4	X5	X6	X7	X8
X1		4	4	3			2
X2					2		2
X3					3	1
X4						4	2
X5								5
X6								3
X7								4
X8
2	X1	X2	X3	X4	X5	X6	X7	X8
X1		4	3	3			2
X2					2		5
X3					2	2
X4						2	4
X5								5
X6								4
X7								2
X8

Практическая работа №10.

Тема: Компоненты связности графов.

Цель: Изучить способы представления графов, их разновидности и алгоритмы нахождения пути по графу.

		Связность графа.
Определение	10.1.	Вершины	xi	и	x j	слабо	связны,	если
существует путь (xi ,x j ) в графе (G,X).
Определение	10.2.	Вершины	xi	и	x j	сильно	связны,	если
существуют пути	(xi ,x j )	и (x j ,xi ) в графе ( G, X ).
Определение	10.3. Если в графе нет путей из						xi и x j	и нет
обратного пути из x j в xi , то вершины xi				и x j		несвязны.

Для неориентированного графа имеет смысл только понятие сильной связности.

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

Пример 10.1.

x2	x3
x1	x4
x7	x5

x8

x6

компоненты связности:1){x1,x2,x3,x4} ;2){x5,x6,x7} ; 3){x8}

Между компонентами – только слабая связность: есть пути из вершин компоненты 1) в вершины компоненты 2) и 3) , и из вершин компоненты 2) в 3).

Алгоритм построения компонент связности в неориентированном графе.

1.i=0. Все вершины графа не отмечены.

2.i=i+1. Выбираем очередную неотмеченную вершину, отмечаем ее и все связанные с нею вершины значением индекса i с помощью распространения волны отметок по ребрам, идущим от уже отмеченных индексом i вершин.

Таким образом, выделяется i компонента связности. Если есть еще неотмеченные вершины, то выполняется пункт 2, иначе выделение компонент связности закончено.

Пример 10.2.

				X1		X2	X3
						X5	X4
							X6
				X10
							X7
				X9
X1			X3			X8
						X2	X8	3	X4
		1
						2			4
									X5
							X6
X9			X7	X10

1.i=0

2.i=1. Отмечаем индексом i=1 вершину X1 и связанные с ней

вершины X 3 , X 7 и X 9 . Получена первая компонента связности: 1{ X1 , X 3 , X 7 , X 9 }

3.i=2. Отметим индексом i=2 вершину X 2 и вершины X 6 , X10 . Построена вторая компонента связности: 2{ X 2 , X 6 , X10 }

4.i=3. Отмечаются индексом i=3 вершины X 4 и X8 . Построена третья компонента связности: 3{ X 4 , X8 }.

5.i=4. Отмечаются индексом i=4 вершину X5 , которая формирует

четвертую компоненту связности - { X5 }. Циклы.

Определение 10.4. Циклом называется замкнутый маршрут в неориентированном графе. Для ориентированного графа определяется аналогично понятие контур - замкнутый путь.

Пример 10.3. Рассмотрим граф (рис.) в котором каждому ребру присвоен свой номер. В графе можно выделить соответствующее ему число циклов. Для нашего примера циклами Ci являются замкнутые маршруты, образованные ребрами (рис. ): C1={1,2,5,4}, C2={5,6,7}, C3={3,6,2}, C4={1,2,6,7,4} и т.д. Среди этих циклов найдутся такие, которые включают в себя другие циклы. Так, цикл C4 состоит из циклов C1 и C2 , у которых имеется общее ребро 5, не вошедшее в цикл 4. Говорят, что цикл 4 получен линейной комбинацией циклов 1 и 2, т.е. является линейно зависимым от них.

x1

1		3	2			3
x2				x3	1		2
						lll
4					l	lv
	5		6			lV
					4	5 ll	6
x5	7		x4
					а)	7	б)

рис.10.1.

Линейно-зависимым от некоторой совокупности других циклов называется цикл, который можно построить линейной комбинацией циклов в совокупности этих циклов.

Присвоим каждому ребру графа номер j, j=1, m, и сопоставим каждому циклу Сi двоичный m разрядный вектор Vi , компоненты vi j которого определяются следующим образом: vj = 0, если ребро j не входит в цикл Ci , vj = 1, в противном случае.

Тогда линейной комбинацией векторов Vi является результат векторной операции сложения по модулю два этих векторов.

Для рассмотренного выше примера имеет:

Поскольку Vi – отношение принадлежности ребер графа циклу Ci , а Ci – это множество ребер, то в результате применения векторной операции мы получаем совокупность ребер, входящих в циклы, составляющих линейную комбинацию за исключением общих для этих циклов ребер ;на языке теории множеств это означает объединение множеств Ci без их пересечения что соответствует операции «симметрическая разность» для множеств.

J	1	2	3	4	5	6	7
V	1	1	0	1	1	0	0
1
V
	0	0	0	0	1	1	1
2
V	1	1	0	1	1	1
4

В нашем примере общим является ребро 5, которое исключено из цикла

4.

Линейно-независимым от совокупности других циклов называется цикл, который не может быть построен линейной комбинацией этих циклов. Максимальное множество линейно-независимых циклов образует систему независимых циклов; мощность γ этого множества называется

цикломатическим числом.

Алгоритм построения системы независимых циклов графа.

1. Строится произвольный остов графа. В исходном графе отмечаются ребра, не включенные в остов.

2.	Выбирается очередное отмеченное ребро и строится цикл,
	содержащий то ребро и ребра остова. Рассмотренное ребро
	отмечается и если есть еще не отмеченные ребра, то выполняется
	пункт 2, иначе – пункт 3.
3.	По формуле Эйлера γ = m − n + p производится проверка числа
	построенных циклов (для контроля).

X2

X2

X3

X1

X3

X1

1

3

2

X5

X4

X5

X4

X2

X2

X2

1 X1

X3

2

X3

3

X3

X1

X1

1

3

2

X5

X4

X5

X4

X5

X4

1)(X2,X4)(X4,X5)(X5,X1)(X1,X3); 2)(X3,X5)(X5,X1)(X1,X2)(X2,X3); 3)(X3,X4)(X4,X5)(X5,X1)(X1,X2)(X2,X3).

Дерево. Остов.

Определение 10.5. Деревом называется конечный связный граф без циклов. Из свойств отсутствия циклов и связности следует, что у дерева количество компонент связности p=1 и цикломатическое число γ = 0 = m

– n+1, отсюда следует, что m=n-1, т.е. число ребер в дереве на единицу меньше числа вершин. Ниже приведены примеры деревьев.

		1				4
	2		5				7
					2
				1
		4
	2						8
1	3	6			3	6	9
		3

Определение 10.6. Остов – это подграф (частичный), который может быть построен из графа удалением некоторых ребер и который является деревом.

В общем случае для графа можно построить несколько остовов. Для приведенного ниже графа построен один из вариантов возможного построения остова.

	x2	x3	x2
			x3
	x1		x1

x5	x4	x5	x4

Для несвязного графа: мы рассмотрим отдельные его компоненты. Остов такого графа – совокупность его компонент.

Алгоритм построения произвольного остова. 1. Для каждой компоненты i графа выполняем пункты 2 и 3.

2.Строим частичный подграф, содержащий все ni вершины компоненты и не содержащий ребер (0 граф).

3. Если в текущий частичный граф включены уже ni -1 ребер, то остов для компоненты i построен, иначе выбираем очередное ребро компоненты и пытаемся его включить в текущий граф. Если в текущем графе это не приводит к образованию цикла, то включаем ребра, иначе - не включаем. Ребро считаем рассмотренным. Выполняем пункт 3.

Так как цикл не образовался, то все ребра с номерами 1, 2, 3, 4 включены в остов, проверяем: m=n-1 ( 4=5-1 ).

Алгоритм построения минимального остова.

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

Пример 10.4.:

	2
	X
	1
1		1		3
X				X

3 2

X4 X4

РАСКРАСКА ГРАФА.

Раскраска представляет собой маркирование вершин графа таким образом, чтобы у смежных вершин маркеры не совпадали. Вместо красок используются числа 0,1,2…

Условие оптимальности раскрашивания – использование минимального числа красок ϕ - хроматического числа графа.

Определение 10.7. Граф, который можно представить на плоскости, без пересечения его ребер, называется плоским.

Определение 10.8. Конечная грань - это внутренняя область плоскости, ограниченная ребрами в плоском изображении графа. Теорема 10.1. Для плоских графов ϕ ≤ 4 .

Пример 10.5. Рассмотрим граф G, изображенный на рисунке 10.2. и произведем раскраску этого графа.