Page 119 - 4204

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

матриці найкоротших відстаней між вершинами графа та обчис-

лення параметрів критерію.

Для побудови матриці найкоротших відстаней у мережах ро-

зроблені спеціальні алгоритми, проте, якщо кількість вузлів неве-

лика, то можна використати метод перебору варіантів (див.

п. 8.2). Ми розглянемо задачу за умови, що ця матриця вже відо-

ма. Зокрема у найпростішому випадку її можна обчислити вико-

риставши формулу відстані між двома точками (центрами насе-

лених пунктів).

Приклад. Нехай за результатами підрахунків отримано матрицю

найкоротших відстаней для 5-ти населених пунктів.

№ п/п 1 2 3 4 5 к-сть
учнів
1 0 3 5 8 6 38

2 3 0 4 5 3 44

3 5 4 0 3 1 37

4 8 5 3 0 2 26

5 6 3 1 2 0 31

711 485 475 697 449

Приєднаємо справа до таблиці ще один стовпчик, у якому розмісти-

мо дані про кількість учнів у населених пунктах. Знизу таблиці приєднаємо

рядок, у якому розмістимо суми добутків кількості учнів у населених пу-

нктах на найкоротші відстані до цих населених пунктів. Ці числа бу-

дуть характеризувати сумарну відстань, пройдених всіма учнями до шко-

ли, розташованої у відповідному населеному пункті. Аналіз останнього

рядка показує, що найвигідніше розмістити школу у п’ятому населеному

118