Пусть G = (V, E_1 ∪ E_2) будет исходным (взвешенным, полностью связным) графом и G' = (V, E_1) графом, полученным путем удаления ребер в наборе E_2.
Рассмотрим график G'', полученный путем сжатия связанных компонентов G' (т. Е. Каждый связанный компонент становится одной вершиной), где две вершины G'' являются соседями тогда и только тогда, когдасоответствующие компоненты в G' были соединены ребром в E_2.По сути, это означает, что ребра G'' являются ребрами в наборе E_2 (ребра, которые были удалены из исходного графа).
Обратите внимание, что добавление подмножества ребер из E_2 в G' восстанавливает (полную) связность G' тогда и только тогда, когда эти ребра соединяют все вершины из G''.Самый дешевый способ сделать это - выбрать минимальное связующее дерево на G'' (по отношению к весам ребер).Из ваших комментариев я предполагаю, что вы знаете, что такое минимальное остовное дерево и как его можно вычислить.
Краткое изложение в одном предложении: Минимальный по стоимости набор ребер, необходимый длявосстановить связь можно найти, вычисляя на графе минимальное (затратное) остовное дерево, которое получается путем сжатия каждого из соединенных компонентов в одну вершину и содержащее в качестве своего набора ребер ребра, которые были удалены из исходного графа.