Дискретная математика / ДМ_Графы

	Часть III. ГРАФЫ
1. Начальные понятия теории графов
Графом V , E называется пара множеств:					V v1, v2 , , vn – непустое множество,
элементы которого называются вершинами,		E vi , v j vi , v j				V – множество неупорядоченных
пар вершин, называемых ребрами. Будем обозначать ребра k						vi , v j .
На чертеже граф представляет собой совокупность точек – вершин, и соединяющих их
линий – ребер (рис. 1).
	v3		α5		v5
	α2	α4	α6		α7
v2	α3				v6
			v4	α8
					α9
α1						v7
v1
		Рис. 1
Если вершина vi является концом ребра k ,				то они называются инцидентными, следова-

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

Вершины vi и v j , образующие хотя бы одно ребро называются смежными. Два ребра k и p называются смежными, если они инцидентны одной и той же вершине.

Вершина графа инцидентная ровно одному ребру называется висячей, если же вершина не имеет инцидентных ей ребер, то она называется изолированной (рис. 2).

Рис. 2
Подграфом графа V , E называется любой граф	' V ', E' , для которого

V ' V , E' E . На рисунке 3 представлен подграф графа, изображённого на рисунке 1.

1

v3	v5

v2	v4
v1
	Рис. 3

Если множество Е является множеством упорядоченных пар вершин E vi , v j vi , v j V

(т.е. Е – подмножество декартова произведения V2), то граф называется ориентированным или орграфом, а упорядоченные пары vi , v j называют дугами.

Геометрически, дуга – это ребро, с указанным на нём направлением. Дуга изображается линией со стрелкой, направленной от вершины vi, называемой началом, к вершине vj, именуемой

концом дуги (рис. 4).

	v3	α5		v5
α2	α4	α6		α7
v2	α3			v6
		v4	α8
				α9

	α1	v7
	v1

Рис. 4

Для различения графов, вводится термин неориентированный граф или н-граф в смысле первого определения графа, т.е. граф, состоящий из ненаправленных ребер.

Маршрутом в графе называется такая последовательность его вершин v1, v2 , , vm , в которой любые две соседние вершины соединены ребром, или, иначе, последовательность ребер1, 2 , , k , в которой любые два соседних ребра смежные. В орграфе маршрут называют пу-

тём.

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

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

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

называют циклическим.

Циклический маршрут (путь) называется циклом (контуром), если он является цепью, и

простым циклом (контуром), когда это – простая цепь.

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

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

2

	Незамкнутые	Н-графы	Маршрут	Цепь	Простая цепь
	маршруты	Орграфы	Путь	Цепь	Простая цепь
	Замкнутые	Н-графы	Циклический	Цикл	Простой цикл
			маршрут
	маршруты
		Орграфы	Циклический путь	Контур	Простой контур

Заметим, что множество простых цепей данного графа содержится во множестве цепей графа, а множество цепей в свою очередь во множестве маршрутов:

{простые цепи} {цепи} {маршруты} ,

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

Ребра (дуги) называются кратными, если они инцидентны одной и той же паре вершин. В этом случае множество Е будет содержать одинаковые пары вершин, при этом количество одинаковых пар называется кратностью ребра. Например, кратность ребра {v1, v2} в графе, изображенном на рисунке 5, равна двум, кратность ребра {v3, v4} − трём.

Рис.5

Если множеству Е принадлежат пары вида {v, v}, то такие ребра называют петлями. На рисунке 6 представлен граф с петлями при вершинах v1 и v3.

v2

v1v3

Рис. 6

Псевдограф – граф, в котором есть петли и/или кратные ребра. Мультиграф – псевдограф без петель.

Граф без петель и кратных рёбер называют обыкновенным или простым графом.

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

Обыкновенный граф называется полным, если любые две вершины графа соединены ребром. Полный граф с n вершинами обозначается Kn. На рисунке 7 представлены полные графы K1,

K2, K3, K4, K5.

Рис. 7

Число ребер полного графа с n вершинами равно числу неупорядоченных пар из n-

3

элементного множества, т.е. числу сочетаний Cn2 .

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

Нагруженный граф – граф, каждому ребру (дуге) которого поставлено в соответствие некоторое число ( ) , называемое весом. Таким образом, на множестве ребер Е нагруженного

графа определена весовая функция: ( ) , для любого E .

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

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

Будем использовать следующие обозначения:

