ДМ_Конспект

Пример. На рис. 22.6 пунктирами показаны фундаментальные сечения s1, s2,...,s6 по дереву T «большая медведица».

s1	s2		s4	5		s5
		s3	y4		y5
			4			6
1						s6
						y6
			y3			7
y1

2	y2	3

Рисунок 22.6

Определение. Фундаментальной матрицей сечений ST (по дереву T )

называется матрица, строками которой являются вектор-сечения, фундаментальные по дереву T . Выделенному дереву T на рисунке 4 отвечает фундаментальная матрица сечений, столбцы которой помечены номерами дуг всего графа, строки – номерами дуг дерева, точнее, номерами соответствующих фундаментальных сечений:

			2	3	4	5	6	7	8	9	10
		1
	1	1	0	0	0	0	0	1	0	0	0
	2	0	1	0	0	0	0	1	0	0	0
S 3		0 0 1 0 0 0 1 1 1 0
T	4	0	0	0	1	0	0	0	1	1	0
	5	0	0	0	0	1	0	0	0	1	0
	6	0	0	0	0	0	1	0	0	0	1

Определение. Фундаментальным циклом графа G (по дереву T )

называется всякий цикл, содержащий в точности одну дугу yi кодерева G \ T и ориентированный согласно с направлением дуги yi . Каждая дуга y кодерева однозначно задает фундаментальный цикл qy , который дуга y замыкает на

дереве T .

Определение. Фундаментальной матрицей циклов QT (по дереву T )

называется матрица, строки которой есть все фундаментальные вектор-циклы по дереву T . Если для графа на рисунке фундаментальные вектор-циклы

221

пометить номерами задающих дуг кодерева y7, у8, у9, у10 , то фундаментальная матрица циклов такова:

			2		3	4	5	6	7	8	9	10
		1
	7	1	1		1 0		0	0	1	0	0	0
Q 8		0 0			1	1 0		0	0	1	0	0
T	9	0	0		1	1	1 0		0	0	1	0
	10	0	0		0	0	0	1 0 0 0 1
Для произвольных матрицы				сечений			S	и	циклов			Q данного графа G

справедливо соотношение ортогональности: SQT 0; QST 0 .

22.1.5 Алгоритм построения фундаментальной системы циклов

1.Построить любое остовное дерево T исходного графа G .

2.Добавить к T некоторое ребро e , которое является ребром графа, но не принадлежит остову.

3.После такого добавления образуется цикл Ze .

4.Все циклы {Ze} (соответствующие всем ребрам, взятым не из остова)

образуют фундаментальную систему циклов.

22.2Раскраска графов

22.2.1Раскраска вершин

Определение. Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета – это числа 1,2,..., k . Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве 1,2,..., k . Раскраску можно также рассматривать как разбиение множества вершин V V1 V2 ... Vk , где Vi – множество вершин цвета i . Множества называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного

222

графа в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается G .

22.2.2 Хроматическое число

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

Пусть граф G не имеет петель; тогда G называется k - раскрашиваемым, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета. Если граф G является k -раскрашиваемым, но не является k 1 - раскрашиваемым, назовем его k -хроматическим, а число назовем хроматическим числом. На рис. 22.722изображен 4-хроматический (и, следовательно, k -раскрашиваемый граф при k 4 ) граф; цвета обозначены греческими буквами.

	b
a	a	c

d

Рисунок 22.7 – 4-х хроматический граф

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

Ясно, что Kn n , и, следовательно, легко построить графы со сколь угодно большим хроматическим числом. С другой стороны, нетрудно видеть, что G 1 тогда и только тогда, если G – вполне несвязный граф, и что

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

Теорема 22.1. Если наибольшая из степеней вершин графа G равна p , то этот граф p 1 -раскрашиваем. При этом хроматическое число графа равно

223

p 1 только в двух случаях: во-первых, если граф является полным и, вовторых, если p 2 и при этом данный граф содержит контур нечетной длины. Во всех остальных случаях хроматическое число графа не превосходит максимальной степени вершин.

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

этот граф p 1 -раскрашиваем, отсюда получится p 1 -раскраска для G , если окрасить вершину i цветом, отличным от тех, которыми окрашены смежные с ней вершины, а их не более чем p.

