Алгоритм решения

Начнем с любого узла и соединим его с ближайшим уз­лом сети. Соединенные два узла образуют связное множество, а остальные — несвязное. Далее в несвязном множестве выбе­рем узел, который расположен ближе других к любому из узлов связного множества. Скорректируем связное и несвязное мно­жества и будем повторять процесс до тех пор, пока в связное множество не попадут все узлы сети. В случае одинаково уда­ленных узлов выберем любой из них, что указывает на неодно­значность (альтернативность) "минимального дерева-остова".

Пример. Телевизионная фирма планирует создание кабель­ной сети для обслуживания 5 районов-новостроек. Числа на ребрах указывают длину кабеля (рис. ниже). Узел 1 — телеви­зионный центр. Отсутствие ребра между двумя узлами означа­ет, что соединение соответствующих новостроек либо связано с большими затратами, либо невозможно.

Рисунок 14 – Ход решения.

Найтитакое соединение кабелем районов-новостроек, что­бы длина его была минимальной.

Решение. Минимальная длина кабеля: 1+3+4+3+5 = 16 (рис.14).

 

 

Пример. На рис. 30.20 указаны длины коммуникаций, свя­зывающих 9 установок по добыче газа в открытом море с рас­положенным на берегу приемным пунктом. Поскольку скважи­на 1 расположена ближе всех к берегу, она оснащена необходи­мым оборудованием для перекачки газа, идущего с остальных скважин в приемный пункт.

Построить сеть трубопровода, соединяющего все скважины с приемным пунктом и имеющего минимальную общую длину труб.

Рисунок 15 – Ход решения.

Решение. Минимальная длина труб: 5+6+4+3+7+5+ 6+5=41