Анализ системы управления Общежитие (стр. 2 из 5)

Далее рассмотрим второй способ представления графа – матричный. Основными матрицами графа являются матрицы смежностей, инциденций и матрица основных контуров.

2.1 Матрица смежностей

Матрицей смежностей орграфа, имеющего n вершин, называется матрица A=||

||n´n, элемент которой =1, если вершина i смежна к вершине j (т.е. дуга направлена от вершины i к вершине j) и =0 в противном случае. Матрица смежностей ГСУ «Общежитие» представлена на рисунке 2.2.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	ρ+
1	1	1	2
2	1	1
3	1	1
4	1	1	2
5	1	1	1	1	4
6	1	1	2
7	1	1
8	1	1
9	1	1	2
10	1	1
11	1	1
12	1	1
13	1	1	2
14	1	1
15	1	1
ρ-	0	0	0	3	10	2	0	1	0	6	0	1	0	0	0

Рисунок 2.2 – Матрица смежностей A

Из данной матрицы можно увидеть, что сумма всех элементов матрицы равна числу дуг орграфа. Сумма элементов строки i равна полустепени исхода вершины i, а сумма элементов столбца j равна полустепени захода вершины j.

2.2 Матрица инциденций

Матрицей инциденций орграфа, имеющего n вершин и m дуг, называется матрица B=||

||_n´m, у которой =1, если дуга j инцидентна вершине i и направлена от нее, = -1, если дуга j инцидентна вершине i и направлена к ней, и =0 в противном случае. На рисунке 2.3 представлена матрица инциденций ГСУ «Общежитие».

1/4	1/10	2/10	3/5	4/5	4/10	5/4	5/6	5/10	5/12	6/5	6/8	7/5	8/6	9/4	9/5	10/5	11/10	12/5	13/5	13/10	14/5	15/5
1	1	1
2	1
3	1
4	-1	1	1	-1	-1
5	-1	-1	1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1
6	-1	1	1	-1
7	1
8	-1	1
9	1	1
10	-1	-1	-1	-1	1	-1	-1
11	1
12	-1	1
13	1	1
14	1
15	1

Рисунок 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/4	1	-1	-1	1
4/5	1	1
4/10	1	1	-1
5/12	1	1
6/5	1	1
8/6	1	1
9/5	1	1	-1
10/5	1	1
13/5	1	1	-1

Рисунок 2.5 – Матрица основных контуров С

2.4 Матрица расстояний

Матрицей расстояний орграфа называется матрица R=||

||_n´n, в которой элемент равен длине кратчайшего пути из вершины i в вершину j. Если такого пути нет, то соответствующий элемент полагается равным бесконечности =∞, а =0. Матрица расстояний ГСУ «Общежитие» представлена на рисунке 2.6.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	∞	∞	1	2	3	∞	4	∞	1	∞	3	∞	∞	∞
2	∞	∞	3	2	3	∞	4	∞	1	∞	3	∞	∞	∞
3	∞	∞	2	1	2	∞	3	∞	2	∞	2	∞	∞	∞
4	∞	∞	∞	1	2	∞	3	∞	1	∞	2	∞	∞	∞
5	∞	∞	∞	1	1	∞	2	∞	1	∞	1	∞	∞	∞
6	∞	∞	∞	2	1	∞	1	∞	2	∞	2	∞	∞	∞
7	∞	∞	∞	2	5	2	3	∞	2	∞	2	∞	∞	∞
8	∞	∞	∞	3	2	1	∞	∞	3	∞	3	∞	∞	∞
9	∞	∞	∞	1	1	2	∞	3	2	∞	2	∞	∞	∞
10	∞	∞	∞	2	1	2	∞	3	∞	∞	2	∞	∞	∞
11	∞	∞	∞	3	2	3	∞	4	∞	1	3	∞	∞	∞
12	∞	∞	∞	2	1	2	∞	3	∞	2	∞	∞	∞	∞
13	∞	∞	∞	2	1	2	∞	3	∞	1	∞	2	∞	∞
14	∞	∞	∞	2	1	2	∞	3	∞	2	∞	2	∞	∞
15	∞	∞	∞	2	1	2	∞	3	∞	2	∞	2	∞	∞

Рисунок 2.6 – Матрица расстояний R

2.5 Матрица достижимостей

Матрицей достижимостей орграфа называется матрица D=||

||_n´n, в которой элемент =1, если существует путь из вершины i в вершину j (т.е. вершина j достижима из вершины i), иначе =0, а =1. Матрица достижимостей ГСУ «Общежитие» представлена на рисунке 2.7.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1	1	1	1	1	1	1
2	1	1	1	1	1	1	1
3	1	1	1	1	1	1	1
4	1	1	1	1	1	1
5	1	1	1	1	1	1
6	1	1	1	1	1	1
7	1	1	1	1	1	1	1
8	1	1	1	1	1	1
9	1	1	1	1	1	1	1
10	1	1	1	1	1	1
11	1	1	1	1	1	1	1
12	1	1	1	1	1	1
13	1	1	1	1	1	1	1
14	1	1	1	1	1	1	1
15	1	1	1	1	1	1	1

Рисунок 2.7 – Матрица достижимостей D

2.6 Матрица обходов

Матрицей обходов орграфа называется матрица S=||

||_n´n, в которой элемент равен длине наибольшего пути из вершины i в вершину j, если такого пути нет, то соответствующий элемент полагается равным бесконечности, т. е. =∞. Матрица обходов ГСУ «Общежитие» представлена на рисунке 2.8.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	∞	∞	∞	3	2	3	∞	4	∞	3	∞	3	∞	∞	∞
2	∞	∞	∞	3	2	3	∞	4	∞	1	∞	3	∞	∞	∞
3	∞	∞	∞	2	1	2	∞	3	∞	3	∞	2	∞	∞	∞
4	∞	∞	∞	2	2	2	∞	3	∞	2	∞	2	∞	∞	∞
5	∞	∞	∞	1	2	1	∞	2	∞	2	∞	2	∞	∞	∞
6	∞	∞	∞	2	1	2	∞	1	∞	2	∞	2	∞	∞	∞
7	∞	∞	∞	2	5	6	∞	3	∞	2	∞	2	∞	∞	∞
8	∞	∞	∞	3	2	1	∞	2	∞	4	∞	3	∞	∞	∞
9	∞	∞	∞	2	2	2	∞	3	∞	3	∞	2	∞	∞	∞
10	∞	∞	∞	2	1	2	∞	3	∞	2	∞	2	∞	∞	∞
11	∞	∞	∞	3	2	3	∞	4	∞	1	∞	3	∞	∞	∞
12	∞	∞	∞	2	1	2	∞	3	∞	2	∞	2	∞	∞	∞
13	∞	∞	∞	3	2	3	∞	4	∞	2	∞	3	∞	∞	∞
14	∞	∞	∞	2	1	2	∞	3	∞	3	∞	2	∞	∞	∞
15	∞	∞	∞	2	1	2	∞	3	∞	3	∞	2	∞	∞	∞

Рисунок 2.8 – Матрица обходов S