Консультация № 187017
23.12.2012, 09:06
100.00 руб.
0 3 1
Здравствуйте! У меня возникли сложности с таким вопросом:
https://rfpro.ru/upload/9007 - задача 1.

Обсуждение

давно
Профессор
230118
3054
24.12.2012, 23:25
общий
это ответ
Здравствуйте, Aleksandrkib!

Шаг 1. Начать с вполне несвязного графа G, содержащего N вершин.

Шаг 2. Упорядочить ребра графа G в порядке неубывания их весов.

Шаг 3. Начав с первого ребра в этом перечне, добавлять ребра в графе Q, соблюдая условие: добавление не должно приводить к появлению цикла в Q.

Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в Q не станет равным N-1. Получившееся дерево является каркасом минимального веса.

Прикрепленные файлы:
давно
Профессор
230118
3054
24.12.2012, 23:26
общий
Второй
Прикрепленные файлы:
4a2fa5ea87b23f8a6062aba5780cf380.png
давно
Профессор
230118
3054
24.12.2012, 23:26
общий
Первый
Прикрепленные файлы:
c93f660d3deea8d27e0cefd1afabe9dd.png
Форма ответа