Page 118 - 4204

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

ких задач визначається конфігурацією області припустимих то-

чок розміщення і способом оцінки якості розміщення. Внаслідок

цього існує багато різноманітних задач розміщення, що стосу-

ються різних сфер діяльності і у технічній літературі пропонуєть-

ся чимало методів їх розв’язання.

Для того, щоб формулювати і розв’язувати задачі на розмі-

щення, необхідно ввести нові поняття теорії графів.

Центром графа називається будь-яка його вершина, відстань

від якої до найвіддаленішої від неї вершини є мінімальною.

Медіаною графа називається точка, в якій сума відстаней до

усіх вершин графа є мінімальною.

Наступна задача моделює процес визначення медіани певної

мережі з урахуванням ваги кожного пункту.

Формулювання. Задана дорожня мережа, яка складається n

вершин (населених пунктів), з’єднаних ребрами. Необхідно:

1) обчислити матрицю найкоротших відстаней між усіма пунк-

тами мережі;

2) використовуючи дані про кількість учнів у населених пунк-

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

В основу розв’язування задачі покладено критерій, що вини-

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

по дорозі до школи повинна бути мінімальною. Доведена тео-

рема, згідно з якою оптимальним місцем розташування школи

може бути лише населений пункт. Це значно спрощує

розв’язування задачі і, по суті, зводить її до задачі про побудову

117