Методические рекомендации (стр. 4 )

T5 – не содержит “x”,

.

IV. ТЕОРИЯ ГРАФОВ

Основные понятия

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

Определение. Графом G называется совокупность двух множеств: вершин V и ребер E, между элементами которых определено отношение инцидентности – каждое ребро еÎЕ инцидентно ровно двум вершинам , , которые оно соединяет.

При этом вершина и ребро е называются инцидентными друг другу, а вершины и , являющиеся для ребра её концевыми точками, называются смежными. Часто вместо и еÎЕ пишут соответственно , еÎG. Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой. Тогда ребро называется направленным (ориентированным) или дугой и изображается стрелкой, направленной от вершины, называемой началом, к вершине, называемой концом. Граф, содержащий направленные ребра (дуги) с началом и концом , называется ориентированным (ор-графом) и ненаправленные - неориентированным (н-графом). Ребра, инцидентные одной и той же паре вершин, называются параллельными (кратными). Граф, содержащий кратные ребра, называется мультиграфом. Ребро, концевые вершины которого совпадают, называется петлей. Если множество его элементов графа (вершин и ребер) конечно, то он называется конечным. Если же множество вершин V (ребер Е) пусто, то граф называется пустым. Граф без петель и кратных ребер называется полным, если каждая пара вершин соединена ребром.

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

Локальной степенью (или просто степенью) вершины н – графа G называется количество ребер , инцидентных вершине . В н-графе сумма степеней всех вершин равна удвоенному числу ребер “m” графа, т. е. четна (в графе с петлями петля дает вклад 2 в степень вершины).

В н-графе число вершин нечетной степени четно. Для вершин графа определяются две локальные степени:

1)  - число ребер с началом в вершине (количество выходящих из ребер);

2)  - количество входящих в вершину ребер, для которых эта вершина является концом.

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

.

Графы G1 и G2 равны G1=G2, если их множества вершин и ребер (выраженных через пары инцидентных им вершин) совпадают: V1=V2 и Е1=Е2. Граф G считается полностью заданным, если нумерация его вершин и ребер зафиксирована. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Пример 1:

Рис 1.

G1 – G7 – неориентированные графы;

G8 – G12 – орграфы, G1 = G2 ;

G7 – не является полным, хотя каждая пара вершин соединена ребром, но имеется одна петля;

G3 – все вершины этого графа являются изолированными, т. е. Е = 0;

G4 – G5 – являются дополнением друг другу ;

G6 – мультиграф, т. к. содержит кратные ребра а и в, е и f;

G8 – ориентированный граф, канонически соответствующий Н – графу G5;

G9 – G10 – не равны, т. к. имеют отличающиеся ребра;

G11 – ор. граф (мультиграф), а и в – кратные;

G12 – не мультиграф (а и в различно ориентированы).

Пример 2:

Рис.2

G1 и G3 – оба графа имеют по четыре вершины V = {1, 2, 3 ,4}.

Степени вершины н – графа : r (1) =3, r (2) =4, r (3) =3, r (4) =4.

Тогда , т. е. равна , где 7 – число ребер графа.

Степени вершин орграфа :

r1 (1) =2, r1 (2) =3, r1 (3) =1, r1 (4) =1, r2 (1) =1, r2 (2) =1, r2 (3) =2, r2 (4) =3.

Тогда (число ребер).

Способы задания графов

Рассмотрены два способа описания графов: графически и в виде двух множеств вершин V и ребер Е, когда каждое ребро еÎЕ определено парой инцидентных ему концевых вершин .

Опишем множество его вершин и ребер, а также отношение инцидентности. Занумеруем вершины графа G: V1, V2, …, Vi, Vn и ребра: е1, е2, …, еi, еm.

Отношение инцидентности задается:

1.  Матрицей инцидентности размера m x n: по вертикали и горизонтали указываются вершины и ребра соответственно, а на пересечении i-ой вершины и j-го ребра, в случае н – графа проставляется 1, если они инцидентны и 0 – в противном случае, т. е.

В случае орграфа: -1, если вершина является началом ребра;

1, если вершина является концом ребра;

0, если вершина и ребро не инцидентны.

Если некоторая вершина является для ребра началом и концом (петля), проставляется любое другое число, например, 2, т. е.

2.  Списком ребер графа, представленным двумя столбцами: в левом перечисляются все ребра еiÎЕ, а в правом – инцидентные ему вершины , ; для н – графа порядок вершин в строке произволен, для орграфа первым стоит номер начала ребра;

3.  Матрицей смежности - квадратной матрицей размера n x n; по вертикали и горизонтали перечисляются все вершины VjÎV, а на пересечении и вершин в случае н-графа проставляется число, равное числу ребер, соединяющих эти вершины; для орграфа равно числу ребер с началом в вершине и концом в .

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

Пример 1: Задать матрицами инцидентности и смежности, а также списком ребер графы G1, G3 (рис 2).

Матрица инцидентности: Табл.1

G1	a	b	c	d	e	f	g
1	1	1	1	0	0	0	0
2	1	1	0	1	1	0	0
3	0	0	1	1	0	1	0
4	0	0	0	0	1	1	1

G3	a	b	c	d	e	f	G
1	-1	1	-1	0	0	0	0
2	1	-1	0	-1	-1	0	0
3	0	0	1	1	0	-1	0
4	0	0	0	0	1	1	2

Матрица смежности:

Табл.2

G1	1	2	3	4
1	0	2	1	0
2	2	0	1	1
3	1	1	0	1
4	0	1	1	1

G3	1	2	3	4
1	0	1	1	0
2	1	0	1	1
3	0	0	0	1
4	0	0	0	1

Список ребер:

Табл. 3

Ребро	Вершины
a	1 2
b	2 1
c	1 3
d	2 3
e	2 4
f	3 4
g	4 4