Информатика конспект лекций_2012

Пример 4. 1. Последовательность v1x2v2x3v4x4v3 – маршрут, соединяющий вершины v1, v3 в графе G (см. пример 2).

2.Последовательность v1x2v2x3v2x4v3 – путь из v1 в v3 в ориентированном псевдографе D (см. пример 1).

Замечание 3. Последовательность v1х1v2х2v3... хkvk+1 можно однозначно восстановить по последовательности х1...хk, а следовательно, вместо нее можно использовать более короткую запись х1...хk. Отметим далее, что в случае, когда в последовательности v1х1v2х2v3... хkvk+1

–х1,…,хk имеют кратности, равные 1, ее можно однозначно восстановить по последовательности вершин v1...vk+1, а следовательно, вместо нее также можно использовать более короткую запись v1...vk+1. В общем случае вместо последовательности v1х1v2х2v3... хkvk+1 можно использовать сокращенную последовательность, в которой опущены

все xi кратности 1.

Пример 5. 1. Последовательности х1х3х4, v1v2v4v3 – сокращенные записи маршрута, приведенного в примере 4, п. 1.

2.Последовательности х2х3х4, v1x2v2v2v3 – сокращенные записи пути, приведенного в примере 4, п. 2.

Пусть х1х2…хk – маршрут в графе G (см. замечание 3) и для некоторой последовательности номеров i1,...,ir, где r≥1, 1≤ i1 < i2<...< ir ≤ k,

xi1,xi2...xir снова является маршрутом в графе G. Тогда xi1,xi2...xir называется подмаршрутом маршрут та x1x2...xk. При этом будем говорить, что маршрут xi1,xi2...xir выделен из маршрута x1x2...xk. Аналогично определяется подпуть, выделенный из пути орграфа. Число ребер (дуг) в маршруте (пути) называется длиной маршрута (пути).

Маршрут (путь) v1х1v2х2v3... хkvk+1 называется замкнутым, если его начальная вершина совпадает с конечной, т. е. если v1 = vk+1.

Замечание 4. Далее всюду при подсчете числа вхождения вершин в замкнутый маршрут (путь) начальную и конечную вершины будем считать за одно вхождение этой вершины в маршрут (путь).

Замечание 5. При замкнутом маршруте (пути) x1x2...xk обычно считается, что последовательности x1x2...xk, x2x3...xkx1,..., xkx1x2...xk-1 – различные записи одного и того же маршрута (пути). Незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется цепью. Цепь, в которой все вершины попарно различны, назы-

вается простой цепью.

Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром). Цикл (контур), в котором все вершины попарно различны (см. замечание 4), называется про-

стым.

40

Пример 6. Рассмотрим граф G из примера 2. Тогда:

1)v1x1v2x3v4x4v3 – маршрут длины 3, соединяющий v1, v3; это простая цепь, так как все ребра и вершины попарно различны;

2)v2x2v3x4v4x3v2 – замкнутый маршрут длины 3; это простой цикл, так как все ребра и вершины попарно различны;

3)v1x1v2x2v3x4v4x3v2 – маршрут длины 4, соединяющий вершины v1, v2; это цепь, которая не является простой, так как вершина v2 встречается дважды;

4)v1x1v2x2v3x2v2 – маршрут длины 3, соединяющий вершины v1, v2

ине являющийся цепью, так как ребро x2 = {v2, v3} встречается дважды.

Пример 7. Рассмотрим ориентированный псевдограф D из примера 1. Тогда:

1)v1x1v2x4v3 – путь длины 2 из v1 в v3; это простая цепь так, как все дуги и вершины попарно различны;

2)v2x3v2 – простой контур длины 1;

3)v1x2v2x3v2x4v3 – цепь из v1 в v3 длины 3, которая не является про-

стой.

Нетрудно показать, что в псевдографах, мультиграфах и графах минимальная длина простого цикла равна соответственно 1, 2 и 3 (каковы минимальные длины простых контуров в ориентированных псевдографах, мультиграфах и графах?).

Утверждение 3. В псевдографе G (в ориентированном псевдографе D) из всякого цикла (замкнутого пути) можно выделить простой цикл (простой контур).

Доказательство будем проводить для G (для D доказательство аналогично) индукцией по k – количеству ребер в цикле. При k = 1 всякий цикл является простым. Пусть при некотором k ≥ 2 доказываемое утверждение справедливо для любого цикла длины ≤ k-1. Покажем его справедливость для произвольного цикла µ = v1x1...vkxkv1

