Page 121 - 4204

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

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

ним.

Для прикладу використаємо матрицю найкоротших відстаней, з по-

передньої задачі. Далі приєднаємо справа до таблиці ще один стовпчик і

випишемо в ньому максимальні елементи з кожного рядка. Ці числа від-

повідатимуть відстаням з кожного пункту до найбільш віддаленого у да-

ній мережі (розглядаємо найгірший варіант), тобто маємо максимальні

відстані у мережі для випадків, якщо пожежну частину розташовувати у

населеному пункті із номером рядка. Остаточно вибираємо мінімальний

елемент серед всіх чисел доданого стовпчика. У нашому випадку це число

5 (пункти 2 та 3).

№ п/п 1 2 3 4 5
max
1 0 3 5 8 6 8

2 3 0 4 5 3 5

3 5 4 0 3 1 5

4 8 5 3 0 2 8

5 6 3 1 2 0 6

Отже, пожежну частину найбільш вигідно розміщувати у 2-му або

3-му населених пунктах. При цьому відстань до найбільш віддаленого пун-

кту (у 1-му випадку до п. № 4, а в 2-му до п. № 1) становитиме 5 кіломе-

трів. Зрозуміло, що отримання кількох однаково оптимальних результа-

тів дозволяє застосовувати додаткові критерії.

Контрольні запитання.

1. Назвіть основні передумови виникнення та сфери застосування тео-
рії графів.
2. Дайте визначення поняття «граф».

120