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

2.Клика V' называется максимальной, если V' не содержится в клике с большим числом вершин.

3.Клика V' называется наибольшей, если число вершин в ней наибольшее среди всех клик.

4.Число вершин в наибольшей клике графа G называется кликовым числом или плотностью графа G.

Теорема 18.4. Подмножество вершин графа G является кликой

тогда и только тогда, когда оно независимо в дополнительном графе G .

Пример 18.2. Пусть G=(V,R) – граф, имеющий вид:

Тогда граф G имеет следующие клики:

Рассмотрим понятие матрицы клик.

Определение 18.8. Пусть G=(V,R) – произвольный граф, Q = {Q1,Q2,…,Qр} – множество всех максимальных клик графа G и V={a1,a2,…,an}. Матрицей клик графа G называется матрица C=(cij)

1, если a		Q
размера p×n такая, что cij=	j	i , где i 1, p, j 1, n.
0, если a j		Qi

Пример 18.3. Для графа G из примера 18.2 матрица клик имеет следующий вид:

81

Q1	1 1 0				0	0	0	0	0
Q2		0	1	1	0	0	0	0	1
C Q		0	0	1	0	0	1	1	0	.
3
Q4	0		0	1	0	1	1	0	0
Q5		0	0	0	1	1	1	0	0

Независимое множество ребер (паросочетание)

Пусть G=(V,R) – двудольный граф. Напомним, что подмножество М множества R называется паросочетанием, если никакие два ребра из М не имеют общей вершины. Таким образом, никакие два ребра не являются инцидентными. Если (а,b) – ребро в паросочетании М, то вершины а и b имеют паросочетающие ребра. При этом вершины а и b называются

паросочетанными.

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

Определение 18.9. Паросочетание М двудольного графа G=(V,R) называется максимальным, если никакое другое паросочетание графа G не содержит ребер больше, чем М.

Определение 18.10. Паросочетание М двудольного графа G=(V,R) с

долями A и B называется полным, если для каждой вершины а A суще-

ствует вершина b В такая, что (a,b) M.

Определение 18.11. Пусть G=(V,R) – двудольный граф с долями A и

B, X – подмножество множества А. Множество R(Х)={b: b B и b – смежная с вершиной из Х} называется множеством значений X.

Теорема 18.5 (теорема Холла). Двудольный граф G=(V,R) с долями A и B имеет полное паросочетание тогда и только тогда, когда для каждого подмножества X A выполняется неравенство |X |≤| R (X ) |.

82

Глава III. Деревья и их приложения

§ 19. Деревья и их простейшие свойства

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

определение неориентированного дерева;

простейшие свойства деревьев;

теорема Кэли о числе деревьев n-го порядка;

понятие ориентированного дерева;

упорядоченные деревья;

понятие бинарного дерева.

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

Напомним, что лесом называется неорграф, не имеющий циклов. Таким образом, дерево представляет собой частный случай леса. Дерево – это связный лес.

Рассмотрим простейшие свойства деревьев.

Лемма 19.1. Неорграф G является деревом тогда и только тогда, когда любые две несовпадающие вершины графа G соединены единственной цепью.

83

Доказательство. 1. Необходимость. Пусть G (V , R) – дерево. Тогда G – связный граф. Поэтому для любых вершин a,b V существует

цепь P, соединяющая a и b. Пусть, например	P : (a,...,b) .
Предположим, что существует цепь	P	вида: (a,...,b) , причем
	1

P P1 . Тогда из цепей P и P1 можно образовать цикл (a,…,b,…,a). Противоречие. Следовательно, для любых вершин a,b V существует единственная цепь, их соединяющая.

2. Достаточность. Пусть любые две вершины графа G соединены единственной цепью (1). Покажем, что G – дерево. Из условия (1) следу-

ет,	что G –	связный граф. Допустим, что				G имеет	цикл
P	(a1 , a2 ,..., an	a1 ) . Тогда вершины a1		и a2	соединены цепью (a1 , a2 )
и	(a1 , an 1 ,..., a2 ) . Получили противоречие. Следовательно, граф G не
имеет циклов, и значит, G – дерево. Лемма доказана.
	Лемма 19.2. Пусть G – дерево и a – концевая вершина графа G. То-
гда граф G–a также является деревом.
	Лемма 19.3. Пусть		G (V , R)	–	дерево,	a V ,	b V ,
G1 (V1, R1 ) , где V1 V {a},			R1 R {[a, b]}. Тогда граф G1				также
является деревом.

Лемма 19.4. Всякое непустое дерево имеет, по крайней мере, две концевые вершины и одно концевое ребро.

