Для данного графа найдите остов максимального веса. Бесплатный доступ к контрольной работе

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

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

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

Условие

Для данного графа найдите остов максимального веса. 1-2 3-4 1-5 2-3 1-4 2-7 3-7 3-6 4-5 5-6 6-7 2 8 5 -1 2 6 0 5 3 7 1

Решение

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

Воспользуемся, например, алгоритмом Прима поиска минимального остова: на каждом шаге алгоритма минимальное остовное дерево достраивается следующим образом – к множеству ребер уже построенного дерева добавляется ребро минимального веса, один конец которого находится в дереве VT, а второй – в множестве вершин, не входящих в дерево.
Чтобы применить алгоритм, меняем знаки ребер на противоположные:
1-2 3-4 1-5 2-3 1-4 2-7 3-7 3-6 4-5 5-6 6-7
-2 -8 -5 1 -2 -6 0 -5 -3 -7 -1
На начальном этапе VT=∅ . Начнем строить минимальное дерево с вершины v1.
1. Выбираем инцидентное ребро минимального веса:
cv1;v5=-5
Таким образом:
VT=v1;v5;ET=v1;v5
2. Из ребер, инцидентных вершинам из множества VT=v1;v5 наименьший вес имеет ребро:
cv5;v6=-7
Таким образом:
VT=v1;v5;v6;ET=v1;v5,v5;v6
3

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

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

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