Теорема (Брукса). Пусть G – простой связный граф, не являющийся полным; если наибольшая из степеней его вершин равна p p 3 , то он p - раскрашиваем.

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

Выберем произвольную вершину i и удалим ее, вместе с инцидентными ей ребрами. Останется граф с n 1 вершинами, в котором наибольшая из степеней вершин не превосходит p . По предположению индукции этот граф p -раскрашиваем. Теперь окрасим вершину i в один из имеющихся p цветов.

Как и раньше, считаем, что смежные с i вершины i ,...,i		расположены вокруг
1	p
i по часовой стрелке и окрашены в различные цвета A1 , c2 ,...,cp .
Определяя подграфы Hij i j,1 i, j p , когда		ii ,i j лежат в разных

компонентах графа Hij . Таким образом, можно считать, что при любых данных i, j вершины ii ,i j связаны простой цепью, целиком лежащей в Hij . Обозначим компоненту графа Hij , содержащую вершины ii ,i j , через Cij .

Ясно, что если вершина ii – смежная более чем с одной вершиной цвета c j , то существует цвет, отличный от ci , не приписанный никакой из вершин,

смежных с ii . Тогда вершину ii можно окрасить в этот цвет, что, в свою очередь, позволит окрасить вершину i в цвет ci и закончить на этом

224

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

(отличная от ii и от i j ) должна иметь степень 2. Предположим, что i — первая вершина простой цепи из ii в i j , которая имеет степень больше 2; тогда u

можно перекрасить в цвет, отличный от ci или c j , нарушая тем самым свойство, что ii и i j связаны простой цепью, целиком лежащей в Cij . Поэтому мы можем считать, что для любых i и j компонента Cij состоит только из простой цепи, соединяющей вершину ii c i j .

Заметим теперь, что две простые цепи вида Cij и C jl , где i l , можно считать пересекающимися только в вершине i j , так как если u – другая точка пересечения, то ее можно перекрасить в цвет, отличный от ci или c j , или cl , а

это противоречит факту, что ii , i j связаны простой цепью.

Для завершения доказательства выберем (если это возможно) две несмежные вершины ii , i j и допустим, что u – вершина цвета c j , смежная с ii .

Поскольку Cil – простая цепь (для любого l j ), можно поменять между собой цвета вершин в этой цепи, не затрагивая раскраску остальной части графа. Но это приводит к противоречию, потому что тогда u будет общей вершиной простых цепей Cij и C jl . Отсюда следует, что нельзя выбрать две вершины ii и i j несмежными, и поэтому G должен быть полным графом K p 1 . А так как это не допускается условием теоремы, то все возможные случаи рассмотрены.

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

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

225

Определение. Если граф имеет хроматическое число G 2 , то его называют бихроматическим графом. Любое раскрашивание G 2 красками разбивает вершины на 2 множества X1, X 2 , посередине каждого множества вершины попарно несмежные (или независимы).

Х1	Х2

Рисунок 22.8 – Две плоскости бихроматического графа

Теорема Кенига. Граф G называется бихроматическим тогда и только тогда, когда все его циклы имеют четную длину.

Доказательство. Следующие доказательства графа G эквивалентные:

1.Все замкнутые маршруты имеют четную длину.

2.Все циклы имеют четную длину.

3.Все простые циклы имеют четную длину.

Пусть граф G бихроматический. Раскрашиваем его 2 цветами. Концы каждого цепи четной длины имеют одинаковый цвет, нечетной – разные, поэтому замкнутые маршруты (циклы) нечетной длины отсутствуют. Пусть все замкнутые маршруты графа G имеют четную длину. Разукрасим в цвет 1 а одну вершину x1 , потом в цвет 2 – ее окружение (множество смежных вершин), в цвет 1 – окружение вершин цвета 2 и т.д. За конечное число граф будет раскрашен в цвет 1 и 2.

22.2.3 Гипотеза о четырех красках

Уже сто с лишним лет математики пытаются доказать гипотезу четырех красок. В этом направлении был достигнут значительный прогресс. В печати появилось сообщение (K.Appel, W.Haken, Every planar map is four colorable,

Bull. of Amer. Math. Soc., 82, \No\,5 (sept. 1976)), что гипотезу четырех красок удалось обосновать с использованием ЭВМ.

