Question

Задание 3. Постройте модель графа для решения следующей задачи: «В
некотором районе было решено провести газопровод между пятью деревнями А, В,
С, Д, Е. Стоимость прокладки газопровода указанна в таблице (тыс. у.е.):
А В С Д Е
А 1000 700 1000 1100
В 1000 999 1010 899
С 700 999 1010 900
Д 1000 1010 1010 1200
Е 1100 899 900 1200
Как провести газопровод, чтобы к газу были подключены все пять деревень, и
затраты при этом были минимальные?»

Answer 1

Ответ:

Найдём все варианты маршрутов из A в E и выберем самый короткий. Из пункта A можно попасть в пункты B, D. Из пункта B можно попасть в пункты C, D. Из пункта C можно попасть в пункты D, E. A—B—C—E: длина маршрута 7 км. A—D—B—C—E: длина маршрута 9 км. A—D—C—E: длина маршрута 6 км. Самый короткий путь: A—D—C—E. Длина маршрута 6 км.