Анализ графовой модели СЭГ

Министерство связи РФ

Сибирский Государственный Университет телекоммуникаций и информатики

Факультет заочного ускоренного обучения

Контрольная работа по курсу АПТС.

« Анализ графовой модели СЭГ»

выполнил студент ЗТ-03-073

Кидиеков С.Р.

Новосибирск-2003г

Вариант 10-В2.

Анализ графовой модели СЭГ.

    Исходные данные:

Задан план городского населенного пункта .Цифры в каждом многоугольнике –количество населения микрорайона в тыс. человек. Цифры около вершин размеченной графовой модели будущей СЭГ, это номера вершин. Цифры в полукруге вблизи каждого ребра модели, это длины участков улиц в километрах.

     Задание:

1.  Построить матрицы инцидентности и смежности для графовой модели.

2.  Определить основные метрические характеристики будущей СЭГ.

·  построить матрицу расстояний;

·  определить экценриситеты всех вершин;

·  определить радиус и диаметр модели сети;

·  определить центральные и периферийные вершины графовой модели.

3.  По алгоритму Прима-Краскала построить кратчайшее остовное дерево с минимальным весом ребер.

Решение:

1.  Построить матрицы инцидентности и смежности для графовой модели СЭГ.

Матрица инцидентности.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	1	0	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
4	0	0	1	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
6	0	0	0	0	1	1	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
7	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	1	1	1	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
9	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
10	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	0	0	0	0	0	0	0	0
12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0	0	0	1	1	0	0	0
13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	1
14	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0	1	1	1	1	0	0	0	0	0	0	0
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	1	0	0	1	1
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0	0	0	0
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0