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

ВАРИАНТ В.4-2.

Задание.

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

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

a)  Построить матрицу расстояний

b)  Определить эксцентриситеты всех вершин.

c)  Определить радиус и диаметр модели сети.

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

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

Решение.

1                  7                             2        4               3        12            4        5      5            6           6

6                                6                                     6                          6                   6                       5

                                                                                                                    13                              

                                                                                       12                 3

                                                                                                                       4       

              3                                                2           11                       12                             3

7                          8                                                                                                   14               15

                                     8                     10

                                                    2

                                            9

Рис. 1.

1.  Обозначим вершины графа х1, х2, …х15.

Ребра графа: у1=1-2 вершина, у2=2-3 вершина, у3=3-4 вершина, у4=4-5 вершина, у5=5-6 вершина, у6=1-7 вершина, у7=7-8 вершина, у8=2-8 вершина, у9=8-9 вершина, у10=9-10 вершина, у11=10-11 вершина, у12=11-3 вершина, у13=11-12 вершина, у14=12-4 вершина, у15=12-13 вершина, у16=13-14 вершина, у17=5-14 вершина, у18=14-15 вершина, у19=15-6 вершина, (на рисунке обозначен вес ребер).

Построим матрицу инцидентности:

Таблица 1. Матрица инцидентности графовой модели

у1 у2 у3 у4 у5 у6 у7 у8 у9 у10 у11 у12 у13 у14 у15 у16 у17 у18 у19 х1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 х2 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 х3 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 х4 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 х5 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 х6 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 х7 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 х8 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 х9 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 х10 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 х11 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 х12 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 х13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 х14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 х15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1