длины k. Рассмотрим любые два номера i, j, где 1≤ i< j≤ k, такие, что vi = vj. Если таких номеров нет, то цикл µ является простым (по определению). Если же указанные номера нашлись, то рассматриваем цикл vixi...vj-ixj-ivj длины j-i≤k-1, а из него в силу индуктивного предположения можно выделить простой цикл.

Утверждение 4. Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же начальной и конечной вершинами.

41

Доказательство будем проводить для маршрута (для пути доказательство аналогично) индукцией по k – количеству ребер в маршруте. При k =1 всякий маршрут является простой цепью. Пусть при некотором k ≥ 2 доказываемое утверждение справедливо для любого маршрута длины ≤ k-1. Покажем его справедливость для произвольного маршрута η = vixiv2...xkvk+i, где v1 ≠ vk+1, длины k. Рассмотрим два номера i, j, где 1≤ i< j≤ k +1 такие, что vi = vj. Если таких номеров нет, то маршрут n является простой цепью. Если же указанные номера на-

шлись, то рассматриваем подмаршрут η1 =v1x1v2...xi-lvixjvj+1...xkvk+1 (т. е. предполагаем, что i≠ 1, j≠ k + 1; случаи, когда i = l или j = k + 1, рассмотрите самостоятельно) длины ≤k-1, а из него, в силу индуктивного предположения, можно выделить простую цепь, соединяющую

вершины v1, vk+1.

Введем понятие композиции путей (маршрутов). Пусть

π 1 = v1x1v2...xk-1vk, π 2 = vkxkvk+1...xl-1vl – пути в орграфе D, где k ≥ 2, l ≥ k+1.

Назовем путь π 1 o π 2 = v1x1v2...xk-1vkxkvk+1...xl-1vl (очевидно, что π 1 o π 2 – путь в D) композицией путей π 1, π 2. Аналогично определя-

ется композиция маршрутов.

Матричное задание графов. Матрицы смежности, инцидентности

Пусть D = (V, X) – орграф, где V = {V1,..., vn}, X = {x1,...,xm}.

Матрицей смежности орграфа D называется квадратная матрица A(D) = [аij] порядка n, у которой

1,если (vi ,v j	) X ;
aij = 0,если (vi ,v j	) X .
Матрицей инцидентности (или матрицей инциденций) орграфа
D называется (n×m) матрица B(D) = [bij], у которой

	является концом дуги x j ;
1, если вершина vi
bij = -1, если вершина vi является началом дуги xj ;
	неинцидентна дуге x j .
0, если вершина vi

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V = {V1,..., vn},

X = {x1,...,xm}.

42

Матрицей смежности графа G называется квадратная матрица A(G) = [aij] порядка n, у которой

aij =	1,если (vi ,v j	) X ;
	0,если (vi ,v j	) X .

Матрицей инцидентности графа G называется (n×m) – матрица B(G) = [bij], у которой

1, если вершина	v	i		инцидентна ребру	x	j	;
bij =	v			неинцидентна ребру				x		.
0, если вершина			i						j

Пример 8. Для орграфа D, изображенного на рис. 6, матрица А(D) приводится в табл. 4, а матрица B(D) – в табл. 5.

Таблица 4

Матрица А(D)

	v1	v2	v3
v1	0	1	0
v2	1	0	1
v3	1	0	0

Таблица 5

Матрица B(D)

	x1	x2	x3	x4
v1	-1	0	1	1
v2	1	-1	0	-1
v3	0	1	-1	0

Рис. 6. Орграф D

Пример 9. Для графа G, изображенного на рис. 7, матрица A(G) приводится в табл. 6, а матрица B(G) – в табл. 7.

			Таблица 6						Таблица 7
	Матрица A(G)						Матрица B(G)
		v1	v2	v3				x1		x2
v1		0	1	1		v1		1		1
v2		1	0	0		v2		1		0
v3		1	0	0		v3		0		1

43

Замечание 6. Матрицу смежности можно определить и для псевдографов. Тогда в случае ориентированного (неориентированного) псевдографа аij = k, где k-кратность дуги (vi, vj) (ребра {vi, vj}) в этом псевдографе.

Рис. 7. Граф G

