Найти дерево минимального веса графа и его вес. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по высшей математике
Найти дерево минимального веса графа и его вес

Найти дерево минимального веса графа и его вес .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Найти дерево минимального веса графа и его вес.

Решение

Потяни, чтобы посмотреть

Минимальное остовное дерево – остовное дерево графа, имеющего минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него ребер.
Используем алгоритм Краскала.
В начале текущее множество ребер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех ребер, добавление которых к уже имеющемуся множеству не вызовет появление в нем цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству . Когда таких ребер больше нет, алгоритм завершен. Подграф данного графа, содержащий все его вершины и найденное множество ребер, является его остовным деревом минимального веса.
Количество шагов: 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 не используются, т.к

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу