1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ

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

Граф может интерпретироваться либо как некоторая геометрическая фигура в пространстве, состоящая из точек и соединяющих их линий, либо как некоторый теоретико-множественный объект. Поэтому многочисленные определения понятия «граф» могут иметь либо геометрический, либо достаточно абстрактный теоретико-множественный смысл.

Определение 1.1. Множество X={x1, x2, …, xk, …} и набор E пар объектов вида {xi, xj} или (xi, xj) из множества X называется графом. Будем обозначать граф символом G.

Множество X объектов будем называть множеством вершин графа, а элементы множества E, т.е. множества пар вида {xi, xj} или (xi, xj), соответственно ребрами или дугами. Отдельное ребро графа G, например ek E, будем обозначать парой {xl, xm}, т.е. ek={xl, xm}. Использование фигурных скобок в данном случае означает, что пара {xl, xm} является неупорядоченной, т.е. роли не играет, какая из вершин в паре является начальной, а какая конечной. Если же в некоторой паре вершин, например (xp, xq), указаны начальная и конечная вершины, то говорят, что эта совокупность вершин определяет дугу графа. Таким образом, ребро – это неупорядоченная, а дуга – упорядоченная пара вершин. Возможны случаи, когда начальная и конечная вершины ребра (или дуги) совпадают, в этом случае говорят, что в графе имеется петля, например, {xn, xn}.

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

Таким образом, граф G определяется множеством своих вершин X, множеством ребер или дуг E и может обозначаться символами G(X, E). Однако в этом обозначении нет прямых указаний на то, какие вершины графа G связаны между собой какими именно ребрами.

Приведенное выше определение понятия «граф» в значительной степени является абстрактным, и поэтому для введения других понятий и опреде-

50

лений целесообразно иметь геометрическую интерпретацию понятия «граф», являющуюся более наглядной. С этой целью будем рассматривать в евклидовом пространстве определенного вида геометрические фигуры, состоящие из точек b1, b2, …, bk, …, также именуемых вершинами, и линий, являющихся либо дугами окружностей, либо отрезками прямых; каждая из этих линий объединяет вершины в пары, например, {bi, bj} или (bl, bm); возможны вырожденные ситуации, когда bi=bj, что соответствует уже рассмотренному понятию петли.

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

1.Любая замкнутая кривая линия, т.е. ei E, содержит одну и только одну точку из множества X (рис. 1.1, а).

2.Каждая разомкнутая линия ej E содержит ровно две точки xl, xm X, являющиеся ее концами (рис. 1.1, б).

3.Линии ei E и ej E не могут иметь общих точек, которые не принадлежали бы множеству X (рис. 1.1, в).

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

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

(bni, bng)↔(xi, xj), то bni↔xi, bnj↔xj, т.е. соответствующие кривые и ребра и G соединяют соответствующие вершины.

На рис. 1.2 представлена геометрическая реализация графа, имеющего че-

тыре вершины X={x1, x2, x3, x4} и шесть ребер E={e1, e2, e3, e4, e5, e6}, при-

чем e1={x1, x1}, e2={x1, x2}, e3={x2, x3}, e4={x1, x3}, e5={x1, x3} и e6={x4, x4}.

Если ребро e E геометрической реализации графа G(X, E) имеет своими концами вершины xi и xj, то говорят, что это ребро соединяет вершины xi и xj, т.е. e=(xi, xj); на рис. 1.2 петлями являются ребра e1 и e6. Пара (или большее число) ребер, соединяющих одни и те же вершины, например xi и xj, являются параллельными и называются кратными. На рис. 1.2 параллельными являются ребра e4 и e5. Вершины xi и xj геометрической реализации графа G(X, E), соединенные между собой хотя бы одним ребром, называются смежными. На рис. 1.2 смежными являются вершины x1 и x2,

51

x1 и x3, x2 и x3. Вершина графа, не смежная ни с какой другой вершиной этого графа (возможно, кроме себя самой), называется изолированной; изолированной является вершина x4 на рис. 1.2.

				xm		x4
					ei
				x3
		ei E
			ej E
	xk	xl	xl, xm X		ej	x5
				x2	x2, x3, x4, x5 X
	a		б		в
				Рис. 1.1
				x2
				e6
			e2	e3	x4
			e1	e4
			x1	e5	x3

Рис. 1.2

		x5
Ex−	=δ− (x5 ) = 3	Ex+	=δ+ (x5 ) = 2
5		5

Рис. 1.3

52

Аналогично два ребра геометрической реализации графа, имеющие хотя бы один общий конец (общую вершину), называются смежными. Смежными ребрами графа на рис. 1.2 являются, например, ребра e2 и e3, e1 и e5, e3 и e5 и т.д. Естественно, смежными являются параллельные ребра.

Таким образом, на множествах вершин X и ребер E неориентированного графа могут быть заданы отношения смежности.

Кроме отношения смежности, относящегося к элементам одного множества (например, множества вершин или множества ребер), может быть определено отображение инцидентности, относящееся к элементам различных множеств. Если ребро ek E геометрической реализации графа G(X, E) соединяет вершины xi и xj, xi, xj X, т.е. ek=(xi, xj), то говорят, что ребро ek инцидентно вершинам xi и xj или вершины xi и xj инцидентны ребру ek. Таким образом, на множествах вершин X и ребер E графа может быть задано отображение инцидентности.

Следовательно, задать граф можно, указав множества его вершин X и ребер E и определив отношение смежности или отображение инцидентности Ф, т.е. G(X, E, Ф). В этом случае граф оказывается полностью определенным: символ Ф соответствует информации о том, какими ребрами соединены между собой какие вершины графа.

От неориентированного графа можно перейти к графу ориентированному, если на каждом ребре однозначно указать направление (например стрелкой). Две дуги орграфа G(X, E, Ф) , например e1 и e2, называются параллельными (или строго параллельными), если они инцидентны одним и тем

же вершинам xi и xj, при этом e1=(xi, xj) и e2=(xi, xj). Если же e1=(xi, xj) и e2=(xj, xi), то дуги e1 и e2 называются антипараллельными. Петли могут

быть ориентированы либо по часовой стрелке, либо против; однако ориентацию петли можно и не учитывать.

На основе рассмотренных понятий можно дать окончательные определения неориентированного и ориентированного графов.

Назовем абстрактным неориентированным графом G(X, E, Ф) совокупность непустого множества X, произвольного множества E, причем X∩E= , и произвольного отображения Ф:E→X&X. Элементы множеств X и E - соответственно вершины и ребра графа, а Ф – отображение инцидентности (отношение смежности). Неупорядоченные пары вершин могут обозначаться символами xi&xj.

Абстрактный ориентированный граф (орграф) G(X, E, Ф) представляет собой совокупность непустого множества X, произвольного множества E, причем такого, что X I E = , и произвольного отображения Ф: E→X×X; элементы множеств X и E являются соответственно вершинами и дугами

53

Ex−i

графа G, а Ф – отображение инцидентности (отношение смежности). Символом xixxj обозначены упорядоченные пары вершин.

Рассмотрим произвольный неориентированный граф, например тот, который показан на рис. 1.2, и выделим некоторую его вершину. Число ребер неориентированного графа G(X, E, Ф), инцидентных вершине xi (петля при этом учитывается дважды), называется степенью, или порядком этой вершины. Степень вершины можно обозначать символом δ(xi). Для вершины x1 графа, показанного на рис. 1.2, δ(x1)=5, для x2 δ(x2)=2, для x3 δ(x3)=3, а для изолированной вершины x4 δ(x4)=2.

Пусть G(X, E, Ф) – ориентированный граф. Если обозначить символом

множество дуг, входящих в вершину xi, а символом Ex+ - множество дуг,

i

выходящих из этой вершины, то тогда число Ex−i = δ− (xi ) будет называть-

ся полустепенью входа (захода) этой вершины, а число		E+		= δ	+	(x ) - по-
		xi				i

лустепенью выхода (исхода) вершины xi. Для вершины х5, показанной на рис. 1.3, δ−(x5 ) =3, а δ+ (x5 ) = 2 .

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

Теорема 1.1. Сумма степеней вершин неориентированного графа G(X, E, Ф) равна удвоенному числу его ребер, т.е. если

q = E , то ∑δ(x) = 2q .

x X

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

Теорема 1.2. В неориентированном графе G(X, E, Ф) число вершин нечетной степени четно.

Для доказательства этого утверждения разобьем множество вершин X графа на два подмножества X0 и X1, X = X 0 U X1, причем Х0 и Х1 – соот-

ветственно множества вершин графа, имеющих четные и нечетные степени. С учетом Теоремы 1.1 можно записать

∑δ(x) =∑δ(x) − ∑δ(x) =2q − ∑δ(x) .

x X1 x X x X 0 x X 0

В правой части этого выражения – разность двух целых четных чисел, поэтому и ∑δ(x) должна быть величиной четной. Но это может быть толь-

x x1

ко в том случае, если и X1 четно.

Граф G´(X´, E´) является частью графа G(X, E), если X´ E и E´ E, т.е. исходный граф содержит все вершины и ребра его части. Часть графа, которая наряду с некоторым подмножеством ребер (дуг) графа содержит и все

