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

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

	G (V , R) , V {a1, a2 , a3 , a4 , a5},		R {u1,u2 ,u3 ,u4 ,u5 ,u6 ,u7} .
	fV :V Sv ,	SV ={Смоленск, Москва, Рязань, Орел, Брянск}.
	fR : R SR , SR ={400, 190, 360, 130, 250, 390, 360}.
	Определение 16.2. Пусть G (V , R)			– взвешенный связный неорг-
раф,	V {a1 , a2 ,..., an }. Матрицей весов графа G называется матрица W
n-го порядка вида		W (wij ) , где wij	равен весу ребра (ai , a j ) , если
(ai , a j ) R ; wij , если (ai , a j ) R .
	Определение 16.3. Пусть G (V , R)			– взвешенный связный неорг-
раф,	W (wij ) – матрица весов графа G,			(a1 , a2 ,..., ak ) (1)	– маршрут
		k 1
графа G. Число		w wi(i 1) , где	wi(i 1) – вес ребра		(ai , ai 1 ),

i 1

i1, k 1, называется весом маршрута (1), т.е. вес маршрута есть сумма

весов всех входящих в него ребер.

Определение 16.4. Пусть G (V , R) – взвешенный связный неорг-

раф. Взвешенным расстоянием между вершинами a и b графа G назы-

вается наименьший из весов всех (a,b) -маршрутов графа G и обозначается dW (a,b) .

71

Определение 16.5. Взвешенным эксцентриситетом вершины a

взвешенного	связного			неорграфа	G	называется	число
eW (a) max{ dW (a,b)			b V } .

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

1.Взвешенным радиусом взвешенного связного неорграфа G называется число rW (G) min{ eW (a) a V }.

2.Взвешенным диаметром взвешенного связного неорграфа G называ-

ется число dW (G) max{ eW (a) a V }. Определение 16.7.

1.Вершина a взвешенного связного неорграфа G называется взвешен-

ной центральной вершиной, если eW (a) rW (G) .

2.Вершина a взвешенного связного неорграфа G называется взвешен-

ной периферийной вершиной, если eW (a) dW (G) .

Пример 16.2. Для графа G из примера 16.1 найдем 1) матрицу весов, 2) взвешенные расстояния между вершинами, 3) взвешенные эксцентриситеты вершин, 4) взвешенный радиус и взвешенный диаметр графа G, 5) взвешенные центральные и взвешенные периферийные вершины графа G.

1) Матрица весов графа G:

			400			250
		400		190	360	390
W			190		360
			360	360		130
		250	390		130
								.

2) Взвешенные расстояния между вершинами графа G:

d	(a , a ) 400 ,		d	(a , a ) 190 ,			d	(a , a			4	) 360 ,
W	1	2	W		2	3	W		3
d	(a ,a ) 590 ,		d	(a		, a ) 360 ,	d	(a , a ) 490 ,
					2		W		3	5
W	1	3	W			4
			d	(a , a ) 390 ,			d	(a	4	,a ) 130 .
			W		2	5	W			5
						72

dW (a1 ,a4 ) 380 , dW (a1 ,a5 ) 250 ,

3) Взвешенные эксцентриситеты вершин графа G:

eW (a1 ) 590 , eW (a2 ) 400 , eW (a3 ) 590 , eW (a4 ) 380 , eW (a5 ) 490 .

4) Взвешенный радиус и взвешенный диаметр графа G: rW (G) eW (a4 ) 380 ,

dW (G) eW (a1 ) eW (a3 ) 590 .

5) Взвешенная центральная вершина графа G: a4; взвешенные периферийные вершины графа G: a1, a3.

§ 17. Сети

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

определение сети;

потоки в сетях: пропускная способность дуги, поток, условие сохранения потока, остаточная пропускная способность дуги, пропускная способность (величина) разреза;

теорема Форда-Фалкерсона о величине максимального потока в сети;

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

сети Петри.

Определение 17.1. Сетью называется взвешенный ориентированный граф.

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

73

Определение 17.2. Пусть G=(V,R) – взвешенный связный ориентированный граф без петель, имеющий единственный источник s и единственный сток t.

1.Вес wu дуги u R называется пропускной способностью дуги u.

2.Функция , определенная на множестве R, называется потоком сети G, если выполняется два условия:

а) u R : 0 u wu ;

б) a V \ s,t : b V (a,b) b v (b, a) (1).

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

3. Величина u wu u называется остаточной пропускной способностью дуги u.

4.Дуга u R называется насыщенной, если w u .

5.Пусть V1, V2 – разбиение множества V. Множество дуг из R, начала которых принадлежат V1, а концы – V2, называется ориентированным разрезом сети G и обозначается (V1→V2).

6.Пропускной способностью или величиной разреза (V1→V2) называ-

ется сумма пропускных способностей всех входящих в него дуг, и

обозначается w(V1→V2), т.е. w(V1→V2)= a V1,b V2 w(a,b) .

Теорема 17.1 (теорема Форда-Фалкерсона). Для любой сети с од-

ним источником и одним стоком величина максимального потока в сети от источника к стоку равна пропускной способности минимального разреза.

Понятие сетевого планирования

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

74

ров. Основными понятиями сетевого планирования являются понятия работы и события.

Работа – это любые действия, сопровождающиеся затратами ресурсов и времени и приводящие к определенным результатам. Событие

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

Сети Петри

Определение 16.9. Двудольный ориентированный граф G=(V,R) с долями Р и Т называется сетью Петри, если задано множество таких функций М, что каждая функция M ставит в соответствие каждому элементу множества Р неотрицательное целое число. Множество Р назы-

вается множеством позиций сети G, а множество Т – множеством пе-