Определение матрицы инцидентности без изменений переносится и на произвольные мультиграфы (ориентированные и неориентированные) и даже на неориентированные псевдографы.

Пример 10. Для ориентированного псевдографа D, изображенного на рис. 8, матрица A(D) приводится в табл. 8.

			Таблица 8
	Матрица A(D)
	v1	v2		v3
v1	1	2		0
v2	0	0		0
v3	2	3		2

Рис. 8. Псевдограф D

Нетрудно видеть, что матрица A(G) является симметричной для любого неориентированного графа G. Матрица A(D), где D – орграф, в общем случае не является симметричной (см. примеры 8 и 10).

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

44

чая их нумерацию непосредственно из определения матрицы А = А(D). Предположим, что доказанное утверждение справедливо при k. Покажем его справедливость и при k = k +1. Обозначим через П (D, vi, vj, r), где r≥1, множество путей длины r из vi в vj в ориентированном псевдографе D. Разобъем множество путей П (D, vi, vj, k+1) на п групп. Первая группа – это множество П (D, vi, v1, vj, k+1) путей с предпоследней вершиной v1, вторая группа – множество П (D, vi, v2, vj, k+1) путей с предпоследней вершиной v2 и т. д., n-я группа – множество П (D, vi, vn, vj, k+1) путей с предпоследней вершиной vn. Очевидно, что совокупность указанных групп является разбиением множества П(D, vi, vj, k+1). Заметим, что по правилу произведения

П(D, vi, vl, vj, k+1)| =| П(D, vi, vl, k) || П(D, vl, vj, 1)| = | П(D, vi, vl, k)|aij, где l=1,2,…,n

Отсюда, используя то, что в силу индуктивного предположения

выполняется равенство | П(D, vi, vl, k) | = a(k)il, получаем |П(D, vi, vl, vj,

k+1)| = a(k+1)ij.

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

Приведем очевидные свойства матриц смежности и инцидентности:

1.Сумма элементов матрицы A(G), где G = (V, X)-мультиграф, V = {v1,...,vn}, по i-й строке (или по i-му столбцу равна δ (vi).

2.Суммы элементов матрицы A(D), где D = (V,X)-opиенти- рованный псевдограф, V={v1,...,vn}, по i-й строке и по i-му столбцу

соответственно равны δ+(vi), δ−(vi).

3. Пусть D – ориентированный мультиграф с непустым множеством дуг. Тогда:

а) сумма строк матрицы В(D) является нулевой строкой;

б) любая строка матрицы B(D) является линейной комбинацией остальных строк;

в) ранг матрицы B(D) не превосходит n(D)-1;

г) для любого контура в D сумма столбцов матрицы B(D), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

45

4. Пусть G – мультиграф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2:

a) сумма строк матрицы В(G) является нулевой строкой;

б) любая строка матрицы B(G) является суммой остальных строк; в) для любого цикла в G сумма столбцов матрицы В(G) соответ-

ствующих ребрам, входящим в этот цикл, равна нулевому столбцу. Обозначим через А(k)=[a(k)ij] k-ю степень матрицы смежности

A=A(D) орграфа D (аналогичное обозначение вводим для графа G). Утверждение 5. Элемент а(k)ij матрицы А(k) ориентированного

псевдографа D = (V,X) (псевдографа G = (V,X)), где V={v1,...,vn}, равен числу всех путей (маршрутов) длины из vi в vj (соединяющих vi, vj).

Доказательство проведем для D (для G оно аналогично) индукцией по k. При k = 1 справедливость доказываемого утверждения

следует.

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

Утверждение 6. Для того, чтобы n-вершинный орграф D с матрицей смежности A=A(D) имел хотя бы один, контур, необходимо и достаточно, чтобы матрица K = A2+ A3+…+ An имела ненулевые диагональные элементы.

Достаточность. Пусть K = [kij] и для некоторого номера i выполняется kii > 0. В этом случае для некоторого r ={2,...,n} справедливо a(r)ii > 0), а следовательно, в силу утверждения 5 найдется путь в D из vi в vi. Но тогда в силу утверждения 3 в орграфе D найдется простой контур.

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

любой вершины vi, принадлежащей некоторому простому контуру длины l, где 2 ≤ l ≤ n, элемент a(l)ii матрицы Аl отличен от нуля, а сле-

довательно, и элемент kii матрицы К отличен от нуля.