54

инцидентные им вершины, называется подграфом. Часть графа, которая наряду с некоторым подмножеством ребер (дуг) графа содержит и все вершины исходного графа (X´=X, E´ E), называется суграфом. Рассмотренные графы показаны на рис. 1.4.

x2

x1

	x3
x4
a	б	в	г
		Рис.1.4

Исходный граф по отношению к его подграфу называется надграфом, а по отношению к суграфу – сверхграфом. Совокупность всех ребер (дуг) графа, не принадлежащих его подграфу, вместе с инцидентными им вершинами образует дополнение подграфа. Говорят, что подграфы G´ (X´, E´) и G"(X", E") разделены ребрами (дугами), если они не имеют общих ребер

(дуг) (т.е. E´∩E"= ), и разделены вершинами, если у них нет общих вер-

шин X ′I X ′′ = .

Графы G(X, E, Ф) и G´ (X´, E´, Ф´) называются изоморфными, если X=X´, E=E´ и существует взаимно однозначное соответствие между их вершинами и ребрами, причем такое, что соответствующие вершины соединяются соответствующими ребрами. Для изоморфных графов G и G´ должны существовать такие нумерации их вершин и ребер, при которых одноименные вершины оказываются соединенными одноименными ребрами. С точки зрения понятия изоморфизма абстрактный граф и его геометрическая реализация оказываются изоморфными. Поэтому в соответствии с уже доказанной теоремой о реализуемости любого конечного графа в пространстве E3 вместо абстрактных конечных графов можно рассматривать их геометрические реализации. Другими словами, с графами можно выполнять операции, как с геометрическими объектами. На рис. 1.5 представлены изоморфные, а на рис. 1.6 – неизоморфные графы.

55

a

б

в

Рис. 1.5

а

б

Рис. 1.6

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

В некоторых случаях необходимо различать изоморфные графы, в связи с чем вводится понятие «помеченного графа». Граф с n вершинами называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, …, n.

Введем операцию подразделения ребра графа G(X, E). Пусть {xi, xj} – произвольное ребро этого графа и y – некоторый объект, не принадлежащий множеству X. Операция подразделения ребра {xi, xj} графа заключается в построении графа G´, множество вершин которого X´=X {y}, а множество ребер E´ содержит все ребра исходного графа, за исключением выде-

ленного ребра {xi, xj}, и два дополнительных новых ребра:

E′ = [E \ {xi , x j }]U{xi , y}U{y, x j }.

56

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

Графы G1 и G2 называются гомеоморфными, если существуют такие их подразделения, которые изоморфны. Другими словами, два графа гомеоморфны, если они изоморфны с точностью до вершин второй степени (второго порядка). На рис. 1.7 показаны гомеоморфные графы. Изоморфизм графа G(X, E, Ф) на себя называется автоморфизмом этого графа. Автоморфизм обладает теми же свойствами, что и изоморфизм.

а б

Рис. 1.7

2.ТИПЫ ГРАФОВ

Вп. 1 уже были определены графы неориентированные, ориентированные и смешанные.

Граф G(X, E, Ф) назовем конечным, если конечны множества его вершин X, а также ребер (или дуг) E.

		Назовем граф обыкновенным, если в нем отсут-
		ствуют петли и параллельные ребра (дуги) (рис. 2.1).
		Граф, имеющий параллельные ребра (дуги), называ-
		ется мультиграфом, а граф, в котором есть хотя бы
		одна петля, называется псевдографом (рис. 2.2 и 2.3).
		Если граф состоит только из изолированных вершин,
		то он именуется тривиальным; тривиальный граф
	Рис. 2.1	без петель называется нуль-графом (рис. 2.4 и 2.5).
		Если в обыкновенном неориентированном графе
		любые две вершины смежны, то такой граф имену-
	ется полным. Обыкновенный орграф называется полным, если для любых
	его вершин x и y существуют дуги ei и ej, такие, что ei=(x,y) и ej=(y,x). Если
	в каждую вершину полного графа добавить по петле, то получившийся
	граф будет называться насыщенным. На рис. 2.6, 2.7 и 2.8 показаны соот-

57

ветственно полные неориентированный, ориентированный и насыщенный графы.

Рис. 2.2. Рис. 2.3

x2	x3
	x4
x1	x5

Рис. 2.5

Рис. 2.6

x2	x3
x1	x4

Рис. 2.4.

Рис. 2.6

Рис. 2.7

Граф G(X, E, Ф) называется двудольным (или биграфом), если множество его вершин может быть разбито на два непересекающихся подмножества X1 и X2, причем X=X1 X2, таким образом, что каждое ребро графа имеет

58

	одну инцидентную ей вершину во множестве X1, а другую – во множестве
	X2. На рис. 2.9 показан двудольный граф. Чтобы подчеркнуть отмеченную
	особенность двудольных графов, их изображают, размещая множества
	вершин X1 и X2 либо в разных строках, либо в разных столбцах.
	В общем случае граф называется k-дольным, если множество его вершин
	можно разбить на k непересекающихся подмножеств X1, X2, …, Xk так, что
			не будет ребер, соединяющих вершины одного
	x 4	x 5	и того же подмножества.
			Граф, степени всех вершин которого одинако-
	x 3	x 6	вы и равны r, называется однородным (регу-
	x 2	x 7	лярным) графом степени r. Полный граф с n
			вершинами всегда является однородным гра-
	x 1	x 8	фом степени n-1. Граф третьей степени назы-
			вают кубическим; этот граф обладает рядом
	Рис. 2 .9		интересных свойств и, в частности, он всегда
			имеет четное число вершин. Можно выделить
			определенные классы графов, исследуя воз-
	можность их реализации в пространстве той или иной мерности.
	Будем говорить, что граф G(X, E, Ф) укладывается на поверхности S, если
	его можно так нарисовать на этой поверхности, что никакие два его ребра
	не пересекались бы. Другими словами граф реализован на некоторой по-
	верхности, если все его вершины и все внутренние точки ребер или дуг
	принадлежат этой поверхности.
	Теорема 2.1. Каждый конечный граф G(X, E, Ф) может быть реализован в
	трехмерном евклидовом пространстве.
	Доказательство. Пусть рассматриваемый граф содержит m вершин и n ре-
	бер (или дуг), т.е.	X = m и E = n . Выберем произвольную прямую и на
	ней разместим m точек – b1, b2, …, bm, поставив их во взаимно однознач-
	ное соответствие вершинам графа x1, x2, …, xm. Затем через выбранную
	прямую проведем пучок из n полуплоскостей, поставив в соответствие
	ребра графа G(X, E, Ф) и плоскости из пучка. Пусть e1 ={xi , x j }. В полу-

плоскости, соответствующей ребру e1, соединим точки bi и bj (вершины xi и xj графа) дугой окружности. Выполнив такое построение для всех остальных ребер графа в соответствующих полуплоскостях, получим в трехмерном евклидовом пространстве фигуру , являющуюся геометрической реализацией графа G(X, E, Ф). Это и доказывает теорему, так как граф и его геометрическая реализация оказываются изоморфными. Приведенная теорема не допускает понижения резмерности евклидова пространства, в котором мог бы быть реализован любой степени сложности конечный граф. Однако существует класс графов, реализуемых в пространстве E2. Граф, реализуемый в пространстве E2, называется планарным. Если граф реализован на плоскости, то все его вершины и все внут-

59

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

Теорема 2.2. (Понтрягина-Куратовского). Граф планарен, если ни один из его подграфов не гомеоморфен графам K5 и K3,3.

		На рис. 2.10 и 2.11 показаны планарные графы
		K5 и K3,3, играющие важную роль в теории пла-
		нарности и называемые графами Понтрягина-
		Куратовского. Граф K5 – это полный граф с пя-
		тью вершинами. Он является предельным гра-
		фом в том смысле, что если рассматривать по-
	Граф К3,3	следовательность полных графов, например, с
		семью, шестью, пятью и т.д. числом вершин, то
	Граф К5
	. 2.11	граф K5 будет последним в этой последова-
		тельности непланарным графом с минималь-
	Рис. 2 .1 0
		ным числом вершин. Полный граф с четырьмя
		вершинами является планарным. Кроме того,
	удаление хотя бы одного ребра из графа K5 делает его планарным.
	Двудольный граф K3,3 также непланарен. Этот граф является моделью из-
	вестной задачи о трех домах и трех колодцах: можно ли так проложить
	дорожки от всех домов к каждому колодцу, чтобы они не пересекались?
	Это соответствует ситуации. Когда поссорившиеся соседи не желают
	встречаться, но хотят пользоваться всеми колодцами.
	Строгое доказательство теоремы Понтрягина-Куратовского приведено в[].

3. МАТРИЦЫ ГРАФОВ

Кроме рассмотренных в разделах 1 и 2 теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов. Матричная форма задания графов обладает достаточной наглядностью при любой степени сложности графа и, что самое важное, позволяет автоматизировать процесс обработки информации, представленной в терминах теории графов, – любая матрица графа может быть введена в ЭВМ.

При задании графов в матричной форме могут учитываться либо отношения смежностей (вершин или ребер (дуг)), либо отображения инцидентно-

60

сти (вершин и ребер (дуг)). В связи с этим матрицы графов делятся на два основных класса: матрицы смежностей и матрицы инциденций. Определение 3.1. Матрицей смежности вершин неориентированного графа G называется квадратная матрица A(G)=[aij] порядка p=p(G) (p – количество вершин графа), элементы aij которой равны числу ребер, соединяющих вершины xi и xj.

		X4
	e8	e9
X3
	e7		X5
			e10
e6	e5
X2 e4
				X6
X1	e1
	e2
			X7
	e3	X8
	Рис.3.1
				x1	x2	x3	x4	x5	x6	x7	x8
		x1		2	0	0	0	1	0	1	0
		x2		0	0	1	0	0	1	1	0
A(G)		x3		0	1	0	1	0	1	0	0
		= x4		0	0	1	0	1	0	0	0
		x5		1	0	0	1	0	0	0	1
		x6		0	1	1	0	0	0	0	0
		x7		1	1	0	0	0	0	0	0
		x8		0	0	0	0	1	0	0	0

На рис. 3.1 приведен неориентированный граф G(X, E) и справа – соответствующая ему матрица смежностей вершин A(G).

Из определения 3.1 непосредственно вытекают основные свойства матриц этого вида.

1.Матрица смежностей вершин неориентированного графа A(G) является квадратной и симметричной относительно главной диагонали.

2.Элементами матрицы A(G) являются целые положительные числа и число ноль.

3.Сумма элементов матрицы A(G) по i-й строке (или по i-му столбцу)

равна степени соответствующей вершины δ(xi).

Из определения матрицы смежностей вершин неориентированного графа и ее основных свойств следуют некоторые особенности соответствия между графом G(X, E) и его матрицей A(G). На рис. 3.1 указана некоторая нумерация вершин графа; расположенная рядом матрица соответствует

61

именно этой нумерации. Если же в графе G(X, E), приведенном на этом рисунке, использовать другую нумерацию вершин (например, сдвинув ее относительно вершин по часовой стрелке), то это приведет к тому, что в матрице A(G) произойдет перестановка отдельных строк и столбцов. Поэтому говорят, что каждый неориентированный граф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная симметричная относительно главной диагонали матрица, элементами которой являются целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма неориентированный граф, матрицей смежностей вершин которого является данная матрица.

Рекомендуется самостоятельно построить матрицу смежностей вершин графа G(X, E), показанного на рис. 3.1, с использованием другой нумерации вершин и сравнить полученную при этом матрицу с матрицей смежностей вершин приведенного графа.

Определение 3.2. Матрицей смежности вершин ориентированного графа G называется квадратная матрица A(G)=[aij] порядка n (n – число вершин графа), элементы которой aij равны числу дуг, исходящих из вершины xi и заходящих в вершину xj.

	X4		e6
		X5
X3 e4			x1	x2	x3 x4	x5 x6 x7 x8

e2	e3	e5	x1	0	0	0	0	0	0	0	0
		e7	x2	0	0	0	0	0	1	0	0
e1		X6	x3	0	1	0	0	1	0	1	0
X2
		e8	A(G) = x4	1	0	0	0	0	0	0	0
		e9	x5	0	0	0	0	1	1	0	0
		e10
			x6	0	0	0	0	0	0	0	1
X1	e11	X7
			x7	0	0	0	0	0	1	0	0
		X8
			x8	1	0	0	0	1	0	0	0

Рис.3.2

На рис. 3.2 показан ориентированный граф G(X, E) и справа – матрица смежностей его вершин. Из определения следует, что сумма элементов i-й строки матрицы A(G) орграфа равна полустепени исхода δ+(xi), а по i-му столбцу – полустепени захода δ-(xi). По-прежнему элементы этой матрицы

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

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

62

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

Определение 3.3. Матрицей инцидентности неориентированного графа G называется матрица B(G)=[bij] размером (p x q) (p и q – количество вершин и ребер графа), элементы bij которой равны единице, если вершина xi инцидентна ребру ej и нулю, если соответствующие вершины и ребра не инцидентны.

Свойства матрицы инцидентности неориентированного графа.

1.Сумма элементов матрицы на i-й строке равна δ(xi).

2.Сумма элементов матрицы по i-му столбцы равна 2.

Матрица инцидентности графа, изображенного на рис. 3.1, а имеет

вид:

	e1	E2	e3	e4	e5	e6	e7	e8	e9	e10
x1	1	1	2	0	0	0	0	0	0	0
x2	0	0	0	1	1	1	0	0	0	0
x3	0	0	0	0	0	1	1	1	0	0
B(G) = x4	0	0	0	0	0	0	0	1	1	0
x5	1	0	0	0	0	0	0	0	1	1
x6	0	0	0	0	1	0	1	0	0	0
x7	0	1	0	1	0	0	0	0	0	0
x8	0	0	0	0	0	0	0	0	0	1

Следует отметить, что петле ej=(xi, xi) в матрицах этого вида соответствует j-й столбец, состоящий из нулей и одной единицы, расположенной на i-м месте. Ребру ek={xm, xn} соответствует в матрице инциденций k-й столбец, состоящий из нулей и двух единиц, расположенных на m-м и n-м местах. Нулевая строка матрицы соответствует изолированной вершине, а нулевой столбец – петле. Следует иметь ввиду, что нулевой столбец матрицы инцидентности лишь указывает на наличие петли, но не содержит информации о том, с какой именно вершиной связана эта петля.

Необходимо отметить, что между строками матрицы инцидентности B(G) существует очевидная зависимость. Так как каждый столбец этой матрицы содержит только два единичных элемента или состоит только из нулей, если столбец соответствует петле, то сумма по модулю 2 всех строк равна нулю. Поэтому без потери информации о графе вместо матрицы B(G) можно рассматривать сокращенную матрицу BoB (G), получаемую из B(G) вычеркиванием любой строки (чаще всего вычеркивается последняя строка). Таким образом, из p строк матрицы B(G) связного графа (см. п. 5)

63

одна строка всегда линейно зависима, т.е. ранг матрицы B(G) не может превышать p-1 (ранг матрицы B(G) в точности равен p-1).

Любое подмножество столбцов матрицы B(G) можно рассматривать как матрицу инцидентности B´(G) некоторого суграфа G´(X, E´), содержащего все вершины исходного графа и соответствующее выделенным столбцам подмножество E´CE его ребер. Все столбцы матрицы B´(G) линейно независимы тогда и только тогда, когда суграф G´(X, E´) не содержит циклов. Действительно, если совокупность ребер образует цикл, то каждая вершина инцидента четному числу ребер этого цикла. Следовательно, сумма по модулю 2 соответствующих столбцов дает нулевой столбец, что означает из зависимость. Если же суграф не содержит циклов, то он имеет по меньшей мере две (вообще, четное число) концевых вершин, каждая из которых инцидентна только одному ребру, являющемуся концевым. Поэтому сумма по модулю 2 соответствующих столбцов будет содержать два (или четное число) единичных элемента и, следовательно, совокупность этих столбцов независима.

В связном графе с p вершинами всегда можно выделить p-1 ребер так, чтобы они образовали суграф без циклов, представляющий собой дерево графа, являющееся каркасом (см. п. 7). Поэтому матрица инцидентности содержит не менее p-1 независимых столбцов. В то же время любой суграф, имеющий более p-1 ребер, обязательно содержит цикл, т.е. в матрице инциденций не может быть больше p-1 независимых столбцов. Отсюда следует, что матрица инцидентности связного графа содержит в точности p-1 независимых столбцов, и поэтому ее ранг равен p-1. Число ν=p-1 и определяет ранг графа.

Определение 3.4. Матрицей инцидентности орграфа G с p вершинами и q ребрами называется матрица B(G) = [bij] размером (p × q), элементы которой определяются следующим образом:

1, если вершина xi является началом дуги ej bij = -1, если вершина xi является концом дуги ej;0, если вершина xi не инцидентна дугу ej .

Ниже приведена матрица инцидентности графа, изображенного на рис. 3.2:

	e1	e2	e3	e4	e5	e6	e7	e8	e9	e10 e11
x1	0	0	0	0	-1 0		0	0	0	0	-1
x2	1	-1 0		0	0	0	0	0	0	0	0
x3	0	1	1	1	0	0	0	0	0	0	0
B(G) = x4	0	0	0	0	1	0	0	0	0	0	0

64

x5	0	0	0	-1 0		±1	1	0	0	-1 0
x6	-1	0	0	0	0	0	-1 1		-1	0	0
x7	0	0	-1 0		0	0	0	0	1	0	0
x8	0	0	0	0	0	0	0	-1 0		1	1

Матрица инцидентности орграфа G обладает следующими свойствами.

1.Сумма строк матрицы B(G) является нулевой строкой.

2.Любая строка матрицы B(G) является линейной комбинацией остальных строк.

3.Ранг матрицы B(G) равен p-1.

Определение 3.5. Матрицей смежности ребер неориентированного графа G называется квадратная матрица A*(G) = [a*ij] порядка q, элементы a*ij которой равны единице, если ребра ei и ej смежны, и нулю – в противном случае.

Для графа, изображенного на рис. 3.1, матрица смежности ребер имеет вид

	e1	e2	e3	e4	e5	e6	e7	e8	e9	e10
e1	0	1	1	0	0	0	0	0	1	1
e2	1	0	1	1	0	0	0	0	0	0
e3	1	1	2	0	0	0	0	0	0	0
e4	0	1	0	0	1	1	0	0	0	0
e5	0	0	0	1	0	1	1	0	0	0
A*(G) = e6	0	0	0	1	1	0	1	1	0	0
e7	0	0	0	0	1	1	0	1	0	0
e8	0	0	0	0	0	1	1	0	1	0
e9	1	0	0	0	0	0	0	1	0	1
e10	1	0	0	0	0	0	0	0	1	0

Очевидно, что матрица A*(G) смежности ребер неориентированного графа обладает теми же свойствами, что и матрица A(G) смежности вершин графа G. Таким образом, можно найти граф G*, матрица смежности вершин которого равна матрице A*(G) смежности ребер графа G.

G(X,E) → A*(G) ≡ A(G*) → G*.

Такой граф называется реберным, или сопряженным графом G. На рис. 3.3 приведен реберный граф (для неориентированного графа, показанного на рис. 3.1).

65

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

Обозначим через BT(G) матрицу, полученную транспонированием матрицы инцидентности B(G). Квадратная матрица A = B(G) BT(G) порядка p будет равна матрице смежности вершин графа, а квадратная матрица А* = BT(G) B(G) порядка q – матрице смежности ребер.

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

(дуг).

		x5
	x4	x6
x3		x7

x2	x8
x1	x9
	x10

Рис. 3.3

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

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

4.ОПЕРАЦИИ НА ГРАФАХ

66

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

Объединение графов.

Пусть G1(X1,E1) и G2(X2,E2) – произвольные графы. Объединением G1 G2 графов G1 и G2 называется граф с множеством вершин X1 X2, и с множеством ребер (дуг) E1 E2.

Рассмотрим операцию на примере графов G1(X1,E1) и G2(X2,E2), приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X1 = {x1, x2, x3} и X2 = {x2, x3, x4}, а множество вершин результирующего графа определится как X = X1 X2 = {x1, x2, x3, x4}. Аналогично определяем множества дуг графа:

E1 = {(x1, x2), (x1, x3), (x2, x1), (x3, x3)}. E2 = {(x2, x4), (x3, x2), (x4, x2)}.

E = {(x1, x2), (x1, x3), (x2, x1), (x3, x3), (x2, x4), (x3, x2), (x4, x2)}.

Результирующий граф G(X,E) = G1(X1,E1) G2(X2,E2) также приведен на рис. 4.1.

X2	X4	X2	X3
X2

X3		X3	X1
X1
			X4
G1	G2		G1 G2

Рис. 4.1

Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

1. G1 G2 = G2 G1 – свойство коммутативности; 2.G1 (G2 G3) = (G1 G2) G3 – свойство ассоциативности.

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

67

Теорема 4.1. Пусть G1 и G2 – два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин X, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1 G2 является матрица A = A1 A2, образованная поэлементным логическим сложением матриц A1 и A2.

Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G1(X1,E1) и G2(X2,E2) – графы без параллельных ребер и множества X1 и X2 вершин этих графов не совпадают. Пусть A1 и A2 – матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом.

В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как X1 X2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество X1 X2, а множество ребер (дуг) определяется множествами E1 для графа G’1 и E2 для графа G’2. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем добавления в них дополнительных столбцов и строк с нулевыми элементами. Применив к графам G’1 и G’2 теорему 4.1, найдем матрицу смежности вершин графа G’1 G’2 как A’1 A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1 X2, а множество ребер определяется, как E1 E2, что соответствует операции объединения графов.

Пример 4.1. Выполнить в матричной форме операцию объединения графов G1 и G2, представленных на рис. 4.1.

Составим матрицы смежности вершин графов.

x1	x1	x2	x3	x2	x2 x3 x4
	0	1	1		0	0	1
A1 = x2	1	0	0	A2 = x3	1	0	0
x3	0	0	1	x4	0	1	0

Множество вершин результирующего графа X1 X2 = {x1, x2, x3, x4}. Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.

x1	x1	x2	x3	x4	x1	x1	x2	x3	x4
	0	1	1	0		0	0	0	0
A’1 = x2	1	0	0	0	A’2 = x2	0	0	0	1
x3	0	0	1	0	x3	0	1	0	0
x4	0	0	0	0	x4	0	0	1	0

Матрица A = A’1 A’2 имеет вид

68

x1	X1	x2	x3	x4
	0	1	1	0
x2	1	0	0	1
A = A’1 A’2 = x3	0	1	1	0
x4	0	0	1	0

Полученная матрица смежности вершин A’1 A’2 соответствует графу G1 G2, изображенному на рис.4.1.

Пересечение графов

Пусть G1(X1,E1) и G2(X2,E2) – произвольные графы. Пересечением G1∩G2 графов G1 и G2 называется граф с множеством вершин X1∩X2 с множеством ребер (дуг) E = E1∩E2

Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

1.G1∩G2 = G2∩G1– свойство коммутативности;

2.G1∩ (G2∩G3) = (G1∩G2) ∩ G3 – свойство ассоциативности.

Для того чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X= ). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E= ). Пустой граф обозначается символом . Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X1∩X2= . В этом случае говорят о непересекающихся графах.

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

