![]()
|
|||||||
Тема 11 задача 1. ЗадачаСтр 1 из 3Следующая ⇒ Тема 11 задача 1 Нахождение минимального остова в графе.
Алгоритм решения 1. Упорядочить ребра графа по возрастанию весов; 2. Выбрать ребро с минимальным весом, не образующее цикл с ранее выбранными ребрами. Занести выбранное ребро в список ребер строящегося остова; 3. Проверить, все ли вершины графа вошли в построенный остов. Если нет, то выполнить пункт 2.
Задача
Решение Для решения данной задачи достаточно рассмотреть или только левую или только правую часть от главной диагонали матрицы. Воспользуемся левой частью таблицы. Из элементов матрицы выбираем минимальный - (D,С) = 4. Обводим выбранный элемент кружком.
Из оставшихся элементов выбираем минимальный - (D,E) = 8. Элемент обводим кружком. Чтобы выполнялось условие 2 пункты С и D не должны соединяться, поэтому элемент (Е,С) зачёркивается.
Из невыделенных и незачеркнутых элементов минимальным является (D,B). Этот элемент обводится кружком. Элементы (С,В) и (Е,В) зачёркиваются.
Из невыделенных и незачеркнутых элементов минимальным является (F,E) = 15. Элементы (F,A), (F,B), (F,C) и (F,D) зачёркиваются.
В последней строке минимальным элементом является (G,E) = 18. Обводим этот элемент, и получаем остов, связывающий все семь пунктов. Все остальные элементы вычеркиваются.
Длина минимального остова равна (С,А)+(D,B)+(D,С)+(Е,D)+(F,E)+(G,E) = 13+10+4+8+15+18 = 68.
|
|||||||
|