Минимальное остовного дерева....

Question

Минимальное остовного дерева....

DINERO Ученик (91), открыт 1 неделю назад

Добавьте к данной задаче граф (и исходного, и с минимальным остовным деревом):
Дан граф с 7 вершинами и следующими ребрами и их весами:
Вершина 1 соединена с вершиной 2 весом 4
Вершина 1 соединена с вершиной 3 весом 6
Вершина 2 соединена с вершиной 3 весом 2
Вершина 2 соединена с вершиной 4 весом 5
Вершина 3 соединена с вершиной 4 весом 3
Вершина 3 соединена с вершиной 5 весом 11
Вершина 4 соединена с вершиной 5 весом 7
Вершина 5 соединена с вершиной 6 весом 1
Вершина 4 соединена с вершиной 6 весом 8
Вершина 6 соединена с вершиной 7 весом 9
Найти минимальное остовное дерево.
Решение:
1) Сортируем ребра по весу: (5, 6), (1, 2), (3, 4), (6, 7), (2, 3), (4, 5), (4, 6)
2) Добавляем в остовное дерево ребра по порядку, но избегаем образования циклов: (5, 6), (1, 2), (3, 4), (6, 7)
Минимальное остовное дерево: (5, 6), (1, 2), (3, 4), (6, 7)

Answer 1

Исходный граф:
Вершина 1 соединена с вершиной 2 весом 4.
Вершина 1 соединена с вершиной 3 весом 6.
Вершина 2 соединена с вершиной 3 весом 2.
Вершина 2 соединена с вершиной 4 весом 5.
Вершина 3 соединена с вершиной 4 весом 3.
Вершина 3 соединена с вершиной 5 весом 11.
Вершина 4 соединена с вершиной 5 весом 7.
Вершина 5 соединена с вершиной 6 весом 1.
Вершина 4 соединена с вершиной 6 весом 8.
Вершина 6 соединена с вершиной 7 весом 9.
Сортировка ребер по весу:
(5, 6) - вес 1
(1, 2) - вес 4
(3, 4) - вес 3
(6, 7) - вес 9
(2, 3) - вес 2
(4, 5) - вес 7
(4, 6) - вес 8
Добавление ребер в остовное дерево:
Добавляем ребро (5, 6) с весом 1.
Добавляем ребро (1, 2) с весом 4.
Добавляем ребро (3, 4) с весом 3.
Добавляем ребро (6, 7) с весом 9.
Таким образом, минимальное остовное дерево состоит из следующих ребер:

(5, 6) - вес 1
(1, 2) - вес 4
(3, 4) - вес 3
(6, 7) - вес 9