X1 = {x1, x2, x3}; X2 = {x1, x2, x3, x4};

X = X1∩X2 = {x1, x2, x3}.

Аналогично определяем множество E дуг результирующего графа:

E1 = {(x1, x2), (x1, x3), (x2, x1), (x2, x3), (x3, x2)};

E2 = {(x1, x3), (x2, x1), (x2, x3), (x2, x4), (x3, x1)};

E = E1∩E2 = {(x1, x3), (x2, x1)}.

69

Графы G1(X1,E1), G2(X2,E2) и их пересечение приведены на рис 4.2.

X2 X2 X2

X1	X3	X1	X3	X1	X3

G G2 G1∩G2

1

Рис. 4.2

Операция пересечения графов может быть выполнена в матричной форме. Теорема 4.2. Пусть G1 и G2 – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1∩G2 является матрица A = A1∩A2 образованная поэлементным логически умножением матриц A1 и A2.

Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин.

Пусть G1(X1,E1) и G2(X2,E2) – графы без параллельных ребер, множества X1 и X2 вершин графов не совпадают, а A1 и A2 – матрицы смежности вершин графов. Для таких графов операция пересечения может быть выполнена так.

В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как X1∩X2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество X1∩X2, а множество ребер (дуг) определяется множествами E’1 и E’2 всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество X1∩X2.