для н-графа – G V , E ;

для нагруженного н-графа – G V , E ;

для орграфа – D V , E ;

для нагруженного орграфа – D V , E .

Пример 1. Для графа, изображённого на рисунке 8:

1)определить тип графа;

2)задать граф множеством вершин и множеством ребер.

Рис. 8

Решение.

1)Граф G на рисунке 8:

неориентированный, поскольку не заданы направления ребер;

ненагруженный, так как для графа не определена весовая функция;

неполный, поскольку есть вершины не соединенные ребром, например, v1 и v4 , v4 и v5;

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

не является однородным, так как его вершины имеют различные степени, например:

(v1) 2, (v2 ) 4 ;

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

4

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

граф не является ациклическим (т.е. не содержащим циклы), поскольку в нем можно выделить циклы, например, v1 v2 v3 v1 и v1 v2 v6 v7 v5 v3 v1;

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

2) Множество вершин графа V {v1, v2 , v3,..., v7}, множество ребер A {1,2 ,3,...,11} или

A {{v1, v2},{v1, v3},{v2 , v3},{v2 , v4},{v3, v4},{v3, v5},{v2 , v6},{v4 , v6},{v5 , v6},{v5 , v7},{v6 , v7}}.

Пример 2. Для графа, изображённого на рисунке 9:

1)определить тип графа;

2)задать граф множеством вершин и множеством дуг;

Рис. 9

Решение.

1)Граф на рисунке 9:

ориентированный, поскольку для каждого ребра графа определено направление;

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

неполный, поскольку не все вершины графа являются началом и концом некоторой дуги, например, v1 и v4 , v3 и v1;

не связный, поскольку существуют пары вершин, для которых не существует соединяющего их пути, например, из вершины v2 невозможно попасть в вершину v1;

не является однородным, поскольку его вершины имеют различные полустепени, например: (v1) 2, (v3 ) 1 (полустепени вершин и однородность графа определены в пункте 4).

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

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

граф содержит контуры, например, v3 v4 v2 v3,

v6 v5 v7 v6 ;

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

2) Множество вершин графа V {v1, v2 , v3,..., v7} , множество дуг A {1,2 ,3,...,11} или

A {(v1, v2 ), (v1, v3 ), (v2 , v3 ), (v4 , v2 ), (v3, v4 ), (v5 , v3 ), (v2 , v6 ), (v6 , v4 ), (v6 , v5 ), (v5 , v7 ), (v7 , v6 )}.

5

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

Рассмотрим граф с n вершинами и m ребрами.

Матрицей инцидентности н-графа G называется матрица In G , строки которой соответствуют вершинам, столбцы – ребрам графа, элементы ij определяются по правилу:

	1,	если вершина vi инцидентна ребру j ,
ij		в противном случае.
	0

Матрицей инцидентности орграфа D называется матрица In D , строки которой соответствуют вершинам, столбцы – дугам графа, элементы ij определяются по правилу:

	1, если вершина v	i	начало дуги	j	,
ij
	1, если вершина vi конец дуги j ,
				дуге j .
	0, если вершина vi не инцидентна

Матрицей смежности графа называется матрица S G или S D , строки и столбцы которой соответствуют вершинам графа, а элементы sij определяются по правилу:

	в случае н-графа,	sij	равно числу ребер, соединяющих вершины vi и v j ;
	в случае орграфа,	sij	равно числу дуг с началом в вершине vi и с концом в v j .

Из определения матрицы смежности следует, что

1)матрица S G симметрична относительно главной диагонали;

2)диагональные элементы графа без петель sii 0 .

Способами задания графов являются:

графический способ (изображение графа);

по определению, задаются множества V и Е;

матрицей инцидентности;

матрицей смежности, с точностью до изоморфизма, так как в матрице смежности отсутствует информация о нумерации ребер.

Следующая теорема и следствие выясняют достаточное условие существования циклических маршрутов или контуров длины k с помощью анализа k-той степени матрицы смежности

S k S S S .

k раз

Теорема (о существовании циклических маршрутов). Пусть Sk – k-ая степень матрицы смежности некоторого графа. Если найдутся элементы sii 0 , т. е. на диагонали k-той степени

матрицы смежности Sk найдутся элементы отличные от нуля, то существуют циклические маршруты длины k с началом в вершине vi .

