учебное пособие - теория графов

Лемма 21.2. Пусть K – матрица Кирхгофа графа G и B – соответ-

ствующая матрица инцидентности некоторой его ориентации. Тогда K = B · tB.

Лемма 21.3. Пусть G – произвольный граф с n вершинами и (n–1) ребрами, n > 2, B – матрица инцидентности некоторой его ориентации, М – произвольный минор порядка (n –1) матрицы B. Тогда

1)если G не является деревом, то М = 0;

2)если G – дерево, то М = ±1.

Лемма 21.4 (формула Бине – Коши). Пусть P – (s × t)-матрица, Q

– (t × s)-матрица и s < t, C=P·Q. Тогда определитель матрицы C равен сумме всевозможных попарных произведений миноров порядка s матрицы P на соответствующие миноры матрицы Q.

	(Минор		1	порядка s матрицы Q называется соответствующим ми-
нору	2	порядка s матрицы Р, если множество номеров строк, состав-
ляющих матрицу минора					1 , равно множеству номеров столбцов, состав-
ляющих матрицу минора					2 .)

Теорема 21.2 (теорема Кирхгофа). Число остовных деревьев в

связном графе G порядка n≥2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа K графа G.

Доказательство. Пусть G – произвольный связный граф с n вершинами и m ребрами, n ≥ 2 и B – матрица инцидентности какой-либо ориентации графа G. В силу связности графа G имеем m ≥ n–1. По лемме 21.2 K = B·tB. Пусть K' – подматрица матрицы K, полученная из K удалением последней строки и последнего столбца. Тогда определитель матрицы K' есть алгебраическое дополнение элемента knn в матрице Кирхгофа K. Пусть B' – подматрица матрицы B, полученная из B удалением последней строки. Согласно лемме 21.2 K' = B' · t (B'). По лемме 21.4 определитель матрицы K' равен сумме квадратов всех миноров порядка (n – 1) матрицы B'. Согласно лемме 21.3 каждый такой минор М равен ±1, если подграф графа G, ребра которого соответствуют столбцам, вошедшим в матрицу минора М, является деревом, и равен 0 в противном случае. Следователь-

91

но, определитель матрицы K' равен числу остовов графа G. Отметим, что по лемме 21.1 алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой. Теорема доказана.

§22. Фундаментальные циклы

ифундаментальные разрезы графов

Содержание параграфа

фундаментальный цикл графа;

матрица фундаментальных циклов;

разрезающее множество графа;

разрез графа, простой разрез графа;

теоремы о связи циклов с разрезами;

фундаментальный разрез графа;

матрица фундаментальных разрезов графа.

Пусть G – неориентированный граф, имеющий n вершин, m ребер и k компонент связности, T – остов графа G, v1, ,vn k – ветви остова T, u1 , ,um n k – хорды остова T, T – граф, полученный из T добавлением

хорды ui , 1 i m n k , т.е. T T ui	теорема 20.1	T имеет единствен-

ный цикл, состоящих из хорды ui и некоторых ветвей остова T, причем

по теореме 20.1 эти ветви принадлежат единственной цепи, соединяющей концы хорды ui простой цепью.

Определение 22.1. Пусть G – неориентированный граф, T – остов графа G, u – хорда остова T. Фундаментальным циклом графа G относительно остова T и хорды u называется цикл C графа G, состоящий из хорды u и тех ветвей остова T, которые соединяют концы хорды u простой цепью.

92

Замечание 22.1. Из определения 22.1 следует, что граф G относительно заданного остова T имеет m n k G фундаментальных циклов.

Множество C1,C2 , ,C G всех фундаментальных циклов графа G

относительно остова T называют фундаментальным множеством цик-

лов графа G.

Определение 22.2. Пусть G – неориентированный граф, имеющий n вершин, m ребер и k связных компонент, T – остов графа G, u1 , ,um –

ребра графа G, С1 , ,Cm n k – фундаментальные циклы графа G относи-

тельно остова T. Матрицей фундаментальных циклов графа G отно-