Применив к графам G’1 и G’2 теорему 4.2, найдем матрицу смежности вершин графа G’1∩G’2 как A’1∩A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1∩X2, а множество ребер определяется, как E1∩E2, что соответствует операции пересечения графов.

70

Пример 4.2. Выполнить в матричной форме операцию пересечения графов G1 и G2, представленных на рис. 4.2.

Составим матрицы смежности вершин исходных графов.

x1	x1	x2	x3	x1	x1	x2	x3	x4
	0	1	1		0	0	0	1
A1 = x2	1	0	1	A2 = x2	1	0	1	1
x3	0	1	0	x3	1	0	0	0
				x4	0	0	0	0

Находим множество вершин X результирующего графа.

X = X1∩X2 = {x1, x2, x3}.

Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.

x1	x1	x2	x3	x1	x1	x2	x3
	0	1	1		0	0	0
A’1 = x2	1	0	1	A’2 = x2	1	0	1
x3	0	1	0	x3	1	0	0

Найдем матрицу смежности вершин A = A1 ∩ A2

x1	x1	x2	x3
	0	0	0
A’1∩A’2 = x2	1	0	1
x3	0	0	0

Полученная матрица смежности вершин A’1 ∩ A’2 соответствует графу G1∩G2, изображенному на рис.4.2.

Композиция графов

Пусть G1(X,E1) и G2(X,E2) — два графа с одним и тем же множеством вершин X. Композицией G1(G2) графов G1 и G2 называется граф с множеством вершин E, в котором существует дуга (xi,xj) тогда и только тогда, когда существует дуга (xi,xk), принадлежащая множеству E1, и дуга (xk,xj), принадлежащая множеству E2.

Рассмотрим выполнение операции композиции G1(G2) на графах, изображенных на рис.4.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (xi, xk), принадлежащие графу G1, во втором — ребра (xk, xj), принадлежащие графу G3, а в третьем — результирующее ребро (xi, xj) для графа G1(G2).

71

G1	G2	G1(G2)
(x1,x2)	(x2,x1)	(x1,x1)
	(x2,x3)	(x1,x3)
(x1,x3)	(x3,x3)	(x1,x3)
(x2,x1)	(x1,x1)	(x2,x1)
	(x1,x3)	(x2,x3)

