Конспект_лекций_по_курсу_Дискретная_математика

x2	x3 x2		x3	x2

x1

x4

G = X, Г

x1

x4

x1

x4

H = X,

GA = A, ГA

Рис. 2.5

2.4. Связность

2.4.1. Определения

Пусть G(X) - неограф.

Говорят, что вершины xi и xj связаны, если существует цепь S(xi, xj), соеди-

няющая эти вершины.

Граф G(X) называется связным, если любая пара его вершин связана.

Нетрудно убедиться, что отношение связности на множестве вершин графа рефлексивно, симметрично и транзитивно, следовательно, оно является отношени-

ем эквивалентности. Это отношение позволяет разбить множество вершин графа X

на классы эквивалентности Xi так, что все вершины, входящие в один и тот же класс связаны между собой, а вершины из разных классов между собой не связа-

ны.

Подграф G(Xi) графа G(X) называется связной компонентой графа G(X).

Объединение всех связных компонент графа совпадает с самим графом, пере-

сечение разных связных компонент одного и того же графа пусто.

Пусть G X, Г орграф. Он связен, если связен соотнесенный неограф, полу-

чающийся из графа G(X, Г) заменой всех его дуг звеньями.

Орграф G(X, Г) называется сильно связным, если для любых двух его вер-

шин xi и xj (i j) существует путь из вершины xi в вершину xj.

Сильно связный граф всегда связен. Обратное утверждение в общем случае неверно.

-41-

Пример 2.9. На рис. 2.6 граф G1 связен и сильно связен, граф G2 связен, но не сильно связен.

x2			x2
G1			G2
x1	x3	x1	x3
	Рис. 2.6

Сильно связный подграф G' графа G называется максимальным сильно связ-

ным подграфом, если не существует другого сильно связного подграфа, строго со-

держащего в себе G'.

2.4.2. Алгоритм выделения максимальных сильно связных подграфов (алгоритм Мальгранжа)

Введем следующие обозначения:

ˆ xi xi 2 xi 3 xi ... n xi ... множество вершин графа, достижимых из вершины xi каким-либо путем (множество достижимости вершины xi),

ˆ 1xi 1xi 2 xi 3 xi ... n xi ... – множество вершин графа, из которых можно попасть в вершину xi каким-либо путем (множество обратной достижимости вершины xi).

С(xi) - множество вершин максимального сильно связного подграфа, содер-

жащего вершину xi.

В соответствии с определением максимального сильно связного подграфа

C(xi) содержит саму вершину xi и множество вершин, в которые можно попасть из вершины xi и вернуться обратно. Последнее множество представляет собой пере-

сечение множеств достижимости и обратной достижимости вершины xi. Таким образом,

