1. Списки ребер

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

2. Матрицы смежности

Пусть G = (V, U)  это граф с вершинами V = {v₁, ... v_n}. Тогда матрицей смежности этого графа называется квадратная таблица размером n  n, строки и столбцы которой поставлены во взаимно однозначное соответствие вершинам множества V.

Значение элемента этой матрицы, расположенного на пересечении i -й строки и j-го столбца определяется по правилу:

=

Для графа, изображенного на рис. 5.2., матрица смежности имеет следующий вид:

	a	b	c	d	e	v
a	0	0	1	0	1	1
b	0	1	0	1	0	0
c	1	0	0	1	0	0
d	0	1	1	0	0	1
e	0	0	0	0	0	0
v	0	0	0	1	0	0

3. Матрицы инциденций

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

Пусть G = (V, U)  произвольный граф, для которого

V = {v₁, ... v_n} и U = {u₁, ... , u_k}.

Тогда матрицей инциденций этого графа называется таблица, имеющая n строк, соответствующих вершинам из V, и k столбцов, соответствующих ребрам из U.

Значение элемента b_i,j этой матрицы, находящегося на пересечении i-й строки и j-го столбца определяется по правилу:

- 1, если ребро u_j выходит из вершины v_i и

не является петлей

b_i,j = + 1, если u_j ведет в v_i

0, в остальных случаях.

Пример. Построим матрицу инциденций для графа, изображенного на рис. 5.3.:

a u₃ c u₁

u₅

b u₄

u₆ e

d

u₇ u₂ f

Рис. 5.3.

	u1	u2	u3	u4	u5	u6	u7
a	-1	0	-1	0	-1	0	0
b	0	0	0	0	+1	+1	0
c	0	0	+1	-1	0	0	0
d	0	+1	0	0	0	+1	+1
e	0	0	0	+1	0	0	0
f	+1	+1	0	0	0	0	0

Представления графов с помощью матриц могут использоваться для хранения и обработки графов при решении задач с помощью ЭВМ.

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

Например, если граф имеет 100 вершин и из каждой вершины выходит не более 10 ребер, то в матрице смежности для такого графа число единиц, которыми представляется информация о ребрах графа, составляет не более 10% от общего числа элементов матрицы.

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