Заметим, что дуга (x1,x3) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x1,x3) учитыва-

ется только один раз, т.е. E = {(x1,x1), (x1,x3), (x2,x1), (x2,x3)}

На рис. 4.3 изображены графы G1 и G2 и их композиции G1(G2). На этом же рисунке изображен граф G2(G1). Рекомендуется самостоятельно построить граф G2(G1) и убедиться, что графы G1(G2) и G2(G1) не изоморфны.

X2

X2

X2

X2

X1		X3	X3
X3		X3
X1		X1	X1
G1	G2	G1(G2)	G2(G1)

Рис. 4.3.

Пусть А1 и A2 – матрицы смежности вершин графов G1(X,E1) и G(X,E2) соответственно. Рассмотрим матрицу A12 элементы aij которой вычисляется так:

n

aij = a1ik a2kj	(4.1)
k=1

где a1ik и a2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент aij равен 1, если в результирующем графе G1(G2) существует дуга, исходящая из вершины xi и заходящая xj, и нулю

– в противном случае.

Пример 4.3. Выполнить операцию композиции для графов, представленных на рис. 4.3.

72

Составим матрицы смежности вершин графов:

x1	x1	x2	x3	x1	x1	x2	x3
	0	1	1		1	0	1
A1 = x2	1	0	0	A2 = x2	1	0	1
x3	0	0	0	x3	0	0	1

Вычислив элементы матрицы согласно (4.1), получаем:

x1	x1	x2	x3	x1	x1	x2	x3
	1	0	2		0	1	1
= x2	1	0	1	A21 = x2	0	1	1
A12
x3	0	0	0	x3	0	0	0

Нетрудно убедиться, что полученным матрицам смежности вершин соответствуют графы G1(G2) и G2(G1), представленные на рис. 4.3.

Декартово произведение графов. Пусть G1(X,E1) и G2(Y,E2) — два графа.

Декартовым произведением G1(X,E1)×G2(Y,E2) графов G1(X,E1) и G2(X,E2) называется граф с множеством вершин X×Y, в котором дуга (ребро), идущая из вершины (xiyj) в (xkyl), существует тогда и только тогда когда существует дуга (xixk), принадлежащая множеству дуг E1 и j = l или когда существует дуга (yj,yl), принадлежащая множеству E2 и i = k.

Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4.4. Множество вершин Z результирующего графа определяется как декартово произведение множеств X×Y. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).

73

X2

Y2

Z4

Z6

Z5

				Z2
X1	Y1	Y3	Z1	Z3
G1		G2		G1×G2

Рис. 4.4.

Определим множество дуг результирующего графа. Для этого выделим группы вершин множества Z, компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X, и три группы, имеющие совпадающие компоненты из Y. Рассмотрим группу вершин результирующего графа,

которые имеют общую компоненту x1: z1=(x1y1), z2=(x1y1), z3=(x1y3). Согласно определению операции декартова произведения графов, множество

дуг между этими вершинами определяется связями между вершинами множества Y. Таким образом, дуга (y1,y1) в графе G2 определяет наличие дуги (z1,z1) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.

№	Группы вершин с совпадаю-	Дуги для не-	Дуга	Дуга
п.п.	щими компонентами	совпадаю-	(xiyj)→(xkyl)	(zα,zβ)
		щих компо-
		нент
1	z1=(x1y1), z2=(x1y2), z3=(x1y3)	(y1,y1)	(x1y1)→(x1y1)	(z1,z1)
		(y1,y2)	(x1y1)→(x1y2)	(z1,z2)
		(y2,y3)	(x1y2)→(x1y3)	(z2,z3)
		(y3,y1)	(x1y3)→(x1y1)	(z3,z1)
2	z4=(x2y1), z5=(x2y2), z6=(x2y3)	(y1,y1)	(x2y1)→(x2y1)	(z4,z4)
		(y1,y2)	(x2y1)→(x2y2)	(z4,z5)
		(y2,y3)	(x2y2)→(x2y3)	(z5,z6)
		(y3,y1)	(x2y3)→(x2y1)	(z6,z4)
3	z1=(x1y1), z4=(x2y1)	(x1,x2)	(x1y1)→(x2y1)	(z1,z4)

74

		(x2,x1)	(x2y1)→(x1y1)	(z4,z1)
4	z2=(x1y2), z5=(x2y2)	(x1,x2)	(x1y2)→(x2y2)	(z2,z5)
		(x2,x1)	(x1y2)→(x1y2)	(z5,z2)
5	Z3=(x1y3), z6=(x2y3)	(x1,x2)	(x1y3)→(x2y3)	(z3,z6)
		(x2,x1)	(x2y3)→(x1y3)	(z6,z3)

Граф G1× G2 изображен на рис. 4.4.

Операция декартова произведения обладает следующими свойства-

ми.

1.G1×G2 = G2×G1

2.G1×(G2×G3) = (G1×G2)×G3.

Операция декартова произведения графов может быть выполнена в матричной форме.

Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1×G2 имеет nx ny вершин, а его матрица смежности вершин - квадратная матрица размером (nx ny)× (nx ny). Обо-

значим через aαβ = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину zα=(xiyj) c zβ=(xkyl). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

aαβ = a(ij)(kl) = Kik a2,jl Kjl a1,ik,

(4.2)

где a1,ik, a2,jl – элементы матрицы смежности вершин графов G1 и G2 соответственно;

Kik – символ Кронекера, равный 1, если i=k, и нулю, если i≠k . Пример 4.4. Выполнить операцию декартова произведения на гра-

фах, приведенных на рис. 4.4.

Составим матрицы смежности вершин исходных графов.

x1	x1	x2	y1	y1	y2	y3
	0	1		1	1	0
A1 = x2	1	0	A2 = y2	0	0	1
			y3	1	0	0

Для построения матрицы смежности результирующего графа воспользуемся соотношением (4.2). В этом соотношении первое слагаемое Kik a2,jl указывает на наличие дуг для вершин, у которых совпадают компоненты из множества X. Для пояснения сказанного, рассмотрим вспомогательную матрицу Axy, в которой элементы, для которых Kik = 1, помече-

75

ны символом X. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A2 смежности вершин графа G2, так, как это показано для матрицы A*.

Axy =

	x1y1	x1y1
		a1,11 a2,11
	x1y2	a2,21
	A = x1y3	a2,31
	*
	x2y1	a1,21
	x2y2	0
	x2y3	0

			x1y1	x1y2	x1y3	x2y1	x2y2	x2y3
x1y1		X Y		X	X	Y	0	0
x1y2			X	X Y	X	0	Y	0
X1y3			X	X	X Y	0	0	Y
X2y1			Y	0	0	X Y	X	X
X2y2			0	Y	0	X	X Y	X
X2y3			0	0	Y	X	X	X Y
x1y2				x1y3	x2y1		x2y2	x2y3
a2,12				a2,13	a1,12
a1,11 a2,22				a2,11			a1,12
A2,32				a1,11 a2,33		0	0	a1,12
	0			0	a1,22 a2,11		a2,12	a2,13
a1,21				0	a2,21		a1,22 a2,22	a2,23
	0			a1,21	a2,31		a2,32	a1,22 a2,33

Второе слагаемое Kjl a1,ik соотношения (4.2) указывает на наличие дуг для групп вершин, у которых совпадают компоненты из множества Y. В матрице Axy элементы, для которых Kjl = 1 помечены символом Y. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A1 смежности вершин графа G1, так, как это показано для матрицы A*.

Заметим, что в матрицах Axy и A* на главной диагонали располагаются элементы, равные логической сумме значений элементов матриц смежности вершин обоих графов. Это определяется тем, что на главной диагонали расположены элементы, для которых Kik = Kjl = 1.

Таким образом, матрица смежности вершин результирующего графа принимает вид:

x1y1	x1y1 x1y2 x1y3 x2y1 x2y2 x2y3
	1	1	0	1	0	0
x1y2	0	0	1	0	1	0
A = x1y3	1	0	0	0	0	1
x2y1	1	0	0	1	1	0

76

x2y2	0	1	0	0	0	1
x2y3	0	0	1	1	0	0

Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1×G2, представленный на рис. 4.4

Операция произведения графов. Пусть G1(X,E1) и G2(Y,E2) - два графа. Произведением G1 G2 графов G1 и G2 называется граф с множеством вершин X×Y, а дуга из вершины (xi,yj) в вершину (xk,yl) существует тогда и только тогда, когда существуют дуги (xi,xk) E1 и (yj,yl) E2.

Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 4.5. Множество вершин Z результирующего графа определяется как декартово произведение множеств X×Y. Множество Z со-

держит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).

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

G1	G2	(x1,y1)→(x2,y1)	(zα, zβ)
(x1,x2)	(y1,y1)	(x1,y1)→(x2,y1)	(z1,z4)
	(y1,y2)	(x1,y1)→(x2,y2)	(z1,z5)
	(y2,y3)	(x1,y2)→(x2,y3)	(z2,z6)
	(y3,y2)	(x1,y3)→(x2,y2)	(z3,z5)