реходов сети G. Функция М называется разметкой сети G.

Каждая позиция в сети Петри обозначается кружком, а каждый переход – вертикальной линией. Если р – позиция, то f(р) называется разметкой позиции р. Разметка графа G изображается с помощью больших черных точек, называемых метками, помещенных в кружки, которые обозначают позиции. Если кружок позиции р пуст, это означает, что в р меток нет, поэтому f(p) = 0.

Пример 16.3. Сеть Петри G, имеет две позиции р1 и р2 и один переход – t1. Позиция р1 содержит одну метку, а позиция р2 меток не содержит.

G

75

Сети Петри находят широкое применение в моделировании параллельных процессов: в моделировании компонентов компьютера, параллельных вычислений, в робототехнике и др.

Срабатыванием перехода t называется удаление одной метки из каждой позиции pi такой, что имеется ориентированное ребро из pi в t, и добавление метки в каждую позицию pj такую, что имеется ориентированное ребро из t в pj. Например, срабатывание t1 в примере 16.3 приводит к следующей сети Петри:

Пример 16.4.
Сеть Петри G:	Результат срабатывания перехода t:

Переход t может сработать, когда каждая позиция pi такая, что имеется ориентированное ребро из pi в t, содержит метку. Когда такая ситуация имеет место, говорят, что переход t разрешен. Срабатывание перехода предполагается мгновенным и может произойти в любой момент, когда переход разрешен. Возможно, что в некоторый момент времени более, чем один переход будет разрешен. В этом случае неизвестно, какой из переходов сработает первым. Сети Петри используются для проверки работоспособности системы даже в условиях такой неопределенности.

76

Таким образом, сети Петри представляют собой эффективное средство для нахождения дефектов в системе.

§ 18. Устойчивые множества и покрытия

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

независимое (внутренне устойчивое) множество вершин графа;

максимальное и наибольшее независимые множества;

число вершинной независимости (неплотность) графа и его оценка;

доминирующее (внешне устойчивое) множество вершин;

минимальное и наименьшее доминирующие множества;

число доминирования графа;

теорема Рамсея;

полностью зависимое множество;

покрывающие множества вершин и ребер;

числа вершинного и реберного покрытия;

связь чисел независимости и покрытий;

определение клики графа, максимальная и наибольшая клики графа;

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

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

максимальное, полное, совершенное паросочетания;

теорема Холла о паросочетаниях в двудольном графе.

Определение 18.1. Пусть G=(V,R) – граф.

1.Множество V1 V называется независимым (внутренне устойчивым),

если никакие две вершины из V1 не являются смежными.

2.Независимое множество V1 называется максимальным, если оно не является собственным подмножеством никакого другого независимого множества. Наибольшее по мощности независимое множество называ-

ется наибольшим.

3.Множество R1 R называется независимым (паросочетанием), если никакие два ребра из R1 не являются смежными.

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

77

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

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

1.Число вершин в наибольшем независимом множестве графа G называ-

ется числом (вершинной) независимости или неплотностью графа

G и обозначается 0 (G) .

2.Число ребер в наибольшем независимом множестве графа G называет-

ся числом (реберной) независимости графа G и обозначается 1 (G) .

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

Для графа G наибольшими независимыми множествами вершин

являются {a1, a2, a3, a4, a5} и {a6, a7, a8, a9, a10}, максимальными незави-

симыми – {a1, a8, a7, a6}, {a2, a10, a7, a6}.

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

Теорема 18.1. Для любого графа G=(V,R )верно неравенство

0 (G) x V 1 deg x 1 .

Доказательство теоремы 18.1 дает алгоритм построения независимого множества M, такого что M x V 1 deg x 1 . Множество М

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

78

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

С понятием независимости в графе связано понятие доминирова-

ния.

Определение 18.3. Пусть G=(V,R ) – граф.

1.Подмножество V' V называется доминирующим (внешне устойчи-

вым), если каждая вершина из V\V' смежна с некоторой вершиной из V', т.е. каждая вершина графа G находится на расстоянии в одно ребро от доминирующего множества.

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

3.Доминирующее множество, имеющее наименьшую мощность, назы-

вается наименьшим.

4.Числом доминирования (числом внешней устойчивости) графа G

называется наименьшее число вершин, составляющих минимальное доминирующее множество.

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

Теорема 18.2. Независимое множество максимально тогда и только тогда, когда оно доминирующее.

Доказательство. Пусть V' V – максимальное независимое множество. Тогда не существует вершины a V \ V , не соединенной ребром, так как в противном случае множество a V также было бы независимым, но V максимально по условию. Отсюда следует, что V – незави-

79

симое доминирующие множество. Тогда никакую вершину a нельзя перевести из V \ V в V так, чтобы множество a V осталось независимым. Следовательно, V – максимальное множество. Теорема доказана.

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

Покрывающие множества

Говорят, что вершина покрывает инцидентные ей ребра, а ребро покрывает инцидентные ему вершины.

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

1.Покрывающим множеством вершин (вершинным покрытием) гра-

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

2.Числом вершинного покрытия графа G называется наименьшее число вершин во всех вершинных покрытиях графа G и обозначается 0 (G) .

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

1.Покрывающим множеством ребер (реберным покрытием) графа G

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

2.Числом реберного покрытия графа G называется наименьшее число ребер во всех реберных покрытиях графа G и обозначается 1(G) .

Теорема 18.3. Для любого нетривиального связного графа G n-го порядка справедливо равенство 0 (G) 0 (G) 1(G) 1(G) n .

Клики

Антиподом понятия независимого множества является понятие клики.

Определение 18.7. Пусть G=(V,R ) – граф.

1. Подмножество V' V называется кликой, если любые две вершины из V' являются смежными.

80