Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

 

Теорема

Если матрица смежности графа , то (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, т. е. tii = 1, остальные элементы – это символьные обозначения ребер (если вершины i и j не соединены ребром, то tij = 0). При этом если при i< j и вершины i и j соединены ребром а, то элемент tij = 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.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал