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

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

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

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

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

Матрицей смежности R=[r_i,j] графа 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.

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

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 будут иметь вид:

; .

Дата добавления: 2015-10-13