Минимизация сети

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

Решение

Итерация 1.

Начнем построение с вершины 1. Обозначим:

С - множество связанных вершин

- множество несвязанных вершин.

Тогда

Итерация 2.

Ближе всех к связанному множеству вершин расположена вершина 5, так как

Тогда

Итерация 3.

Ближе всех к связанному множеству вершин расположены вершины 2 и 6, так как

.

Включим во множество связанных вершин вершину 2.

Тогда

Итерация 4.

Ближе всех к связанному множеству вершин расположена вершина 6, так как

Тогда

Итерация 5.

Ближе всех к связанному множеству вершин расположены вершины 3 и 4, так как

Включим во множество связанных вершин вершину 3.

Тогда

Итерация 6.

Ближе всех к связанному множеству вершин расположена вершина 7, так как

Тогда

Итерация 7.

Ближе всех к связанному множеству вершин расположена вершина 9, так как

Тогда

Итерация 8.

Ближе всех к связанному множеству вершин расположена вершина 11, так как

Тогда

Итерация 9.

Ближе всех к связанному множеству вершин расположена вершина 12, так как

Тогда

Итерация 10.

Ближе всех к связанному множеству вершин расположена вершина 10, так как

Тогда

Итерация 11.

Ближе всех к связанному множеству вершин расположена вершина 4, так как