Планируется строительство газопровода который должен соединить 15 населённых пунктов в единую сеть. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
Планируется строительство газопровода который должен соединить 15 населённых пунктов в единую сеть

Планируется строительство газопровода который должен соединить 15 населённых пунктов в единую сеть .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Планируется строительство газопровода, который должен соединить 15 населённых пунктов в единую сеть. Стоимость строительства возможных участков газопровода указана в таблице. Участки, на которых строительство технически невозможно или слишком дорого, в таблицу не включены. Требуется найти схему газопровода, требующую минимальных затрат. Определить стоимость реализации найденного оптимального плана. A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A1 12 8 11 10 14 9 A2 7 15 16 11 9 A3 12 15 10 7 A4 11 9 8 A5 13 10 11 16 A6 12 9 10 A7 8 14 A8 9 10 A9 A10 12 A11 A12 A13 A14 A15

Решение

Потяни, чтобы посмотреть

Рассмотрим нагруженный неориентированный граф с вершинами А1-А12 и рёбрами, веса которых указаны в таблице. Мы рассматриваем 12 вершин, поскольку по условию задачи в остальные населенные пункты нецелесообразно строить газопровод.
Будем строить минимальный каркас (минимальное основное дерево) в этом графе . Реализацию алгоритма Краскала оформим в виде таблицы. Будем изображать графически выбираемые рёбра, чтобы избежать циклов. Поскольку есть 12 населенных пунктов соединенных между собой (вершин), должно быть 11 рёбер.
Рёбра Стоимость Отсутствие циклов Счётчик рёбер
(2;3) 7 + 1
(3;12) 7 + 2
(1;3) 8 + 3
(4;12) 8 + 4
(7;8) 8 + 5
(1;10) 9 + 6
(2;11) 9 + 7
(4;8) 9 + 8
(6;9) 9 + 9
(8;11) 9 - -
(1;7) 10 - -
(3;8) 10 - -
(5;9) 10 + 10
(6;12) 10 + 11
(8;12) 10 - -
(1;5) 11 - -
Мы выбрали 11 рёбер, поэтому дальнейшие пути не рассматриваем

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу