2.2 Матричные представления графа

Одной из форм математического представления графа является его представление в виде матриц смежности инциденций.

Вершины х и y являются смежными, если они различны и если существует дуга, идущая из х в y.

Дугу u называют инцидентной вершине х, если она заходит в эту вершину или исходит из нее.

Обозначим через х₁, х₂, …, х_n вершины графа, а через u₁, u₂, …, u_m его дуги.

Матрицей смежности R= графа G=(Х, Г) называется квадратная матрица порядка n (n – число вершин графа), элементы которой r_i,j (i=1, 2, …n; j=1,2, …n) определяются следующим образом:

2.6

Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат. Элемент матрицы R² определяется по формуле:

2.7

Слагаемое тогда и только тогда, когда и , в противном случае слагаемое . Так как из равенства следует существование пути длины два (пути, проходящего через две дуги) из вершины х_i в вершину x_j, проходящего через вершину x_k, то равно числу путей длины два, идущих из x_i в x_j через x_k.

Если является элементом матрицы , то 0 равно числу путей длины p, идущих из x_i в x_j.

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

Рис. 2.4

Решение.

Элемент , следовательно в данном графе существует единственный путь длиной три – это путь из вершины х₁ в вершину х₄: х₁ u₁ x₂ u₂ x₃ u₃ x₄.

Все элементы матрицы равны нулю. Следовательно, в графе отсутствуют пути длиной четыре.

Матрицей инциденций называется прямоугольная матрица размерности nm (n-число вершин, m – число дуг), элементы которой определяются следующим образом:

2.8

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

Пример. Построить матрицу смежности и матрицу инциденций для графа, приведенного на рис. 2.5.

Рис. 2.5

Решение.

Матрица смежности будет иметь вид:

xi	x1	x2	x3	x4	x5
x1	0	1	0	1	0
x2	0	0	1	1	0
x3	0	0	0	0	0
x4	0	1	1	0	1
x5	1	0	1	0	0

Матрица инциденций будет иметь вид:

xi /uj	u1	u2	u3	u4	u5	u6	u7	u8	u9
x1	-1	1	1	0	0	0	0	0	0
x2	0	0	-1	1	-1	1	0	0	0
x3	0	0	0	0	0	-1	-1	0	1
x4	0	-1	0	-1	1	0	1	1	0
x5	1	0	0	0	0	0	0	-1	1

Или в более компактной форме матрица смежности R и инциденций S будут иметь вид:

; .