Следствие. Пусть Sk – k-тая степень матрицы смежности некоторого орграфа. Если найдутся элементы sii 0 , т. е. на диагонали k-той степени матрицы смежности Sk найдутся элементы отличные от нуля, то существуют контуры длины k с началом в вершине vi .

Пример 1. Для н-графа, изображённого на рисунке 8, построить матрицы смежности и инцидентности.

6

Решение. Для построения матрицы смежности согласно определению сначала заполним следующую таблицу

	v1	v2	v3	v4	v5	v6	v7	(vi )
v1	0	1	1	0	0	0	0	2
v2	1	0	1	1	0	1	0	4
v3	1	1	0	1	1	0	0	4
v4	0	1	1	0	0	1	0	3
v5	0	0	1	0	0	1	1	3
v6	0	1	0	1	1	0	1	4
v7	0	0	0	0	1	1	0	2

Теперь оформим таблицу в виде матрицы смежности
0		1	1	0	0	0	0
	1	0	1	1	0	1	0
	1	1	0	1	1	0	0
S (G) 0 1			1	0 0 1			0 .
	0	0	1	0	0	1	1
	0	1	0	1	1	0	1
	0	0	0	0	1	1	0

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

		1	2	3	4		5			6	7		8			9	10			11	(vi )
	v1	1	1	0	0		0			0		0	0			0		0		0	2
	v2	1	0	1	1		0			0		1	0			0		0		0	4
	v3	0	1	1	0		1			1		0	0			0		0		0	4
	v4	0	0	0	1		1			0		0	1			0		0		0	3
	v5	0	0	0	0		0			1		0	0			1		1		0	3
	v6	0	0	0	0		0			0		1	1			1		0		1	4
	v7	0	0	0	0		0			0		0	0			0		1		1	2
А затем саму матрицу инцидентности
					1		1	0		0	0	0	0	0		0	0	0
						1	0	1		1	0	0	1	0		0	0	0
						0	1	1		0	1	1	0	0		0	0	0
				In(G) 0 0 0 1 1 0 0 1 0													0	0 .
						0	0	0		0	0	1	0	0		1	1	0
						0	0	0		0	0	0	1	1		1	0	1
						0	0	0		0	0	0	0	0		0	1	1

Пример 2. Для орграфа, изображённого на рисунке 9, построить матрицы смежности и инцидентности.

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

7

	v1	v2	v3	v4	v5	v6	v7	(v )
								i
v1	0	1	1	0	0	0	0	2
v2	0	0	1	0	0	1	0	2
v3	0	0	0	1	0	0	0	1
v4	0	1	0	0	0	0	0	1
v5	0	0	1	0	0	0	1	2
v6	0	0	0	1	1	0	0	2
v7	0	0	0	0	0	1	0	1
(vi )	0	2	3	2	1	2	1

0		1	1	0	0	0	0
	0	0	1	0	0	1	0
	0	0	0	1	0	0	0
S([D]) 0 1 0 0					0	0	0 .
	0	0	1	0	0	0	1
	0	0	0	1	1	0	0
	0	0	0	0	0	1	0

Построим матрицу инцидентности согласно её определению

	1	2	3	4		5	6		7				8		9	10		11	(vi )			(vi )
v1	1	1	0	0		0	0			0			0		0		0	0		2		0
v2	-1	0	1	-1		0	0			1			0		0		0	0		2		2
v3	0	-1	-1	0		1	-1			0			0		0		0	0		1		3
v4	0	0	0	1		-1	0			0			-1		0		0	0		1		2
v5	0	0	0	0		0	1			0			0		-1		1	0		2		1
v6	0	0	0	0		0	0			-1			1		1		0	-1		2		2
v7	0	0	0	0		0	0			0			0		0		-1	1		1		1
					1		1	0			0		0		0	0	0	0	0	0
						1	0	1		1 0					0	1	0	0	0	0
						0	1	1 0 1							1	0	0	0	0	0
			In([D]) 0				0	0			1		1		0	0	1 0		0	0 .
						0	0	0			0		0		1	0	0 1		1	0
						0	0	0			0		0		0	1 1		1	0	1
						0	0	0			0		0		0	0	0	0	1 1

4. Степени вершин

Степень (v) вершины v – число ребер, инцидентных вершине v. Геометрически, степень вершины – число ребер, сходящихся в этой вершине.

Рассмотрим сумму степеней всех вершин графа. Каждое ребро вносит в эту сумму двойку.

