Page 58 - 4386

6 АЛГОРИТМИ ПОБУДОВИ ДЕРЕВ

Розглянемо таку задачу. У керуванні шосейних доріг

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

зв'язати п'ять міст деякого району, причому не обов'язково

безпосередньо кожну пару міст (рис. 6.1 а). Побудуємо граф,

вершини якого відповідають містам, а ребра – дорогам, які

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

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

задачі побудови для відповідного графа кістякового дерева. Це

можливо в силу того, що ребра будь-якого кістякового дерева

з'єднують кожну вершину (місто) графа з будь-якою іншою

вершиною (містом).

Нехай відомо також вартість прокладання дороги між

кожною парою міст (рис. 6.1 в). Припишемо кожному ребру вагу,

яка дорівнює вартості будівництва відповідної дороги. Складання

проекту будівництва дороги тепер можна звести до задачі

побудови для відповідного графа кістякового дерева мінімальної

вартості.

а b с d е

а - 5 50 80 90

b 5 - 70 60 50

с 50 70 - 8 20

d 80 60 8 - 10

а б е 90 50 20 10 -
в

Рисунок 6.1

57