Учебное пособие 1920

Тетраэдр

Куб

Октаэдр

Додекаэдр

Икосаэдр

Рис. 6.5. Правильные многогранники и их графы

Рис. 6.6. Типы графов (слева направо): звезда, двудольный, трёхдольный

240

Три графа рис. 6.7 изоморфны. Графы (рис. 6.8) не изоморфны.

Рис. 6.7. Изоморфные графы

Рис. 6.8. Неизоморфные графы

Отношение изоморфизма графов имеет эквивалентность. Граф порядка п будет называться помеченным, если для его вершин имеются метки, т. е. номера 1, 2, ..., n. Равенство

помеченных графов G1=(X,V1) и G2=(X,V2) одного и того же порядка G1=G2 тогда, когда V1=V2.

На рис. 6.9 изображены помеченные графы.

x2		x2		x2
			x4
x1	x3	x1	x1	x3

Рис. 6.9. Помеченные графы

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

241

Граф, не имеющий петель и кратных ребер, называется простым.

Граф G=(X,V) называется симметрическим, если в V для дуги (xi,xj) существует противоположно ориентированная дуга (xj,хi). Граф определяется как антисимметрический, если каждая пара смежных вершин соединена в одном направлении и нет петль.

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

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

Реберным графом L(G) простого графа G называется граф, вершины которого взаимно однозначно сопоставлены ребрам графа G, и две вершины в L(G) смежны тогда, когда соответствующие им ребра смежны в G.

Орграф G' называется обратным к данному орграфу G, если он имеет те же вершины (как в G), а дуга (xi,xj) принадлежит G' тогда, когда дуга (xj,хi) принадлежит G.

6.3. Матричные представления графов

Структура графа определяется матрицей смежности. Матрицей смежности графа G=(X,V), |X|=n называется квадратная матрица A (aij )n n с элементами

1,	если вершины x ,и x	j	смежны;
	i
ai, j

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

Матрица смежности неориентированного графа симметрична. Если имеются кратные ребра, то aij - есть количество

242

ребер с вершинами xi и xj. Для орграфа аij – это количество дуг

( xi,xj).

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

По матрице смежности граф можно восстановить однозначно с точностью до изоморфизма.

Матрицей инцидентности графа G=(X,V), |Х|=п,|V|=m

называется матрица B (bij )n m .

1. Если G- ориентированный граф, то

1,если вершина xi -начальная вершина дуги vj;

bij -1,если вершина xi -конечная вершина дуги vj;

0,если вершина xi не инцидентна дуге vj;

2. Если G - неориентированный граф, то

1,	есливершина xi инцидентна ребру vj;
bij 0	впротивномслучае.
	6.4. Операции над графами

Рассмотрим операции над графами.

Бинарные операции

1. Объединение графов. Рассмотрим графы G=(X1,V1) и G=(X2,V2). Объединение графов G1 и G2 обозначаемое как G1 G2, представляет собой граф G3 =(X1 X2,V1 V2) , в котором множество его вершин будет объединением X1 и X2, множество ребер – объединением V1 и V2.

2. Пересечение графов G1 и G2. (G1 G2) - это граф G3=(X1 X2,V1 V2). При этом у графа G3 множество вершин состоит из вершин, входящих одновременно в графы G1 и G2, а множество ребер графа G3 состоит только из ребер, входящих одновременно в графы G1 и G2.

243

3. Кольцевой суммой G1 G2 графов G1 и G2 называется

граф G3 =(X1 X2,V1 V2), где V1 V2 = (V1\V2)Y(V2\V1).

4. Соединением графов G1+G2 называется граф

G3=(X1 X2,V1 V2 {(xi,xj) | xi X1, xj X2, xi xj}).

5. Произведением G1×G2 графов G1 и G2 называется граф G3 =(X1×X2,V), , в котором ((x1,y1), (x2,y2)) V тогда, ко-

гда x1=x2 и (y1,y2) V2, или y1=y2 и (x1, x2) V1.

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

Унарные операции

1. При удалении вершины из графа удаляются и все ин-

цидентные ей ребра (дуги). Пусть G=(X,V) – граф и x X. Удапостроить новый

лить вершину x из графа G -				это значит
граф			, в котором			и	получается из V
удалением всех ребер, инцидентных вершине x.
	= (	, )		= \{	}
	2. Пусть G=(X,V) – граф. Удалить ребро (дугу) v – это
значит построить новый граф				= ( ,		),	в котором	=

и= \{ }. . При удалении ребра (дуги) его концевые вершины не удаляются. Операцией, являющейся обратной к удалению ребра, будет добавление ребра.

3.Говорят, что вершины xi и xj в графе G отождествляются (сливаются), если они заменяются такой новой вершиной xk, что все ребра (дуги) графа, инцидентные xi и xj, становятся инцидентными новой вершине xk.

4.Стягивание ребра (дуги). Это операция удаления ребра

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

5.Пусть G=(X,V) – граф и v=(x,y) V.

	Подразбиение			ребра v - это построение		нового граф
( \{	} {(	,	),( ,	е. z – новая вершина) и
				)}.	означает	«внесение =в
