Матрицы графов.

Во многих задачах графы удобно задавать матрицами. Пусть граф G=(V, E) – граф c n вершинами и m ребрами, причем вершины и ребра занумерованы.

Матрицей инцидентности называется матрица A(G) размера m n, элементы которой имеют вид

Матрицей смежности графа называется матрица B(G) n n , которая имеет вид

B(G)_{i j} = числу ребер, инцидентных одновременно i –той и j – ой вершинам.

П р и м е р .Задана матрица инцидентности графа (цифрами обозначены вершины, буквами – ребра графа).

. Требуется:

a) Восстановить граф по матрице инцидентности;

b) Выяснить, является ли граф связным;

c) Построить для данного графа матрицу смежности

Р е ш е н и е .

2

a ) e₁ e₅

1 e₂ 4

e₄

e₆

e₃

3

h

Более компактным описанием графа по сравнению с матрицей инцидентности является список ребер.

Ребро e₁ инцидентно вершинам 1 и 2.

Ребро e₂ инцидентно вершинам 1 и 2.

Ребро e₃ инцидентно вершинам 1 и 3.

Ребро e₄ инцидентно вершинам 2 и 3.

Ребро e₅ инцидентно вершинам 2 и 4

Ребро h инцидентно вершинам 4 и 4

b) .Граф является связным.

c) Матрица смежности имеет вид.