226

Сформулируем без доказательства несколько относящихся к этой проблеме результатов.

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

2.Любой не содержащий треугольников планарный граф 3-раскрашиваем (теорема Греча).

3.Если попытаться доказать гипотезу четырех красок, то достаточно доказать ее для гамильтоновых планарных графов (довольно неожиданный результат Уитни).

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

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

b
			3
a	3	a 1	c
1
		2

d

Рисунок 22.9 – Граф 3-раскрашиваемый и вершинно 4-раскрашиваемый.

Теперь сформулируем гипотезу четырех красок для карт: всякая карта 4-раскрашиваема.

Теорема 22.2. Карта G является 2-раскрашиваемой тогда и только тогда, если G представляет собой эйлеров граф.

227

Доказательство. Любую вершину i из G должно окружать четное число
граней, так как их можно раскрасить в два цвета. Отсюда следует, что степень
каждой вершины четна, и поэтому G – эйлеров граф.
22.2.4 Двудольные и k -дольные графы
Определение.	Неориентированный				граф	G X , A		называют
двудольным, если множество его вершин X может быть разбито на такие два
подмножества X a и X b , что каждое ребро имеет один конец в X a , а другой в
X b (рис. 22.10,а).
Ориентированный		граф	G	называется		двудольным,		если	его
неориентированный двойник – двудольный граф (рис. 22.10,б,в).
Двудольный граф G X a X b , A называют полным, если для любых двух
вершин xi X a и x j X b существует ребро xi , x j в G X , A (рис. 22.10,г).
Хa					х1 «+»	х2 «+»	х3 «+»
		X2
X1
			X3

Хb X5	X4
	х4 «-»	х5 «-»	х6 «-»
	а	б

х2	«+»	х3 «+»	х1	х2	х3
х1

х5	х4	«-»	х4		х6
				х5

в	г

Рисунок 22.10 – Двудольные графы: а, б, в – двудольные графы; г – полный двудольный граф

228

Теорема о двудольности. Граф G X , A является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

Доказательство: смотри теорему Кенига о бихроматических графах.

22.3 Контрольные вопросы и задания

1.Дайте определение маршрута, пути, цепи, цикла в графе. Приведите практические примеры этих определений.

2.Дайте определение цикломатического числа. Охарактеризуйте его свойства.

3.Как задается цикломатическая матрица графа?

4.Что называется раскраской вершин графа.

5.Что называется хроматическим числом.

6.Какой граф является бихроматическим графом?

7.Приведите теорема Кенига о бихроматическом графе.

8.Что называется хроматическим классом G графа или индексом?

9.Сформулируйте гипотезу четырех красок для карт.

10.Какие графы являются двудольными и k -дольными?

ЛЕКЦИЯ 23. ТРАНСПОРТНЫЕ СЕТИ И ПОТОКИ. ИХ СВОЙСТВА

23.1 Кратчайшие расстояния и пути в графах

Пусть G – неориентированнный граф.

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

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

Определение. Цепью называется маршрут, в котором каждое его ребро встречается не более одного раза; вершины в цепи могут повторяться и более одного раза. Любой участок цепи является цепью. Нециклическая цепь является простой цепью, если в ней никакая вершина не повторяется.

229

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

23.2 Алгоритм Дейкстры поиска кратчайших путей

Алгоритм Дейкстры решает задачу о кратчайших путях из одной

вершины для взвешенного ориентированного графа			G (V , E)	с	исходной
вершиной s , в котором веса всех рѐбер неотрицательны ( c(u,v) 0					для всех
(u,v) E ).
Формальное объяснение
В	процессе работы алгоритма	Дейкстры поддерживается		множество
S V ,	состоящее из вершин v , для	которых (s,v)	уже найдено.		Алгоритм

выбирает вершину u V \ S с наименьшим d[u] , добавляет u к множеству S и производит релаксацию всех рѐбер, выходящих из u , после чего цикл повторяется. Вершины, не лежащие в S , хранятся в очереди Q с приоритетами, определяемыми значениями функции d . Предполагается, что граф задан с помощью списков смежных вершин.

Неформальное объяснение

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до s . Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины s полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от s до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

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

230