Оглавление | Назад | Глоссарий понятий
Требуется спроектировать радиотрансляционную сеть, которая должна обслуживать семь населённых пунктов. Расстояния между пунктами приведены в таблице.
 |
рис. 2.24 |
Решение
Для решения данной задачи достаточно рассмотреть или только левую или только правую часть от главной диагонали матрицы. Воспользуемся левой частью таблицы.
Из элементов матрицы выбираем минимальный - (D,С) = 4. Обводим выбранный элемент кружком.
 |
рис. 2.25 |
Из оставшихся элементов выбираем минимальный - (D,E) = 8. Элемент обводим кружком. Чтобы выполнялось условие 2 пункты С и D не должны соединяться, поэтому элемент (Е,С) зачёркивается.
 |
рис. 2.26 |
Из невыделенных и незачеркнутых элементов минимальным является (D,B). Этот элемент обводится кружком. Элементы (С,В) и (Е,В) зачёркиваются.
 |
рис. 2.27 |
Минимальным элементом является (С,А) = 13. Элементы (В,А), (D,А) и (Е,А) зачеркиваются.
 |
рис. 2.28 |
Из невыделенных и незачеркнутых элементов минимальным является (F,E) = 15. Элементы (F,A), (F,B), (F,C) и (F,D) зачёркиваются.
|
рис. 2.29 |
В последней строке минимальным элементом является (G,E) = 18. Обводим этот элемент, и получаем остов, связывающий все семь пунктов. Все остальные элементы вычеркиваются.
 |
рис. 2.30 |
Длина минимального остова равна (С,А)+(D,B)+(D,С)+(Е,D)+(F,E)+(G,E) = 13+10+4+8+15+18 = 68.
Оглавление | Назад | Глоссарий понятий
