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

	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	х13	х14	х15
х1		7	11	23	28	34	6	9	17	19	17	29	32	34	36
х2	7		4	16	21	27	9	6	14	12	10	22	25	27	30
х3	11	4		12	17	23	13	10	10	8	6	18	21	23	26
х4	23	16	12		5	11	25	22	22	20	18	6	9	11	14
х5	28	21	17	5		6	30	27	27	25	23	11	10	6	9
х6	34	27	23	11	6		36	33	31	29	27	15	12	8	5
х7	6	9	13	25	30	36		3	11	13	15	27	30	34	37
х8	9	6	10	22	27	33	3		8	10	12	24	27	31	34
х9	17	14	10	22	27	31	11	8		2	4	16	19	23	27
х10	19	12	8	20	25	29	13	10	2		12	14	17	21	24
х11	17	10	6	18	23	27	15	12	4	2		12	15	19	22
х12	29	22	18	6	11	15	27	24	16	14	12		3	7	10
х13	32	25	21	9	10	12	30	27	19	17	15	3		4	7
х14	34	27	23	11	6	8	34	31	23	21	19	7	4		3
х15	36	30	26	14	9	5	37	34	27	24	22	10	7	3

Эксцентриситеты всех вершин:

e(1)	e(2)	e(3)	e(4)	e(5)	e(6)	e(7)	e(8)	e(9)	e(10)	e(11)	e(12)	e(13)	e(14)	e(15)
36	30	26	25	30	36	37	34	31	29	27	29	32	34	36

Диаметр  d (G) = 37,   радиус  r (G) = 25

Периферийная вершина  - 7 ;  центральная вершина - 4.

3.  Упорядочим ребра графа по убыванию весов: 12,12,8,7,6,6,6,6,6,6,5,5,4,4,3,3,3,2,2.

Рассмотрим последовательно все ребра графа начиная с ребра наибольшего  веса и 

       определим, можно ли их удалить из графа, не нарушив его связности.

1                  7                             2        4               3        12            4        5      5            6           6

6                                                                                                                                                 5

                                                                                                                    13                              

                                                                                       12                 3

                                                                                                                       4       

              3                                                2           11                       12                             3

7                          8                                                                                                   14               15

                                     8                     10

                                                    2

                                            9

Рис. 2. Кратчайшее остовное дерево графовой модели.

Суммарный вес ребер  Σvреб =  82

Литература.

1.  Конспект лекций.