(x2,x1)	(y1,y1)	(x2,y1)→(x1,y1)	(z4,z1)
	(y1,y2)	(x2,y1)→(x1,y2)	(z4,z2)
	(y2,y3)	(x2,y2)→(x1,y3)	(z5,z3)
	(y3,y2)	(x2,y3)→(x1,y2)	(z6,z2)

Результирующий граф G1 G2 изображен на рис.4.5.

77

X2

Y3

Z4

Z5

Z6

X1	Y1	Y2	Z1	Z2	Z3
G1	G2			G1 •G2

Рис. 4.5.

Операция произведения обладает следующими свойствами.

1. G1 G2 = G2 G1.

2. G1 (G2 G3) = (G1 G2) G3.

Рассмотрим выполнение операции произведения графов в матричной форме.

Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1 G2 имеет nx ny вершин, а его матрица смежности вершин - квадратная матрица размером (nx ny)× (nx ny). Обо-

значим через aαβ = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину zα=(xiyj) c zβ=(xkyl). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

aαβ =a(ij)(kl) = a1,ik a2,jl,

(4.3)

де a1,ik, a1,ik – элементы матрицы смежности вершин графов G1 и G2 соответственно.

Пример 4.5. Выполнить операцию произведения на графах, приведенных на рис. 4.5.

Составим матрицы смежности вершин исходных графов.

x1	x1	x2	y1	y1	y2	y3
	0	1		1	1	0
A1 = x2	1	0	A2 = y2	0	0	1
			y3	0	1	0

Построим матрицу A смежности вершин результирующего графа, каждый элемент которой вычисляется согласно соотношению (4.3).

78

x1y1	x1y1	x1y2	x1y3	x2y1	x2y2	x2y3
	a1,11 a2,11	a1,11 a2,12	a1,11 a2,13	a1,12 a2,11	a1,12 a2,12	a1,12 a2,13
x1y2	a1,11 a2,21	a1,11 a2,22	a1,11 a2,23	a1,12 a2,21	a1,12 a2,22	a1,12 a2,23
A = x1y3	a1,11 a2,21	a1,11 a2,22	a1,11 a2,23	a1,12 a2,31	a1,12 a2,32	a1,12 a2,33
x2y1	a1,21 a2,11	a1,21 a2,12	a1,21 a2,13	a1,22 a2,11	a1,22 a2,12	a1,22 a2,13
x2y2	a1,21 a2,21	a1,21 a2,22	a1,21 a2,23	a1,12 a2,21	a1,12 a2,22	A1,12 a2,23
x2y3	a1,21 a2,31	a1,21 a2,32	a1,21 a2,33	a1,22 a2,31	a1,12 a2,32	A1,12 a2,33

Для удобства рассмотрения разделим матрицу A на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A2 на один из элементов a1,ij матрицы A1. С учетом этого матрицу A можно представить так:

x1y1 x1y2

A= x1y3 x2y1 x2y2 x2y3

x1y1 x1y2 x1y3 x2y1 x2y2 x2y3

a1,11 A2	a1,12 A2
a1,21 A2	a1,22 A2

Таким образом, матрица смежности вершин графа G1 G2 имеет вид:

x1y1	x1y1 x1y2 x1y3 x2y1 x2y2 x2y3
	0	0	0	1	1	0
x1y2	0	0	0	0	0	1
A = x1y3	0	0	0	0	1	0
x2y1	1	1	0	0	0	0
x2y2	0	0	1	0	0	0
x2y3	0	1	0	0	0	0

Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1 G2, представленный на рис. 4.5.

5. СВЯЗНЫЕ ГРАФЫ. КОМПОНЕНТА СВЯЗНОСТИ

Расcмотрим неориентированный граф G(X,E,Φ). Конечная последовательность ребер М = {e1, e2, . . . , ek} графа называется цепью (маршрутом) длины k, если существует такая последовательность вершин (x0, x1, . . . ,

хk), что Φ{ei} = (xi-1, xi), где i = 1, 2, . . . , k. Вершины x0 и xk называются соответственно начальной и конечной вершинами маршрута, остальные

вершины называются внутренними. Маршрут μ длины k может записы-

79

ваться как в виде последовательности ребер μ = {e1, e2, . . . , ek}, так и в ви-
де последовательности вершин μ= {x0, x1, . . . , xk}.
Цепь μ = {e1, e2, . . . , ek}, в которой все ребра различны, называется про-
стой. Цепь μ= {x0, x1, . . . , xk}, в которой все вершины различны, называет-
ся элементарной.
Пусть μ = {e1, e2, . . . , ek} — цепь в графе G; для некоторой последова-
тельности номеров i1, i2, . . . , ir, (где r ≥1, 1≤ i1<i2< ... <ik) последователь-
ность ребер (ei1, ei2, . . . ,eir) называется подцепью цепи μ; при этом говорят,
что цепь (ei1, ei2, . . . ,eir) выделена из цепи μ = {e1, e2, . . . , ek}.
Если цепь μ имеет начальную вершину, но не имеет конечной, или имеет
конечную вершину, но не имеет начальной, то она называется односто-
ронне бесконечной. Если цепь не имеет ни начальной, ни конечной вер-
шины, то она называется двусторонне бесконечной, замкнутой цепью, или
циклом.	Цепь называется нетривиальной, если она содержит хотя бы одно
ребро (дугу); для обеспечения общности рассуждений вводится понятие
нуль – цепи, не содержащей никаких ребер (дуг). Цикл называется про-
стым, если все его ребра различны, и элементарным, если все вершины,
через которые он проходит, различны.
Цепи μ и μ| считаются равными, если они имеют одинаковую длину и со-
стоят из одних и тех же ребер. В противном случае цепи μ и μ| считаются
различными.				Пример 5.1. В неориентированном
	x3
	e4			графе G, приведенном на рис. 5.1
	e2		x4
x2	e5			цепь μ1 = {e1, e2, e4, e8, e10} длиной 5
	e3	e8	e6	может быть задана как последова-
e1
		e7		тельностью ребер, так и последова-
x1				x5 тельностью вершин μ1 ={x1, x2, x3, x4,
			e9	x8, x6}. В этой цепи вершина x1 явля-
				ется начальной, а вершина x6 — ко-
		e10		нечной. Последовательность ребер
	e11		x6	(e2, e4, e8) — подцепь, выделенная из
				цепи μ1. Цепь μ2 = {e1, e2, e4, e7, e5,
x8
	x7
				e4, e7,e3, . . .} является односторонне
	Рис. 5.1			бесконечной.
				Цепь μ3 = {e4, e8, e10,e9, e6,e7} является
простой цепью, а μ4 = {e2, e4, e8, e10} — элементарной. Циклом является
замкнутая цепь μ5 ={e2, e5, e7, e8, e11, e3}, а последовательность μ6 = {e2, e4,

e8, e11, e3} образует элементарный цикл.

Теорема 5.1. Пусть G = (X,E) - неориентированный граф, A(G) – матрица смежности его вершин. Тогда элемент cij матрицы C = An(G) равен числу различных цепей длины n, соединяющих вершины xi и xj.

80

Доказательство. Если aik – число ребер, соединяющих вершины xi и xk, akj – число ребер, соединяющих вершины xk и xj, то произведение aik akj есть число различных маршрутов длины 2, соединяющих вершины xi и xj и проходящих через вершину xk. Тогда

p

cij = ∑aik akj , k =1

где p – число вершин графа G, есть число всех маршрутов длины 2, соединяющих вершины xi и xj. С другой стороны, сij есть элемент матрицы A2(G), поэтому для n = 2 теорема доказана.

Воспользуемся индукцией по n и предположим, что теорема верна для m=n-1. Так как An(G) = A(G) An-1(G), то приведенные выше рассуждения доказывают справедливость теоремы для m = n. Тем самым теорема доказана.

Следствие 5.1. В неориентированном графе G маршрут длиной n существует тогда и только тогда, когда An(G) ≠ 0.

Следствие 5.2. Если An(G)=0 для некоторого n>0, то в неориентированном графе G нет циклов.

Пусть G(X,E) — неориентированный граф. Две вершины xi и xj называются связными, если существует маршрут μ из вершины xi в вершину xj. Если маршрут μ проходит через вершину xk более одного раза, то можно, очевидно, удалить его циклический участок, и при этом оставшиеся ребра образуют маршрут μ°, связывающий xi и xj. Отсюда следует, что связные вершины связаны элементарной цепью. Граф называется связным, если любая пара вершин связана, т.е. любые две вершины соединены цепью. Пусть y - произвольная вершина неориентированного графа G = (X,E). Обозначим через Xy множество всех вершин графа G, которые можно соединить с y цепями (вершину y также включаем в множество Xy). Пусть Gy

— подграф графа G, множеством вершин которого является множество Xy, а множество ребер образуют все те ребра из E, концы которых принадлежат Xy. Построенный таким образом подграф Gy называется компонен-

той связности или связной компонентой графа G.

Теорема 5.2. Компоненты связности неориентированного графа G обладают следующими свойствами.

1.Gy ≠ 0 для любого y X.

2.Если Gy ≠ Gz, то Gy ∩ Gz = .

3.G = UGy .

y X