сительно остова T называется матрица размера m n k m вида:

	a		a
	11		1m			1, если u j		Ci
M				,	где aij				, i 1, m n k ,
								C
						0, если u	j		i
am n k 1		am n k m

j 1, m.

Определение 22.3. Разрезающим множеством графа G называ-

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

Определение	22.4. Пусть	G – неориентированный граф,
G V , R , V1,V2	– разбиение	множества V,	т.е. V1 V2 V и
V1 V2 . Разрезом графа G по разбиению V1 ,V2			называется множе-

ство L всех ребер графа G, соединяющих вершины из V1 с вершинами из

V2 .

Пример 22.1. Пусть граф G имеет вид:

93

94

Пусть	V1	1,4 , V2 2,3 .	Тогда	L 1,3 , 2,4 .
Пусть	V1	1 , V2 2,3,4 .	Тогда	L 1,3 , 1,4 .

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

Замечание 22.2. Разрез, состоящий из одного ребра, является про-

стым.

Замечание 22.3. Простые разрезы графа также называют коциклами. Понятия остова и простого разреза являются противоположными в том смысле, что остов содержит минимальное число ребер графа G, которые соединяют посредством маршрутов все вершины графа G, а разрез содержит минимальное число ребер, которые отделяют некоторые вершины графа от остальных.

Теорема 22.1. Пусть G – неориентированный граф, имеющий k связных компонент, L – некоторое множество ребер графа G. Множество L является простым разрезом графа G тогда и только тогда, когда граф G V , R \ L имеет k 1 связную компоненту, где G V , R .

Теорема 22.2 (о связи остова с разрезами). Пусть G – связный не-

ориентированный граф. Тогда всякий остов графа G имеет с каждым из разрезов хотя бы одно общее ребро.

Теорема 22.3 (о связи циклов с разрезами). Пусть G – связный не-

ориентированный граф. Тогда всякий цикл графа G имеет с каждым из разрезов четное число ребер.

Пусть G – неориентированный граф, имеющий n вершин, m ребер и k связных компонент, T – остов графа G, v1, ,vn k – ветви остова T; u1 , ,um n k – хорды остова T.

Пусть T – граф, полученный из T удалением некоторой ветви vi , 1 i n k . Тогда T имеет k 1 связных компонент. Множество

L1 , , Ln k

L vi является простым разрезом графа G по некоторому разбиению

V1 ,V2 .

Пусть ui1 ,ui 2 , ,uin – все хорды остова T, которые соединяют

вершины из V1 с вершинами из V2. Тогда vi ,ui1, ,uin является разрезом графа G по разбиению V1 ,V2 .

Определение 22.6. Пусть G – неориентированный граф, T – остов графа G, v – ветвь графа G. Фундаментальным разрезом графа G относительно остова T и ветви v называется разрез L графа G, состоящий из ветви v, которая является простым разрезом остова T по некоторому разбиению V1 ,V2 , и всех хорд остова T, которые соединяют вершины из V1 с вершинами из V2.

Из определения следует, что граф G имеет столько фундаментальных разрезов, сколько ветвей имеет остов T , т.е. граф G имеетn k * G фундаментальных разрезов.

Пусть L1 , , Ln k – множество всех фундаментальных разрезов

графа G относительно остова T. Это множество называется фундамен-

тальным множеством разрезов графа G.

Определение 22.7. Пусть G – неориентированный граф, имеющий n вершин, k связных компонент, m ребер u1 , ,um ; T – остов графа G,

– фундаментальные разрезы графа G относительно остова T.

Матрицей фундаментальных разрезов графа G относительно остова

T называется матрица N размера n k m вида:

	a		a
	11		1m
N				,
a	n k 1	a
			n k m

		j	i
	1, если u		L
где aij				, i 1, n k , j 1, m.
			Li
	0, если u j

95

Глава IV. Планарные графы

§ 23. Плоские и планарные графы

Содержание параграфа

плоский граф;

планарный граф;

понятие укладки графа на плоскости, на поверхности, в пространстве;

непланарность графов K5 и K3,3;

