одной матрицы А (U V) граф задается двумя матрицами: истоков А+ (U V) и стоков А– (U V).

1,если

v

j

исток

дуги u

i

;

a

(i, j)

0,иначе.

1,если

v

j

сток

дуги u

i

;

a

(i, j)

0,иначе.

6.2. Операции над графами

6.2.1. Удаление вершин и ребер

Удаление вершины. Пусть G = (V(G), U(G)) – граф и a V .

Удалить вершину a из графа G – это значит построить новый граф

G’=(V’(G’), U’(G’)), в котором V’(G’)=V(G)\{а} и U’(G’) получает-

ся из U(G) удалением всех ребер, инцидентных вершине а. На рис 6.6 приведен пример удаления вершины а из графа:

а

	До удаления	После удаления
	вершины а
		вершины а
		Рис. 6.6

Удаление ребра. Пусть G = (V(G), U(G)) – граф и b U . Уда-

лить ребро b – это значит построить новый граф G’=(V’(G’), U’(G’)), в котором V’(G’)= V(G) и U’(G’)=U(G)\{b}. На рис. 6.7 да-

на иллюстрация удаления ребра графа

147

b

До удаления ребра b

После удаления ребра b

Рис. 6.7

Граф G1=(V1,U1) называется подграфом графа G=(V,U), если V1 является подмножеством V и U1 является подмножеством U.

6.2.2. Дополнение

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

G G

Рис. 6.8

Например, дополнением полного графа на n вершинах будет пустой граф на n вершинах и наоборот.

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

148

ют вершины в своих долях, т.е. дополняют исходных граф до полного вообще (рис. 6.9).

G

G

Рис. 6.9

Например, если исходный граф является полным двудольным графом K4,5, то его дополнение будет представлять из себя несвязный граф, состоящий из двух компонент K4 и K5 (рис. 6.10).

K4,5	K4,5
	Рис. 6.10

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

Пусть даны два графа G1 = (V(G1), U(G1)), G2 = (V(G2), U(G2)), причем множества V(G1), V(G2) не пересекаются. Тогда объедине-

нием G G1 G2 графов G1, G2 называется граф с множеством

вершин V(G1 ) V(G2 ) и семейством ребер U(G1) U(G2 ).

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

149

вершин равно сумме вершин исходных графов, а количество ребер

– сумме ребер исходных графов (рис. 6.11).

G1	G2
n1 = 4	n1 = 3
m1 = 5	m1 = 3

G G1 G2

n = n1+n2 = 4+3 = 7 m = m1+m2 = 5+3 = 8

Рис. 6.11

6.2.4. Сложение графов

Пусть даны два графа G1= (V(G1), U(G1)), G2 = (V(G2), U(G2)),

причем множества V(G1), V(G2) не пересекаются. Тогда суммой графов G1, G2, обозначаемой G=G1+G2, называется граф, полученный как их объединение, причем каждая вершина графа G1 соединяется ребром с каждой вершиной графа G2.

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

графов n k ni , а количество ребер – сумме ребер исходных гра-

i 1

фов плюс количество новых ребер, равное произведению количеств

l	k
вершин исходных графов m mj	ni (рис. 6.12).
j 1	i 1

150