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

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

Пусть 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		-1		-1
b					+1	+1
c			+1	-1
d		+1				+1	+1
e				+1
f	+1	+1

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

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

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

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