Page 115 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

Таблиця 8.1

x 5 36 43 14 17 35 19 12 21
y 29 24 11 28 8 38 23 39 12

Перший етап. Розрахуємо матрицю відстаней між вершинами, ви-

користовуючи формулу (8.1). Перш за все врахуємо, що d 11 = d 22 = d 33 = …

= d 99 = 0. Крім того, слід мати на увазі, що матриця відстаней – симет-

рична. Отже, нам необхідно вирахувати 9*8/2 = 36 відстаней.

2
2
d 12  5 (  36 )  ( 29  24 )  31 4 , ;
2
2
d 13  5 (  43 )  ( 29  11 )  42 0 , ;

2
2
d  5 (  14 )  ( 29  28 )  1 , 9 ;
14
. . . . . . . . . . . . . . . . . . . . . . . . .

2
d 89  ( 12  21 )  ( 39  12 )  28 5 , .
2
У результаті розрахунків отримуємо матрицю відстаней у вигляді:

1 2 3 4 5 6 7 8 9

1 0 31.4 42.0 9.1 24.2 31.3 15.2 12.2 23.3

2 0 14.8 22.4 24.8 14.0 17.0 28.3 19.2

3 0 33.6 26.2 28.2 26.8 41.8 22.0

4 0 20.2 23.3 7.1 11.2 17.5

5 0 35.0 15.1 31.4 5.7

6 0 21.9 23.0 29.5

7 0 17.5 11.2

8 0 28.5

9 0

Другий етап. Застосовуємо алгоритм Пріма – Крускала.

114