= ( ,		),	=	{Эта} (топерация.

ребро новой вершины».

244

Граф =(X, ) будет дополнением простого графа, если

ребро (xi,xj) входит в , но не входит в V или две вершины

смежны в тогда, когда они не смежны в G.

Если G'=(X',V') будет подграфом графа G=(X,V), то граф G будет называться дополнением графа G' графа G.

6.5. Метрические характеристики графа

Пусть G=(X,U) - связный граф, а xi,xj - две его несовпадающие вершины. Длина кратчайшего маршрута, соединяющего вершины xi, xj (пути xi и xj), называется расстоянием между вершинами xi,xj и обозначается d(xi,xj), если вершины xi и xj не соединены маршрутом (путем). Для расстояния d(xi,xj) имеются аксиомы метрики:

1)d(xi,xj)=0;

2)d(xi,xj)≥ 0;

3)d(xi,xj)=0; тогда и только тогда, когда xi=xj;

4)d(xi,xj)= d(xj,xi) для симметрических графов;

5)d(xi,xj)+d(xj,xk)≥ d(xi, xk).

Расстояние для графа G определяется матрицей расстояний. Матрицей расстояний графа с n вершинами называется квадратная матрица D порядка n с элементами:

0,

если x

i

x

j

;

dij

,x

),если x

x

.

d(x

j

i

j

i

Для вершины xj величина e(xi)=max d(xi,xj) называется

эксцентриситетом вершины xi.

Максимальный среди эксцентриситетов вершин называ-

ется диаметром графа G и обозначается diam(G):
diam(G)=max e(xi)=max max d(xi,xj), xi,xj
Минимальный из эксцентриситетов	вершин связного
		.

графа называется его радиусом и обозначается через r(G): r(G )=min e(xi)=min max d(xi,xj) xi,xj .

245

Вершина, имеющая минимальный эксцентриситет, называется центром графа. Для вершины xi число

( ) = d ,x

.

называется передаточным числом.

Вершина графа, которой соответствует минимальное пе-

редаточное число	,x , xi, xj .
max P(xi)=max ∑

называется медианой графа. Центров и медиан в графе может быть несколько.

6.6. Достижимость и связность

Пусть в графе существует путь от вершины xi к вершине хj, то в этом случае вершина xj достижима из вершины хi.

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

Ориентированный граф называется односторонне связным или односторонним, если для двух различных вершин xi и xj существует путь из xi в xj или из xj в xi .

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

В противном случае орграф называется несвязным. Граф на рис. 6.10а будет сильно связным. Граф на рис.

6.10б, не является сильно связным (из x5 в x2 нет пути), но является односторонне связным. Граф, изображенный на рис. 6.10в, не является ни сильно связным, ни односторонним, т. к. в нем не существует путей от x5 к x2 и от x2 к x5. Он будет слабо связным. Граф, приведенный на рис. 6.10г, будет несвязным.

246

Рис. 6.10. Сильно связный граф (а), односторонне связный граф (б), слабо связный граф (в), несвязный граф (г)

Пусть имеется свойство Р. Максимальным подграфом графа G относительно свойства Р будет называться порожденный подграф (XS) графа G, обладающий этим свойством и такой, что не существует другого порожденного подграфа (ХH), у которого XS XH и который также обладает свойством Р.

Вграфе G (рис. 6.10б) подграф ({х1,x4,х5,х6}) является сильной компонентой графа G. А подграфы ({х1,х6}) и ({х1,х5,х6}) не будут сильными компонентами, т. к. они содержатся в графе ({х1,x4,x5,х6}) и они не максимальные.

Вграфе, показанном на рис. 6.10в подграф ({x1,x4,х5}) будет односторонней компонентой. В графе на рис. 6.10г оба подграфа ({х1,х5,х6}) и ({х2,х3,x4}) будут слабыми компонентами. У этого графа только две такие компоненты.

247

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

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

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

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

(СК). Имеется два вида связности – вершинная связность и реберная связность. Число вершинной связности – это наименьшее число вершин, удаление которых (вместе с инцидентными ребрами) приводит к несвязному графу. Число реберной связности – это наименьшее число ребер, удаление которых приводит к несвязному графу.

6.7. Определение сильных компонент графа

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

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

Для определения сильных компонент графа необходимо:

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

	1,	если вершин x	j	достижима из	x ;
ri, j					i
	0, в противном случае.

248

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

	1,	если x				i	x		j	;
dij
			,x		),	x		x			.
	d(x			j			i			j
		i

3. Построить матрицу сильной связности графа. Матрицей сильной связности орграфа с n вершинами называется квадратная матрица S порядка n, элементы которой определяются следующим образом:

	1,	если вершины x и x	j	взамно достижимы;
si, j		i
	0, в противном случае.

Матрицу сильной связности можно определить так:

R=QT, S=R*Q,

где R Q - операция поэлементного умножения матриц.

4. По матрице сильной связности выделить сильные компоненты графа. Если вершины xi и xj принадлежат одной сильной компоненте орграфа, то sij =1. При этом строки (столбцы), соответствующие этим вершинам в матрице S, одинаковы.

Рассмотрим задачи.

Задача 1. Определить метрические характеристики графа на рис. 6.11.

Рис. 6.11. Граф к задаче 1

Решение

Метрические характеристики определяются как:

249