Замечание 5. В случае ориентированного n-вершинного псевдографа D, для существования в D контура необходимо и достаточно, чтобы матрица K = A2+ A3+…+ An имела ненулевые диагональные элементы. Доказательство аналогично.

46

Связность. Компоненты связности

Говорят, что вершина w орграфа D (графа G) достижима из вершины v, если либо w = v, либо существует путь из v в w (маршрут, соединяющий v, w).

Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяю-

щий v, w (из v в w).

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

Псевдографом, ассоциированным с ориентированным псевдографом D = (V, X), называется псевдограф G = (V, Хо), в котором Х0 получается из Х заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w} (рис. 9, где а – ориентированный псевдограф; б – ассоциированный с ним псевдограф).

а

б

Рис. 9. Псевдографы

Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.

Если граф (орграф) не является связным (слабо связным), то он называется несвязным.

Компонентой связности (сильной связности) графа G (орграфа D)

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

Пример 11. У графа, изображенного на рис. 10, три компоненты связности.

Рис. 10. Граф

47

Пример 12. У орграфа, изображенного на рис. 11, а, три компоненты сильной связности, показанные на рис. 11, б.

ϑ2 ϑ4

а

б

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

Из определения компоненты связности (сильной связности) заключаем, что справедливо:

Утверждение 7.

1.Пусть G1 = (V1, X1) – компонента связности графа G. Тогда G1 – подграф графа G, порожденный множеством V1.

2.Пусть D1 = (V1, X1) – компонента сильной связности орграфа D. Тогда D1 – подграф орграфа D, порожденный множеством V1.

Замечание 6. Утверждение 7 остается в силе и для произвольных псевдографов (ориентированных и неориентированных).

Нетрудно показать, что справедливы следующие утверждения.

Утверждение 8. Пусть G = (V, X) - псевдограф с р-компонентами связности: G1 = (V1,X1),..., Gp = (Vp, Хр). Тогда:

1) V = V1 UV2 U... UVp , X = X1 U X 2 U... U X p ,

т.е. G = G1 U G2 U... U G p ;

2) Vi IV j = , X i I X j = при i ≠ j;

3) n(G1) +...+ n(Gp) = n{G), m(G1) +...+ m(Gp) = m (G).

Утверждение 9. Пусть D = (V, X) – ориентированный псевдограф с р-компонентами сильной связности: D1= (V1, X1), ...,

Dp = (Vp, Xp). Тогда:

1)	V = V1 UV2 U... UVp , X X1 U X 2 U... U X p ;
2)	Vi IV j	= , X i I X j = при i ≠ j;
3) n(G1)+		...+n(Gp) = n{G), m(G1)+...+m(Gp)≤m(G).
		48

Утверждение 10. Пусть ρ – отношение достижимости на множестве V вершин псевдографа G, т. е. v ρ w тогда и только тогда, когда

либо v = w, либо существует маршрут, соединяющий v, w. Тогда:

1)ρ – эквивалентность на V;

2)v ρ w тогда и только тогда, когда вершины v, w принадлежат

одной компоненте связности псевдографа G;

3)для любого класса эквивалентности V1 V/ ρ псевдограф G1, по-

рожденный множеством V1, является компонентой связности псевдографа G;

4)для любой компоненты связности G1 = (V1, X1) псевдографа G выполняется V1 V/ ρ .

Утверждение 11. Пусть ρ1 – отношение достижимости на множестве V вершин ориентированного псевдографа D, т. е. v ρ1 w тогда

итолько тогда, когда вершина w достижима из v. Пусть также

ρ2 – отношение двусторонней достижимости на V, т. е. ρ2 = ρ1 I ρ1−1

Тогда:

1)ρ1 – рефлексивно, транзитивно;

2)ρ2 – эквивалентность на V;

3)v ρ2 w тогда и только тогда, когда вершины v, w принадлежат

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

4)для любого класса эквивалентности V1 V/ ρ2 ориентированный псевдограф D1, порожденный множеством V1, является компонентой сильной связности ориентированного псевдографа D;

5)для любой компоненты сильной связности D1 = (V1,X1) ориен-

тированного псевдографа D выполняется V1 V / ρ2 .

В дальнейшем количество компонент связности графа G будем обозначать через p(G). Аналогично, через p(D) будем обозначать количество компонент сильной связности орграфа D.

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

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

49