#graph-algorithm
#граф-алгоритм
Вопрос:
Изначально нам дается полностью связный граф с помощью матрицы смежности. Затем некоторые ребра удаляются таким образом, что граф становится несвязным, и теперь у нас есть несколько компонентов этого несвязанного графа. Какова минимальная стоимость, необходимая для подключения всех компонентов?
Комментарии:
1. Вы имеете в виду минимальную стоимость сложности в O (n) терминах, чтобы найти минимальный набор ребер для добавления для повторного подключения всех компонентов? Или в количестве ребер? Вы могли бы просто выбрать существующий узел случайным образом и подключить к нему все остальные узлы, которых еще нет, что составило бы O (n) как по сложности алгоритма, так и по добавленным ребрам. Я полагаю, вы хотите сделать что-то еще?
2. Минимальные затраты с точки зрения весов ребер, которые необходимо добавить, чтобы снова сделать его связанным графом. (Аналогично концепции поиска минимального связующего дерева.)
3. Итак, ваш график является взвешенным графом (т. Е. Все ребра имеют веса)?
4. Да, все ребра имеют веса.
Ответ №1:
Пусть 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'' (относительно весов ребер). Из ваших комментариев я предполагаю, что вы знаете, что такое минимальное связующее дерево и как его можно вычислить.
Краткое изложение в одном предложении: набор ребер с минимальными затратами, необходимый для восстановления связности, может быть найден путем вычисления минимального (стоимостного) связующего дерева на графе, которое получается путем сжатия каждого из подключенных компонентов в одну вершину и которое содержит в качестве набора ребер ребра, которыебыли удалены из исходного графа.