Page 117 - 4204

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

Оскільки ми з’єднали всі вершини, то процедура завершена і ми

отримаємо мінімальне покриваюче дерево для розглядуваного графа, або,

іншими словами, найдешевшу дорожню мережу для даної системи населе-

них пунктів. Мережа має вигляд, зображений на рис. 8.4.

Висновок. Побудована найкоротша дорожня мережа загальною до-

вжиною 90,1 кілометра.

Зауваження 1. Так само, як і мінімальне покривне дерево,

можна будувати й максимальне. Типові задачі на побудову мак-

симального покривного дерева найчастіше виникають під час

проектування мереж за умови максимізації прибутку від експуа-

тації мережі.

Зауваження 2. Мінімальні (максимальні) дерева можна бу-

дувати і для тих мереж, у яких певні зв’язки (ребра) є фіксовані,

тобто вважаються заздалегідь включеними в покривне дерево не-

залежно від їхніх довжин (наприклад, з причини зручності корис-

тування ними). У такому випадку алгоритм побудови починаєть-

ся з мінімального (максимального) ребра серед тих, що не вклю-

чені у покривне дерево.

8.4. Задача про розміщення школи

Задачі розміщення пов’язані з вирішенням проблем оптима-

льного розташування у певних регіонах пунктів обслуговування,

таких як: торговельні центри, станції техобслуговування, автоза-

правні станції, пости пожежної охорони, лікарні, туристичні

центри, склади, пошти, готелі і т. д. Математична структура та-

116