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

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

– матрица смежности;

– матрица инциденции;

– список смежности.

Рассмотрим эти виды задания.

1. Матрица смежности A = (a_ij) определяется одинаково для ориентированного и неориентированного графов. Это квадратная матрица порядка n, где n - число вершин, у которой

a_ij =

Пример.

Матрица смежности графа, изображенного на рис. 16 (a), имеет вид:

A =

Матрица смежности ориентированного графа, изображенного на рис. 16 (b), имеет вид:

A =

Матрица смежности полностью задает граф.

2. Матрицей инцидентности B = (b_ij) ориентированного графа называется прямоугольная матрица (n ´ m), где n – число вершин, m – число ребер, у которой

b_i =

Для неориентированного графа матрица инцидентности B задается следующим образом:

b_i =

Пример

Матрица инцидентности графа, изображенного на рис. 16 (a), имеет вид:

B =

Пример.

Матрица инцидентности ориентированного графа, изображенного на рис. 16 (b), имеет вид:

B =

Если граф содержит петли, то есть дуги вида (х_i, x_i) тогда элементы матрицы инцидентности, соответствующие дугам, образующим петли, одновременно равны 1 и –1, что приводит к неоднозначности матрицы инцидентности.

Матрица инцидентности, также, как и матрица смежности, полностью задает граф. Пример.

Дан граф, приведенный на рис. 20. Определить для него матрицы смежности и инцидентности.

Рисунок 20

Обозначим матрицу смежности - S, а матрицу инцидентности — U.

Основные свойства матриц смежности и инцидентности

1. Матрица смежности неориентированного графа является симметричной. Для ориентированного графа это, вообще говоря, неверно.

2. Сумма элементов i - ой строки или i -го столбца матрицы смежности неориентированного графа равна степени вершины x_i.

3. Сумма элементов i - ой строки матрицы смежности ориентированного графа равна числу дуг, исходящих из x_i.

4. Сумма элементов i - го столбца матрицы смежности ориентированного графа равна числу дуг, входящих в вершину x_i.

5. Сумма строк матрицы инцидентности ориентированного графа является нулевой строкой.

3. Списки смежности.

Обозначим Г(x)={i / (x,i) A} – множество концов ребер, начинающихся в x (для орграфа). Для графа это множество вершин, смежных с вершиной x.

Пронумеруем все вершины графа к=1, 2, …, n. Будем рассматривать все вершины по порядку и для каждой вершины k составлять список Г(x). Все такие списки подряд без пропусков разместим в некотором массиве А. в другом массиве В, состоящем из n элементов, будем размещать номера элементов массива А, начинающих список, соответствующий данному элементу массива В. Схематически полученная структура представлена на рис. 21.

Рисунок 21.

Указанная структура называется списком смежности.

Замечание. Некоторые списки смежности в общем случае могут быть пустыми. Если список пуст, то в массиве А он места не занимает, а соответствующий элемент в массива В заносится 0.

Пример.

1. Для графа, представленного на рис. 24, список смежности имеет следующий вид:

Вершина	B	A
А (1)	1	2	Г(А)
B (2)	3	3
C (3)	5	1	Г(В)
D (4)	6	4
E (5)	7	1	Г(С)
		5
		2	Г(D)
		4	Г(E)

2. Рассмотрим еще один граф, представленный на рис. 22. Составим для него список смежности.

Рисунок 22.			В	А
		1	0	3	Г(2)
	(3)	2	1	1	Г(3)
		3	2	2
		4	4	1	Г(4)
		5	0	3
			7	4

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

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

а) посредством графического изображения;

б) указанием множества вершин и множества ребер (дуг);

в) матрицей смежности;

г) матрицей инцидентности;

д) списком смежности.