Лемма о рукопожатиях. Сумма степеней всех вершин н-графа равна удвоенному числу ребер графа:

8

(v) 2 | E | .

v V

Следствие. В н-графе число вершин нечетной степени четно.

Понятие степени вершины и лемма о рукопожатиях сохраняются для мульти- и псевдографов. При этом каждая петля вносит в степень соответствующей вершины двойку.

В орграфе различают два вида степени вершины: (v) – полустепень исхода – число дуг, исходящих из вершины v, (v) – полустепень захода – число дуг, входящих в вершину v.

Тогда обычная степень вершины (v) (v) (v) .

Теорема (о сумме полустепеней вершин). Сумма полустепеней исхода всех вершин орграфа равна сумме полустепеней захода и равна числу его дуг:

(v)	(v) | E | .
v V	v V

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

Пример 1. Определить степени вершин н-графа на рисунке 8.

Решение. Поскольку степень вершины определяется количеством принадлежащих ей ре-

бер, то получим: (v1) 2, (v2 ) 4, (v3 ) 4, (v4 ) 3, (v5 ) 3, (v6 ) 4, (v7 ) 2, что совпадает с результатами, полученными в таблицах смежности и ицидентности.

Пример 2. Определить полустепени вершин орграфа на рисунке 9.

Решение. Полустепень исхода вершины определяется числом дуг, исходящих из неё, по-

этому: (v ) 2 , (v			2	) 2 ,	(v	) 1, (v			4	) 1, (v			5	) 2 ,	(v	6	) 2 ,	(v	7	) 1. Полу-
1					3
степени захода каждой вершины равны числу дуг,												входящих в неё:					(v ) 0 ,			(v	2	) 2 ,
																	1
(v ) 3 , (v	4	) 2 ,	(v ) 1,			(v	6	) 2 ,	(v		7	) 1.
3				5

5. Расстояния в графе

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

Маршрут (путь) из v в w называется минимальным, если он имеет наименьшую длину среди всех маршрутов (путей) из v в w.

Заметим, что если вершины можно соединить маршрутом, то существует и минимальный маршрут, минимальная простая цепь, соединяющая эти вершины. Если v w и не существует маршрута, соединяющего v и w, то говорят, что вершина w не достижима из v.

Пусть

длина минимальной простой цепи из v в w, d (v, w)

, если не существует цепи из v в w.

Будем считать, что d(v, v) 0 . Величина d (v, w) называется расстоянием между вершина-

ми v и w.

Расстояние в графе удовлетворяют аксиомам метрики:

1)d(v, w) 0 , при этом d(v, w) 0 v w ;

2)d(v, w) d(w,v) (для н-графа);

9

3)d(v, w) d(v, z) d(z, v) (правило треугольника)

4)d(v, w) (в связном н-графе).

Пусть – связный граф.

Диаметром графа называется величина

d ( ) max d (u, v) .

u,v V

Пусть v – произвольная вершина .

Максимальным удалением (эксцентриситетом) в графе от вершины v называется вели-

чина

r(v) max d (v, ) .V

Радиусом графа называется величина

r( ) min r(v) . v V

Центром графа называется любая вершина v V такая, что r(v) r( ) .

В нагруженном графе каждому ребру (дуге) E поставлено в соответствие некоторое действительное число ( ) , которое будем называть длиной или весом ребра (дуги).

Заметим, что ненагруженный граф является частным случаем нагруженного графа, в котором веса всех ребер (дуг) равны 1.

Матрицей длин или весов ребер (дуг) нагруженного графа называется квадратная матрица C (cij ) порядка n, строки и столбцы которой соответствуют вершинам графа, а элементы определяются следующим условием:

(	ij	), если	ij	E,
cij
, если ij E,
здесь ij vi , v j – ребро (дуга), соединяющее вершины vi				и v j (для орграфа дуга из vi в v j ).

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

Маршрут (путь) в нагруженном графе из v в w называется минимальным, если он имеет наименьшую длину среди всех маршрутов (путей) из v в w.

Расстояние между двумя вершинами нагруженного графа d (v, w) определяется так же, как для ненагруженного графа.

Матрицей расстояний нагруженного графа называется квадратная матрица порядка n с элементами dij d(vi , v j ), (vi , v j ) E .

Пример 1. Составить матрицу длин ребер нагруженного н-графа на рисунке 10.

10