Структурная матрица

Маршруты в графах

Следующая теорема позволяют по матрице смежности графа исследовать маршруты данного графа.

Теорема

Если матрица смежности графа , то (i, j) - тый элемент матрицы есть число маршрутов из вершины в вершину длины к. Длина маршрута определяется числом ребер (дуг) маршрута.

Следствие 1

В графе , |V|=p тогда и только тогда существует маршрут из вершины в вершину , когда (i, j) - тый элемент матрицы не равен 0.

Следствие 2

В графе , |V|=p тогда и только тогда существует цикл, содержащий вершину , когда (i, i) - тый элемент матрицы не равен 0.

Пример

Дан граф , |V|=4

1 2 3

Элемент (1, 3) матрицы равен 1, то есть существует один маршрут из вершины 1 в вершину 3. Из рисунка видно, что этот маршрут определяется набором вершин (1, 4, 2, 3).

Элемент (1, 3) матрицы получается при перемножении элемента (1, 2) матрицы и элемента (2, 3) матрицы . В свою очередь элемент (1, 2) матрицы образуется при перемножении элемента (1, 4) матрицы и элемента (4, 2) матрицы .

(1, 3)

(1, 2) (2, 3)

(1, 4) (4, 2) (2, 3) (1, 4, 2, 3)

В матрице элемент (4, 2) равен 3, то есть существует 3 маршрута длины 3 из вершины 4 в вершину 2:

(4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, 2).

Структурная матрица

Именно эта матрица имеет особое значение в теории сетей связи. Структурная матрица – это символьная матрица графа порядка р (|V|=p).

Она составляется следующим образом: на главной диагонали стоит 1, т. е. t_ii = 1, остальные элементы – это символьные обозначения ребер (если вершины i и j не соединены ребром, то tij = 0). При этом если при i< j и вершины i и j соединены ребром а, то элемент t_ij = a, а при i> j – это отрицание а, которое обычно отмечается чертой сверху (). Если связи вершины i c вершиной j нет, то соответствующий элемент равен 0. В ориентированном графе отрицания отсутствуют.

Структурная матрица может составляться как для неориентированного графа, так и для орграфа и для мультиграфа без петель (здесь если два ребра а и b соединяют две вершины, то соответствующий элемент при i < j равен a b, а при i> j этот элемент равен ).

Отметим, что в учебных целях, когда действия с матрицами осуществляются студентами “вручную” (число вершин в графе невелико), можно обозначать ребра латинскими буквами без индексов a, b, c, … но при использовании компьютера гораздо удобнее обозначать ребра t(i, j), если это ребро соединяет вершины i и j при i< j и с чертой сверху, если i> j.