Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

1. Матрица инциденций

Матрицей инциденций орграфа, имеющего n вершин и m дуг, называется матрица B=|| ||_nm, у которой =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

1. Матрица основных контуров

Матрицей основных контуров орграфа называется матрица С= , состоящая из подматрицы остовного дерева 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 – Матрица основных контуров С

1. Матрица расстояний

Матрицей расстояний орграфа называется матрица R=|| ||_nn, в которой элемент равен длине кратчайшего пути из вершины 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

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

Матрицей достижимостей орграфа называется матрица D=|| ||_nn, в которой элемент =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. Матрица обходов

Матрицей обходов орграфа называется матрица S=|| ||_nn, в которой элемент равен длине наибольшего пути из вершины 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

2. . Анализ числовых характеристик СУ «Общежитие»

Для сравнения структурных свойств различных графов определяют их числовые характеристики (инварианты), которые выражаются числами или системами чисел, характеризуют определенные свойства и являются одинаковыми для изоморфных графов. Простейшими инвариантами графа являются числа его вершин n и дуг m. Ниже будут рассмотрены более сложные числовые характеристики ГСУ и их интерпретация.

1. Степень (полустепень) вершины

Полустепенью исхода вершины орграфа называется число инцидентных дуг, выходящих из вершины, а полустепенью захода — число инцидентных дуг, заходящих в вершину. Для определения данной числовой характеристики используется матрица смежностей (рисунок 2.2), в которой сумма элементов строки равна полустепени исхода соответствующей вершины, а сумма элементов столбца – полустепени захода.

Характеристики

Список файлов курсовой работы