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

Страницы работы

Содержание работы

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

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

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

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

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

выполнил студент ЗТ-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

Похожие материалы

Информация о работе