Доказательство. Так как y Xy, то первое свойство выполняется. Второе свойство докажем от противного. Если Gy ∩ Gz ≠ , то Xy ∩ Xz ≠ . Тогда

81

существует вершина x Xy ∩ Xz, которую можно соединить цепями как с y, так и с z. Отсюда следует, что вершины y и z можно соединить цепью, поэтому Xy = Xz. В результате получаем Gy = Gz, что и доказывает второе свойство.

Третье свойство следует из определения компоненты связности графа.

Следствие 5.3. Неориентированный граф связен тогда и только тогда, когда он состоит из одной компоненты связности.

Условия, эквивалентные связности графа, сформулированы в следующем утверждении.

Теорема 5.3. Неориентированный граф G = (X,E) связен тогда и только тогда, когда множество вершин X нельзя разбить на два непустых непересекающихся подмножества X1 и X2, которые не соединены ни одним ребром.

Доказательство. Необходимость указанного условия доказывается следующим образом. Если X1 и X2 — указанное в теореме разбиение, то любая цепь, соединяющая вершины x X1 и y X2, должна содержать хотя бы одно ребро, соединяющее множества X1 и X2. Поскольку таких ребер нет, то вершины x и y не могут быть соединены цепью. Это противоречит связности графа G, поэтому указанное разбиение не существует.

Доказательство достаточности следующее. Пусть G не связен, и пусть Gy

– его компонента связности со множеством вершин Xy. Тогда X ≠ Xy, множество X2 = X\Xy не пусто, X2 ∩ Xy = . Ясно, что X2 и Xy не соединены ни одним ребром. Это противоречит условию теоремы, поэтому граф G связен. Теорема доказана.

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

	A	0
A =	1	A	,
	0
		2

где A1 и A2 - квадратные матрицы.

Теорема 5.4. Пусть G – обыкновенный неориентированный граф с n вершинами и k компонентами связности. Тогда максимальное число ребер в графе G равно

q = 0.5(n −k)(n −k +1) .

Доказательство. Граф G имеет максимальное число ребер, если каждая компонента связности Gi, i = 1, 2, . . . , k имеет максимальное число ребер. Компонента связности Gi, имеющая максимальное число ребер, явля-

82

ется полным графом. Число ребер полного графа с ni вершинами равно 0,5 ni (ni - 1). Таким образом, максимальное число ребер графа G, компоненты связности Gi которого имеют по ni вершин, равно

k	k
q = 0,5∑ni (ni −1),	причем∑ni = n.
i−1	i=1

Полученное число зависит от того, как распределены вершины графа G по его компонентам связности. Предположим, что существует связные компоненты G1 и G2 графа G, имеющие более чем по одной вершине, т. е. n1 > 1 и n2 > 1. Пусть n1 ≤ n2. Рассмотрим граф G°, получаемый из графа G заменой компонент G1 и G2 на полные графы с (n1-1) и (n2+1) вершинами соответственно. Граф G° имеет n вершин и k компонент связности, а число его ребер равно

k

q'= 0,5(n1 −1)(n1 −2) +0.5(n2 +1)n2 +∑0,5ni (ni −1).

i=3

Тогда

q'−q = 0.5(n1 −1)(n1 −2) +0,5(n2 +1)n2 −

−0.5(n1 −1)n1 −0.5n2 (n2 −1) = n2 −n1 +1 > 0,

поэтому q’ > q. Итак, граф G° имеет больше ребер, чем граф G. Если и далее перестраивать граф указанным образом, то в результате получим граф, состоящий из k-1 изолированной вершины и одной полной компоненты связности с n - k + 1 вершиной. Этот граф имеет максимальное число ребер, равное 0,5 (n - k) (n - k + 1). Теорема доказана.

Следствие 5.5. Если обыкновенный неориентированный граф G с n вершинами имеет больше, чем 0,5 (n - 1) (n - 2) ребер, то он связен. Доказательство. Из теоремы 5.3 следует, что 0,5 (n - 1) (n - 2) — максимальное число ребер в обыкновенном графе с n вершинами и двумя компонентами связности. Если же в графе больше, чем 0,5 (n - 1) (n - 2) ребер, то число компонент в нем либо k=1, либо k ≥ 3. Случай k ≥ 3 противоречит условию, поэтому k = 1 и граф G связен.

Ориентированный граф G(X,E) называется сильно связным, если для любых его вершин x и y, x ≠ y, существуют пути μ и μ°, идущие соответственно из x в y и из y в x.

Рассмотрим теперь ориентированные графы. Пусть G(X,E,Φ) – орграф. Конечная последовательность дуг e1, e2, …, en графа G называется путем длиной n, или ориентированным маршрутом длины n, если существует такая последовательность вершин x0, x1, …, xn, что Φ(ei) = (xi-1,xi), где i =

83

x7

Рис. 5.2

1,2,…, . Путь μ записывается в виде μ ={e1, e2, …, en} или в виде μ = {x0, x1, …, xn }. В этом случае говорят, что путь состоит из дуг e1, e2, …, en, выходит из вершины x0 и заходит в вершину xn. Путь μ называется простым, если все его дуги различны, и элементарным, если все его вершины различны.

Пути μ и μ’ считаются равными, если они имеют одинаковую длину и состоят из одних и тех же дуг. В противном случае пути μ и μ’ считаются различными.

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

Теорема 5.5. Пусть G = (X,E) –орграф, A(G) – матрица смежности его вершин. Тогда элемент cij матрицы C = An(G) равен числу различных путей длиной n, выходящих из вершины xi и заходящих в вершину xj.

Следствие 5.6. В орграфе G путь длиной n существует тогда и только тогда, когда An(G) ≠ 0.

Следствие 5.7. Если An(G)=0 для некоторого n>0, то в орграфе G нет циклов.

Орграф G(X,E) называется сильно связным, если для любых его вершин x и y, x≠y, существуют пути μ и μ’, идущие соответственно из x в y и из y в x.

Теорема 5.6. Орграф G(X,E) сильно связен тогда и только тогда, когда он

						имеет контур, проходящий через все
			x3			вершины.
	x2				x4	Доказательство. Пусть x и y – две вер-
						шины графа G, причем x ≠ y. По условию
						теоремы существует путь μ1, идущий из
					x5	вершины x в вершину y.
	x1					Пусть X1 – множество вершин пути μ1.
						Если X1 = X, то достаточно взять путь μ°,
						идущий из x в y и получим контур μ1
	x8				x6	μ°, проходящий через все вершины гра-

фа. Если же X1 ≠ X, то X\X1 ≠ . Тогда для вершины z X\X1 строим путь μ, идущий из y в z, и получаем путь μ2 = μ1

μ. Пусть X2 – множество вершин пути μ2. Тогда X2 ≠ X1, X2 X1. Если продолжить этот процесс, то через конечное число шагов будет построен

84

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

Пример сильно связного графа приведен на рис. 5.2.

6.ДЕРЕВЬЯ И ИХ СВОЙСТВА

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

Определение 6.1. Деревом называется связный граф, не содержащий циклов. Любой (в том числе несвязный) граф без циклов называется ациклическим . Несвязный граф, каждая компонента связности которого является деревом, называется лесом. Можно сказать, что деревья являются компонентами леса. На рис. 6.1 изображены два дерева G1, G2 и лес G3.

G1

G2

G3

Рис. 6.1

Сформулируем основные свойства деревьев. Сделаем это в виде совокупности утверждений, которые эквивалентны между собой (т.е. из любого утверждения следует любое другое) [].

Теорема 6.1. Пусть G(X, E) – неориентированный граф с p вершинами и q ребрами. Тогда следующие утверждения эквивалентны.

1°. G есть дерево.

2°. Любые две различные вершины x и y графа G соединены единственной простой цепью.

3°. G – связный граф, утрачивающий это свойство при удалении любого из его ребер.

4°. G – связный граф и p = q + 1.

5°. G – ациклический граф и p = q + 1.

6°. G – ациклический граф, причем если любые две его вершины x и y соединить ребром e, то в полученном графе будет ровно один простой цикл.

85

Для доказательства теоремы достаточно доказать следующую цепочку следствий: 1° 2° 3° 4° 5° 6° 1°, так как это означает, что из любого утверждения 1° – 6° выводится любое другое.

1° 2°. Так как граф связен, то любые две его вершины можно соединить простой цепью. Пусть μ1 и μ2 - две различные простые цепи, соединяющие вершины x и y. Если цепи μ1 и μ2 не имеют общих вершин, за исключением вершин x и y, то μ1 Uμ2 есть простой цикл. Предположим, что це-

пи μ1 и μ2 имеют общие вершины, отличные от x и y. Пусть z – первая из таких вершин при движении от вершины x к вершине y и пусть μ1(x, z) и μ2(x, z) – части цепей μ1 и μ2, взятые от вершины x до вершины z. Тогда μ1(x, z) Uμ2 (x, z) - простой цикл. Это противоречит тому, что граф ацик-

личен, и поэтому μ1=μ2, т.е. утверждение 2° доказано.