Теорема 19.2 (теорема Кэли). Число различных деревьев, которые можно построить на n вершинах, равно nn 2 .

Определение 19.2.

1.Орграф G=(V,R), не содержащий контуров, называется ориентированным деревом, если существует единственная вершина a V (на-

84

зываемая корневой вершиной или корнем) такая, что deg a 0 , и

для любой вершины b V \ a выполняется условие deg b 1 .

2.Вершины, инцидентные корневой вершине а, называются непосред-

ственными (прямыми) потомками вершины а. Потомком вершины

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

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

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

стоящий из одного или нескольких ориентированных деревьев.

Теорема 19.3. Орграф G=(V,R) является ориентированным деревом, если G имеет такую вершину a, из которой достижима всякая другая вершина b, причем путь, соединяющий а и b, единственный.

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

Определение 19.5. Орграф G=(V,R) называется бинарным, если для любой вершины a V : deg a 2 .

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

§ 20. Характеризационная теорема для деревьев

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

характеризационная теорема для деревьев;

следствие характеризационной теоремы.

85

Теорема 20.1 (характеризационная теорема для деревьев). Пусть G

– неорграф без петель, имеющий n вершин. Тогда следующие утверждения эквивалентны:

1)G является деревом;

2)G не имеет циклов и имеет (n–1) ребро;

3)G – связный граф, имеющий (n–1) ребро;

4)G – связный граф, и всякое его ребро является мостом;

5)любые две несовпадающие вершины графа G соединяет единственная простая цепь;

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

Доказательство. Если n=1, то 1) – 6) утверждения эквивалентны. Пусть n >1 и G (V , R) .

I. Докажем, что 1) 2). Пусть G – дерево с n вершинами. Тогда по определению в G нет циклов. Докажем, что G имеет (n–1) ребро. Доказательство проведем методом математической индукции по параметру n.

Пусть n=2. Тогда |R|=1.

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

Докажем утверждение для n. Удалим из графа G одно ребро. Получим подграфы G1 и G2 графа G, причем Gi – связный неорграф, i 1,2 .

Пусть Gi (Vi , Ri ) и | Vi | ni . Тогда ni n , i 1,2 . Следовательно, по предположению индукции | Ri | ni 1, и поэтому

| R | | R1 | | R2 | 1 n1 1 n2 1 1 (n1 n2 ) 1 n 1.

Из 1–3 по методу математической индукции следует, что утверждение верно для любого натурального n.

86

Замечание 1. Из пункта I следует, что если G – связный граф с n вершинами, то G имеет по крайней мере (n–1) ребро.

II. Докажем, что 2) 3). Пусть G не имеет циклов и имеет (n–1) ребро. Покажем, что G – связный граф. Предположим, что G – несвязный граф и G1 ,G2 ,...,Gk – связные компоненты графа G. Тогда k >1. Так как

G1 ,G2 ,...,Gk – связные неорграфы без циклов, то G1 ,G2 ,...,Gk		– деревья.
Ввиду пункта I, из Gi (Vi , Ri ) , | Vi	| ni , получим | Ri | ni	1.	Тогда
| R | | R1 | | R2 | ... | Rk | n1 1 n2	1 ... nk 1
(n1 n2 ... nk ) k n k , что невозможно. Следовательно,			допу-

щение неверно, и поэтому G – связный граф.

III. Докажем, что 3) 4). Пусть G – связный граф, имеющий (n–1) ребро. Покажем, что всякое ребро графа G является мостом. Пусть u R и G' G u . Покажем, что G' – несвязный граф. Подсчитаем количество ребер графа G'. Оно равно (n–2), а количество вершин графа G' равно n. Следовательно, из замечания 1 получаем, что G' – несвязный граф, а значит, ребро u является мостом.

IV. Докажем, что 4) 5). Пусть G – связный граф и всякое его ребро является мостом. Пусть a,b V , a b . Так как G – связный граф, то существует цепь, соединяющая вершины a и b. Допустим, что существует две простые цепи, соединяющие a и b. Составим из них цикл и удалим из цикла некоторое ребро u. При этом, полученный граф G–u остаётся связным. Следовательно, ребро u не является мостом. Получили противоречие с условием. Таким образом, любые две несовпадающие вершины графа G соединяет единственная простая цепь.

V. Докажем, что 5) 6).

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

пустим, что граф G имеет цикл (a1 , a2 ,..., an a1 ) .	Тогда вершины
a1 , a2 соединены цепью (a1 , a2 ) и цепью (a2 , a3 ,..., an	a1 ) . Противо-
речие. Следовательно, граф G не имеет циклов.
87

