Решение
Минимальное остовное дерево – остовное дерево графа, имеющего минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него ребер.
Используем алгоритм Краскала.
В начале текущее множество ребер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех ребер, добавление которых к уже имеющемуся множеству не вызовет появление в нем цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству
. Когда таких ребер больше нет, алгоритм завершен. Подграф данного графа, содержащий все его вершины и найденное множество ребер, является его остовным деревом минимального веса.
Количество шагов: n-k=5-1=4
а) ребро с минимальным весом – AE и CD, выбираем AE (вес 2)
T1=V,E1;E1=A,E
б) ребро с минимальным весом – CD (вес 2)
T2=V,E2;E2=E1∪C,D
в) ребро с минимальным весом – BD (вес 3)
T3=V,E3;E3=E2∪B,D
г) ребро с минимальным весом – AC (вес 4)
T4=V,E4;E4=E3∪A,C
Ребра AD, BC, BE не используются, т.к