2° 3°. Граф G – связен, поскольку любые две его различные вершины x и y соединены простой цепью. Возьмем некоторое ребро графа e = (x, y). Согласно 2° простая цепь μ={e} между вершинами x и y единственна. Если ребро e удалить, то вершины x и y будет невозможно соединить простой цепью, и полученный граф будет несвязным. Утверждение 3° доказано.

3° 4°. По условию 3° граф связен. Соотношение p = q + 1 докажем по индукции. Если граф имеет две вершины и удовлетворяет 3°, то он выглядит так:

x	e	y

В этом случае p = 2, q = 1 и соотношение p = q + 1 выполняется. Предположим теперь, что соотношение верно для всех графов, удовлетворяющих 3° и имеющих меньше, чем p вершин, и докажем его для графа G с p вершинами. Удалим из графа G произвольное ребро e. Тогда новый граф G´ будет несвязным и будет состоять из двух связных компонент G1 и G2. По предположению индукции имеем

p1 = q1 + 1, p2 = q2 + 1,

где pi – число вершин компоненты Gi, qi – число ее ребер. Следовательно, p = p1 + p2, q = q1 + q2 + 1,

поэтому p = q1 + q2 + 2 = q + 1, и свойство 4° доказано.

4° 5°. Предположим, что граф G, удовлетворяющий 4°, имеет простой цикл μ длиной l ≥ 1. Этот цикл содержит l вершин и l ребер. Для любой из p - l вершин, не принадлежащих циклу μ, существует инцидентное ей реб-

86

ро, лежащее на кратчайшей цепи ( т.е. цепи минимальной длины), идущей от данной вершины к некоторой вершине цикла μ. Все такие ребра попарно различны. Если вершины x1 и x2 инцидентны одному такому ребру e, то e = (x1, x2), и кратчайшая цепь μ1 для вершины x1 проходит через вершину x2, а кратчайшая цепь μ2 для вершины x2 проходит через вершину x1 (рис. 6.2). Это противоречит тому, что цепи μ1 и μ2 – кратчайшие. Общее число ребер q в графе G в этом случае не меньше, чем l + p – l = p, т.е. q ≥ p, что противоречит соотношению p = q + 1. Отсюда следует, что G – ациклический граф, и утверждение 5° доказано.

μ2

x1

x2

μ1

y2

y1

μ y

Рис. 6.2

5° 6°. Так как G – ациклический граф, то каждая его компонента связности Gi (i = 1, 2, …, k) является деревом. Для каждой компоненты Gi имеем

k	k
в соответствии с 5° pi = qi + 1, откуда ∑pi = ∑(qi +1), т.е. p = q + k. С
i=1	i=1

другой стороны, p = q + 1, поэтому k = 1, т.е. граф G связен. Таким образом, G – дерево. Тогда (см. 2°) любые две различные вершины x и y графа G соединены единственной простой цепью. Если добавить ребро между несмежными вершинами x и y, то оно образует с указанной цепью единственный простой цикл. Утверждение 6° доказано.

6° 1°. По условию 6° G – ациклический граф. Если граф G не является связным, то возьмем вершины x и y из различных компонент связности графа G и соединим их ребром e. Построенный граф G1(X , E U{e}) явля-

ется, как и граф G, ациклическим. Это противоречит свойству G, поэтому G – связный граф, и свойство 1° доказано. Таким образом, доказана и теорема 6.1.

Определение, аналогичное дереву, можно ввести и для орграфа. Определение 6.2. Орграф G(X, E) называется прадеревом или ориентированным деревом, растущим из корня x0, при следующих условиях:

87

1°. Неориентированный граф G', соответствующий графу G, является деревом.

2°. Единственная простая цепь между x0 и любой другой вершиной x графа G' является путем в орграфе G, идущим из вершины x0 в вершину x.

На рис. 6.3 изображено ориентированное дерево.

Рис. 6.3

В неориентированном графе G(X, E) вершина x называется концевой или висячей, если δ(x) = 1, т.е. если этой вершине инцидентно единственное ребро e. Это ребро также называется концевым или висячим. С висячими вершинами связана следующая теорема.

Теорема 6.2. В любом дереве G(X, E) с p ≥ 2 вершинами имеется не менее двух концевых вершин.

Доказательство. Пусть q – число ребер дерева G. В силу теоремы 6.1 p = q + 1. Кроме того, из теоремы 1.1 имеем

∑δ(x) = 2q .

x X

Таким образом, получаем
∑δ(x) = 2( p −1) .	(6.1)
x X
Предположим, что x0 – единственная концевая вершина в дереве G. Тогда
δ(x0) = 1, δ(x) ≥ 2, если x ≠ x0. Отсюда
∑δ(x) ≥ 2(n −1) +1.	(6.2)

x X

Неравенство (6.2) противоречит (6.1), поэтому либо концевых вершин нет, либо их по крайней мере две. Если концевых вершин в G нет, то δ(x) ≥ 2 для всех x X. Тогда

∑δ(x) ≥ 2 p .	(6.3)
x X

Неравенство (6.3) тоже противоречит (6.1). Отсюда следует, что концевых вершин в G две или больше. Теорема доказана.

Важным является вопрос о том, сколько существует деревьев с заданным числом вершин. Для деревьев с помеченными вершинами (на-

88

пример пронумерованными) или для помеченных деревьев ответ на этот вопрос дает следующая теорема.

Теорема 6.3. (А. Кэли, 1897 г.). Число помеченных деревьев с p вершинами равно pp-2.

Доказательство. Пусть G(X, E) – дерево с p помеченными вершинами. Для простоты предположим, что вершины пронумерованы в произвольном порядке числами 1, 2, …, p. Рассмотрим способ, позволяющий однозначно закодировать дерево G.

В соответствии с теоремой 6.2 дерево G имеет концевые вершины. Пусть x1 – первая концевая вершина в последовательности 1, 2, …, p и пусть e1 = (x1, y1) – соответствующее концевое ребро. Удалим из дерева вершину x1 и ребро e1. Получим новое дерево G1 с числом вершин p - 1. Найдем теперь первую концевую вершину x2 дерева G1 в последовательности вершин 1, 2, … …, p из множества {1, 2, …, p }\{x1}, далее возьмем концевое ребро e2 = (x2, y2) и удалим из G1 x2 и e2. Эту процедуру последовательно повторяем. Через (p - 2) шага остается дерево из двух вершин xp-1, yp-1 и одного ребра ep-1 = (xp-1, yp-1). Рассмотрим последовательность вершин

σ(G) = {y1, y2, …, yp-2}.

Очевидно, что по данному дереву последовательность строится однозначно. Покажем теперь, что по данной последовательности вершин σ (G) дерево G можно восстановить однозначно. В последовательности 1, 2, …, p существуют вершины, не принадлежащие σ (G). Выберем первую из них x1 и построим ребро e1 = (x1, y1). Затем удалим x1 из последовательности 1, 2, …, n и y1 удалим из σ(G). Аналогичным образом построим ребро e2 = (x2, y2). Продолжая этот процесс, мы однозначно восстановим дерево G. Рассмотрим пример.

Построение кода	Восстановление
σ(G)	σ(G) и список вершин

2

1		6
3		(2)
		7
	5
4

2

6 (2,6)

3

5

4

7

1

2

2

1

6

(2,6,5,5,6)

1,2,3,4,5,6,7

(6,5,5,6)

2,3,4,5,6,7

89

3		6
		(2,6,5)
4	5	7

6

4 (2,6,5,5)

5 7

6

(2,6,5,5,6)

5 7

	1	2
	3	6
		5
	1	2
		6
	3	5
	1	2
		6

3

5

4

7

(5,5,6)

3,4,5,6,7

(5,6) 4,5,6,7

(6) 5,6,7

Рассмотренный пример позволяет отметить следующие две особенности: 1° В списке σ(G) вершины могут повторяться.

2°. При восстановлении дерева последнее ребро соединяет вершину yp-2 и оставшуюся в списке 1, 2, …, p вершину не равную yp-2.

Итак, существует взаимно однозначное соответствие между множеством помеченных деревьев с p вершинами и множеством последовательностей вершин σ(G). Число таких последовательностей равно, очевидно, pp-2, что и требовалось доказать.

Отметим, что среди pp-2 помеченных деревьев с p вершинами могут быть и изоморфные.

Определение 6.3. Подграф G1(X1, E1) неориентированного графа G(X, E) называется каркасом, или остовным деревом графа G, если G1 – дерево и X = X1.

Теорема 6.4. Граф G(X, E) тогда и только тогда обладает каркасом, когда он связен.

Доказательство. Необходимость этого очевидна. Докажем достаточность. Пусть G(X, E) – связный граф. Выясним, есть ли в графе G такое ребро, удаление которого не нарушает связности графа G. Если таких ребер нет, то граф есть дерево в соответствии с теоремой 1. Если же такое ребро, например e, существует, то выбросим его и придем к графу G1(X, E\{e}). Затем указанную процедуру проделываем с графом G1 и т.д. Через конечное число шагов будет построен, очевидно, каркас графа G. Теорема доказана.

Доказательство теоремы дает алгоритм построения некоторого каркаса в связном графе. Однако связный граф может иметь несколько карка-

90