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

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

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

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

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

2.6

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

2.7

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

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

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

Рис. 2.4

Решение.

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

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

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

2.8

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

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

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

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

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

; .