признаки планарности графа.

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

Пример 23.1.

Определение 23.2. Граф называется планарным, если он изоморфен некоторому плоскому графу.

Граф из примера 23.1 б) является планарным, так как он изоморфен графу из пунктов в) и а).

Замечание 23.1. Графы K1, K2, K3, K4 являются планарными.

96

Замечание 23.2. Если G – планарный граф, то говорят, что граф G укладывается на плоскости. Аналогично можно рассмотреть укладку графа на других поверхностях и в пространстве.

Определение 23.3. Жордановой кривой называется непрерывная линия без самопересечений.

Теорема 23.1 (теорема Жордана). Пусть S – некоторая замкнутая жорданова кривая, x,y S, x y. Тогда всякая жорданова кривая, соединяющая точки x и y, отличная от S, либо лежит полностью внутри S, либо лежит вне S, либо пересекает S по крайней мере в одной точке, отличной от x и y.

Замечание 23.3. Говорят, что граф G укладывается в пространстве L, если существует инъективное отображение множества вершин графа G во множество точек пространства L и существует инъективное отображение множества рёбер графа G во множество жордановых кривых пространства L, при которых кривые, соответствующие различным рёбрам, пересекаются лишь в точках, инцидентных данным рёбрам. Построенный таким образом граф называют укладкой графа G в пространстве L.

Теорема 23.2. Всякий граф укладывается в трёхмерном простран-

стве.

Доказательство. Пусть G=(V,R) – граф. Расположим все вершины графа G на оси Ox.

97

Выберем из пучка плоскостей, проходящих через ось Ox, произвольно R плоскостей. В каждой из плоскостей изобразим одно из рёбер полуокружностью, соединяющей смежные вершины.

Таким образом, получим укладку графа G в трехмерном пространстве. Теорема доказана.

Теорема 23.3. Граф G укладывается на сфере тогда и только тогда, когда G – планарный граф.

Замечание 23.4. В теории графов хорошо известна задача о трёх домах и трёх колодцах: имеется три дома и три колодца, причем жители каждого дома могут пользоваться любым колодцем. Возникает вопрос: можно ли проложить дорожки от домов до колодцев так, чтобы они не пересекались?

98

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

Теорема 23.4. Граф K5 не является планарным.

Доказательство. Так как K5 – связный граф и K5 имеет 5 вершин, то в нём существует цикл длины 5. Допустим, что K5 – планарный граф. Следовательно, K5 G, где G – плоский связный граф, имеющий 5 вершин. Следовательно, в G также имеется цикл длины 5, который можно изобразить правильным пятиугольником. Достроим недостающие рёбра.

1)ребра [a, d], [a, c],

2)ребра [b, e], [b, d],

3)ребро [c, e] – построить невозможно.

Следовательно, граф K5 не является планарным. Теорема доказана.

Теорема 23.5. Граф K3,3 не является планарным.

99

Доказательство проводится аналогично доказательству теоремы

23.4.

Теорема 23.6 (теорема Понтрягина – Куратовского). Граф G яв-

ляется планарным тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам K5 или K3,3.

Теорема 23.7 (свойства планарных графов).

1.Всякий подграф планарного графа является планарным.

2.Если граф имеет непланарный подграф, то он является непланарным.

Доказательство непосредственно следует из определения 23.2.

§ 24. Грани плоского графа

Содержание параграфа

точка, дизъюнктная с плоским графом;

точки, эквивалентные относительно графа;

грани плоского графа;

теорема Эйлера о гранях плоского графа;

следствия теоремы Эйлера;

число планарности (искаженность) графа и его оценка;

толщина непланарного графа и ее оценка.

Определение 24.1. Пусть G – плоский граф, расположенный на плоскости L.

1.Точка x L называется дизъюнктной с графом G, если x не является вершиной графа G и x не лежит ни на одном ребре графа G.

2. Точки x, y L называются эквивалентными относительно графа

G, если x и y дизъюнктны с графом G и существует жорданова кривая на плоскости L, соединяющая x и y, все точки которой дизъюнктны с графом G.

100