Условие задачи
Для графа, представленного на рис. 20, задайте весовую функцию ребер и постройте остовное дерево минимального веса, полагая, что ребра имеют различные положительные целые веса. Минимальный вес ребра равен 8.
Ответ
Зададим весовую функцию ребер, минимальный вес ребра равен 3, полагая, что ребра имеют различные положительные целые веса.
Вводим в дерево ребро минимального веса (v0,v1)=3
Выбираем ребро минимального веса смежное с вершинами (v0,v1) : (v1,v6)=4
Выбираем ребро минимального веса смежное с вершинами (v0,v1, v6) это (v6,v7)=5
Выбираем ребро минимального...
Потяни
