Рисунок 2.3 - Матрица инциденций B
2.3 Матрица основных контуров
Матрицей основных контуров орграфа называется матрица С=, состоящая из подматрицы остовного дерева T орграфа и единичной подматрицы E, порядок которой равен числу хорд остовного дерева T. Остовным деревом называется граф, не имеющий контуров и полуконтуров. Число основных контуров связного орграфа определяется формулой:
,
где m - число дуг;
n - число вершин.
Согласно этой формуле ГСУ «Общежитие» содержит 9 основных контуров (=23-15+1=9). Остовное дерево ГСУ «Общежитие» представлено на рисунке 2.4, а матрица основных контуров на рисунке 2.5.
Рисунок 2.4 - Остовное дерево ГСУ «Общежитие»
1/4
4/5
4/10
5/12
6/5
8/6
9/5
10/5
13/5
1/10
2/10
3/5
5/4
5/6
5/10
6/8
7/5
9/4
11/10
12/5
13/10
14/5
15/5
1
-1
Рисунок 2.5 - Матрица основных контуров С
2.4 Матрица расстояний
Матрицей расстояний орграфа называется матрица R=||||nn, в которой элемент равен длине кратчайшего пути из вершины i в вершину j. Если такого пути нет, то соответствующий элемент полагается равным бесконечности =?, а =0. Матрица расстояний ГСУ «Общежитие» представлена на рисунке 2.6.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
?
Страницы: 1, 2, 3, 4, 5, 6, 7