ˆ	ˆ	1	xi )
C(xi ) {xi } ( xi				(2.1)

-42-

Множества ˆ xi и ˆ 1xi легко найти по матрице смежности графа. Для этого справа от матрицы смежности строят столбец, в котором указывается расстояние от выбранной вершины до всех остальных вершин графа. Вершины, которые нель-

зя достичь из выбранной вершины, помечаются крестиком (х). Около самой вы-

бранной вершины в столбце ставится 0. Множество вершин, которым в этом столбце соответствуют цифры, образуют множество достижимости выбранной вершины.

Затем под матрицей строят строку, в которой выписываются расстояния до выбранной вершины из всех остальных вершин. Вершины, из которых нельзя по-

пасть в выбранную вершину, помечают крестиком. Выбранной вершине ставится в соответствие 0. Множество вершин, которым в построенной строке соответствуют цифры, представляет собой множество обратной достижимости выбранной вер-

шины.

Затем по формуле (2.1) находят множество вершин максимального сильно связного подграфа, содержащего выбранную вершину. Если нужно найти все мак-

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

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

цедура повторяется до тех пор, пока в матрице больше не останется элементов.

Пример 2.10. В графе G = X, Г , заданном матрицей смежности M(G), найти все максимальные сильно связные подграфы. Для сокращения записи у строк и столбцов матрицы проставим не полные обозначения вершин, а только их номера.

-43-

	1	2	3	4	5	6	7	8	9	10
	0 0 0			0	0	0	1	0	0	0 1
	0 1 1			0	0	0	0	0	0	0	2
	0 0 1			0	0	0	0	0	1	0 3
	0 0 1			1	0	0	0	0	0	0	4
M (G)	0 0 0			0	0	0	0	0	0	1	5
	0 0 0			0	1	1	0	0	0	0	6
	0 0 0			0	0	0	0	1	0	0	7
	1 0 0			0	0	0	0	0	1	0 8
	0 1 0			0	0	0	1	0	0	1 9
	0 0 0			0	0	1	0	0	0	0 10

Является ли этот граф сильно связным?

Решение. Воспользуемся для решения задачи алгоритмом Мальгранжа.

Выберем произвольную вершину, например, x1, и, используя M(G), найдем множества достижимости и обратной достижимости этой вершины x1 и ˆ 1x1 .

Элементы первого множества выделим цифрами в дополнительном столбце справа от матрицы смежности, а элементы второго множества – в дополнительной строке под матрицей. Эти цифры означают расстояние от x1 до вершины xi (i = 2, 3, ...,10)

впервом случае и расстояние от xi до x1 во втором. Вершины, не достижимые из x1

вграфе G (или G 1), отметим крестиками в дополнительном столбце (или в допол-

нительной строке).

-44-

	1			2	3	4	5	6	7	8	9	10
	0 0 0					0	0	0	1	0	0	0 1
																0
	0 1 1					0	0	0	0	0	0	0			2	4
	0 0 1					0	0	0	0	0	1	0 3				5
	0 0 1					1	0	0	0	0	0	0			4
M (G)	0 0 0					0	0	0	0	0	0	1			5	6
	0 0 0					0	1	1	0	0	0	0			6	5
	0 0 0					0	0	0	0	1	0	0			7	1
	1 0 0					0	0	0	0	0	1	0 8				2
	0 1 0					0	0	0	1	0	0	1 9				3
	0 0 0					0	0	1	0	0	0	0 10				4
	0			5	4	5			2	1	3

Выпишем в явном виде множество вершин, достижимых из вершины x1

ˆ x1 {x2 , x3, x5 , x6 , x7 , x8 , x9 , x10},

и множество обратной достижимости этой вершины:

ˆ 1x1 {x2 , x3, x4 , x7 , x8 , x9}.

Множество вершин максимального сильно связного подграфа, содержащего вершину x1, C(x1) {x1} ( ˆ x1 ˆ 1x1) {x1, x2 , x3, x7 , x8 , x9}.

Так как это множество включает в себя не все вершины графа G, то граф G не является сильно связным.

Матрица смежности полученного подграфа получается из элементов исход-

ной матрицы, стоящих на пересечении столбцов с номерами 1, 2, 3, 7, 8, 9 и строк с теми же номерами:

1	2	3	7	8	9
0	0	0	1	0	0 1
0 1		1	0	0	0	2
0 0 1			0	0	1 3
M [C(x1)] 0 0 0 0				1	0	7
1	0	0	0	0	1	8
0 1		0	1	0	0 9

-45-

Постройте с помощью этой матрицы соответствующий подграф и убедитесь,

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

Вычеркнем из матрицы M(G) строки и столбцы, соответствующие элементам множества C(x1). В результате получим матрицу М1 подграфа графа G, определен-

ного на всех вершинах исходного графа, не вошедших в C(x1):

		4	5	6	10
		1	0	0	0 4
		0	0	0	1 5
	M
	1
		0	1	1	0 6
		0	0	1	0 10

В полученном подграфе выберем произвольную вершину, например, x4, и

произведем операции, аналогичные описанным выше.

		4		5	6	10
		1		0	0	0 4
								0
		0		0	0	1 5
M	1
		0		1	1	0 6
		0		0	1	0 10
		0

В результате имеем C(x4)= {x4}, т.е. этот максимальный сильно связный под-

граф содержит всего одну вершину x4 с петлей в этой вершине. Его матрица смеж-

ности содержит всего один элемент

M[С(x4)] = [1].

Вычеркнем из М1 строку и столбец, соответствующие вершине x4; получим матрицу М2, с которой выполним описанные выше операции, выбрав для этого вершину x5:

		5		6	10
		0		0	1 5
							0
M	2	1		1	0 6		2
		0			0 10
				1			1
		0		1	2

-46-

Нетрудно видеть, что из вершины x5 можно попасть в любую из оставшихся вершин и вернуться обратно, т.е. подграф, определяемый матрицей М2, сильно связен, C(x5) = {x5, x6, x10} и М[C(x5)] = М2.

Итак, граф G имеет три максимальных сильно связных подграфа, определяе-

мых матрицами M[C(x1)], M[С(x4)] и М[C(x5)].

Упражнение. Дайте графическое изображение графа G и всех трех найденных подграфов, сопоставьте эти изображения между собой. Чем отличается исходный граф G от объединения его максимальных сильно связных подграфов?

2.5.Деревья

2.5.1.Определение и свойства деревьев

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

Лесом называется граф без циклов, все связные компоненты которого явля-

ются деревьями.

Дерево, построенное на n вершинах, обладает следующими свойствами:

1)оно содержит n 1 ребро;

2)добавление к дереву любого ребра между существующими вершинами приводит к образованию цикла;

3)удаление из дерева любого ребра приводит к потере связности;

4)любые две вершины дерева связаны между собой цепью и притом только

одной.

Пусть G(X) – произвольный связный неограф. Можно доказать, что такой граф всегда содержит в себе частичный граф, являющийся деревом. Такое дерево называется покрывающим деревом или каркасом графа G(X).

2.5.2. Задача о минимальном каркасе