P2

б) Пусть a и b – несмежные несовпадающие вершины G. Соединим вершины a и b ребром и получим граф G , то есть G G a,b . Из ус-

ловия следует, что существует цепь		P : (a,...,b) . Следовательно, в гра-
фе G существует цикл	P : (a,..., b, a) . Допустим, что существует еще
	1
некоторый цикл P :	(a,...,b, a)	, причем P P . Тогда	P P . По-
		1	2

лучили противоречие, так как по условию любые две вершины соединены единственной простой цепью. Следовательно, цикл Р1 – единственный.

VI. Докажем, что 6) 1). Пусть граф G не имеет циклов, но если какую–либо пару его несмежных несовпадающих вершин соединить ребром, то получится граф, имеющий единственный цикл. Отсюда следует, что G – неорграф, не имеющий циклов. Покажем, что G – связный граф. Допустим, что G – несвязный граф. Тогда G имеет, по крайней мере, две

связные компоненты G1

и G2. Пусть Gi

(Vi , Ri ) , i 1,2 .

Пусть

a V1

и b V2 .

Соединим вершины a и b ребром. Тогда

граф G G (a,b)

не будет иметь циклов.

Получили противоречие с

условием. Следовательно, G – связный граф. Поскольку в G нет циклов,

то G – дерево. Теорема доказана.

Следствие 20.1.1. Пусть G – лес, имеющий n вершин и k компонент

связности. Тогда G имеет (n–k) ребер.

Доказательство.

Пусть

G (V , R) .

Тогда

V

n .

Пусть

G ,G , ,G

– связные компоненты

графа

G, G (V , R ) ,

V

n ,

1

2

k

i

i i

i

i

i 1, k .

Так как G – лес, то Gi – дерево, i 1, k . Тогда по теореме 20.1

Ri

ni

1 ,

i 1, k . Следовательно,

R

R

R

n 1 n 1 n

n

k n k .

1

k

1

k

1

k

n

Следствие доказано.

88

§ 21. Остовы графов

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

остовы (каркасы) графа;

ветви и хорды остова;

теорема о числе ветвей и хорд остова;

циклический и коциклический ранги графа;

матричная теорема Кирхгофа о числе остовных деревьев связного графа.

Определение 21.1. Пусть G=(V,R) – неорграф. Часть Т (V , R ) графа G называется остовом графа G, если V V и Т является лесом, который образует дерево на каждой связной компоненте графа G.

Определение 21.2. Пусть G – неорграф, Т – остов графа G. Ребра графа G, входящие в остов Т, называются ветвями остова Т. Ребра графа G, не входящие в Т, называются хордами остова Т.

Пример 21.1. Пусть граф G=(V,R) имеет вид:

Тогда граф G имеет остов Т (V , R ),	где V V ,
R u4 ,u1 ,u2 ,u7 ,u8 .

Замечание 21.1. Любой неорграф имеет остов: разрушая в каждой связной компоненте циклы, т.е. удаляя лишние ребра, получаем остов.

89

Теорема 21.1. Пусть G – неорграф, имеющий n вершин, m ребер и k связных компонент. Тогда число ребер, которые требуется удалить для получения остова графа G, не зависит от последовательности их удаления и равно m (n k) .

Доказательство. Пусть G=(V,R) – неорграф, имеющий n вершин, m ребер и k связных компонент, Т – остов графа G. Тогда Т – лес с n вершинами и k связными компонентами. Согласно следствию 20.1.1, Т имеет n k ребер. Это означает, что число удаляемых ребер равно m (n k) . Теорема доказана.

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

1.Число (G) m (n k) называется циклическим рангом графа G или цикломатическим числом, то есть (G) – число ребер, которые требуется удалить из G для получения остова.

2.Число (G) n k называется коциклическим рангом графа G или

корангом, то есть (G) – число ребер графа G, входящих в остов графа G.

Замечание 21.2. Из определения 21.2 следует, что сумма циклического и коциклического рангов графа G равна числу ребер графа G.

Следствие 21.1.1. Пусть G – неорграф. Тогда справедливы следующие утверждения:

1. Граф G является лесом тогда и только тогда, когда (G) 0.

2. Граф G имеет единственный цикл тогда и только тогда, когда

(G) 1.

Следующие леммы используются при доказательстве теоремы Кирхгофа.

Лемма 21.1. Алгебраические дополнения всех элементов матрицы Кирхгофа графа G равны между собой.

90