Пусть G(X) – связный неограф с нагруженными ребрами (т.е. с ребрами, кото-

рым поставлены в соответствие некоторые меры). Необходимо построить каркас

-47-

этого графа T(X), такой, чтобы сумма мер, приписанных его ребрам, была мини-

мально возможной.

Такая задача называется задачей о минимальном каркасе.

Эта задача имеет наглядную содержательную интерпретацию: если граф G(X)

описывает сеть дорог, которые можно построить между городами, представляе-

мыми множеством вершин X, и мера (xi, xj) представляет собой стоимость строи-

тельства дороги, напрямую связывающей города xi и xj, то решение задачи о ми-

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

ных затратах на строительство.

Алгоритм решения задачи:

1) выбрать в графе ребро, имеющее минимальную меру (если таких ребер не-

сколько, взять любое из них); 2) выбрать из оставшихся ребер ребро, имеющее минимальную меру, так,

чтобы добавление этого ребра не приводило к образованию цикла (если при до-

бавлении такого ребра образуется цикл, то берется следующее минимальное по мере ребро);

3) повторять шаг 2 до тех пор, пока не будет построен каркас графа.

Из свойств деревьев следует, что построение завершается за n 1 шаг, где n –

количество вершин графа.

Пример 2.11. В графе G = X, Г , заданном матрицей мер M (G), найти мини-

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

Здесь и в дальнейшем знак " " в матрице означает отсутствие ребра. Так как граф

G является неографом, то его матрица симметрична относительно главной диаго-

нали, и для его представления достаточно изобразить только часть матрицы, рас-

положенную над диагональю.

-48-

		1	2	3	4	5	6	7	8	9	10
			7 11 2 14 5 6						9		7 1
			3 15			4 12
											3		2
				7 3 14 1 3 6							8		3
							5	2	11	8	1		4
	(G)						3	9	12	4	2		5
M μ
								3	1	17	3		6
									2		2		7
										3			8
													9
											10

Решение. Прежде всего необходимо убедиться, что этот граф связен. Для это-

го можно воспользоваться алгоритмом, аналогичным алгоритму Мальгранжа, с

учетом того, что здесь достаточно найти множество достижимости любой верши-

ны. Если это множество содержит в себе все остальные вершины графа, то он свя-

зен (выполните эту проверку самостоятельно).

Так как в этом графе имеется 10 вершин, то построение минимального карка-

са осуществляется за 9 шагов.

Выберем в графе ребра, имеющие минимальную меру. Это ребра (x3, x7), (x4, x10) и (x6, x8) с мерой, равной 1. Нетрудно видеть, что они не образуют цикла и поэтому войдут в состав минимального каркаса (см. рис. 2.7). Далее будем после-

довательно добавлять к уже построенному частичному подграфу ребра, имеющие следующую по величине меру, равную 2: это ребра (x1, x4), (x4, x7), (x5, x10) и (x7, x8). В графе имеется еще одно ребро, имеющее меру 2 – это (x7, x10), но его добавление приводит к образованию цикла (x7 – x10 – x4 – x7), поэтому переходим к выбору ре-

бер следующей по величине меры 3, таких ребер 8. Начнем с ребра (x2, x3). Добавление ребер (x2, x10), (x3, x5), (x3, x8), (x5, x6), (x6, x7) и (x6, x10) приводит к образованию цикла (убедитесь в этом самостоятельно), а вот добавление ребра (x8, x9) к об-

разованию цикла не приводит. Добавим это ребро. Получим каркас, изображенный на рис. 2.7. Его суммарная мера равна 17. В этом графе имеются еще каркасы с та-

кой же мерой (найдите их самостоятельно).

-49-

3	x3	x4
x2
2		2
x1		x5
1	2
	1	x6
x10	1
3		x7
x9	2
	x8

Рис. 2.7

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

Алгоритм Форда Существуют два варианта этого алгоритма, один из которых используется для

поиска кратчайшего пути, а другой – длиннейшего пути между двумя заданными вершинами.

В обоих случаях процесс поиска состоит из трех этапов. На первом этапе производится присвоение вершинам графа некоторых индексов (индекс, присваи-

ваемый вершине хi, будем в дальнейшем обозначать i). На втором этапе, который состоит из нескольких шагов, эти индексы изменяются по определенным прави-

лам, пока выполняется некоторое условие. В конце второго этапа значения индек-

сов стабилизируются. На третьем этапе строится искомый путь.

Рассмотрим эту процедуру сначала для поиска кратчайшего пути в графе с

нагруженными ребрами. Обозначим начальную вершину x0, а конечную xn.

1-й этап. Вершине x0 присваивается индекс 0 =0, а остальным вершинам xi

(i 0) присваиваются индексы i = .

2-й этап. Ищется дуга (xi, xj), для которой разность между конечным и началь-

ным индексом больше меры этой дуги:
j i > (xi, xj)	(2.2)
	-50-