Двумя путями связующее дерево минимума ориентированного графа
Учитывая ориентированного графа со взвешенными краями, что алгоритм может использоваться для предоставления подграфа, который имеет минимальный вес, но позволяет перемещение от любой вершины до любой другой вершины в графике (под предположением, что пути между любыми двумя вершинами всегда существуют).
Такой алгоритм существует?
5 ответов
Это выглядит NP-трудным: проблема минимального веса сильно связного охватывающего подграфа.
Я считаю, что проблема гамильтонова цикла может быть сведена к ней: Учитывая граф G(V,E), построить диграф DG с весом 1 для ребер, которые появляются, и весом 100 (|V|+1) для ребер, которые не появляются. DG имеет минимальный вес сильно связного охватывающего подграфа с весом ровно |V| тогда и только тогда, когда G имеет гамильтонов цикл.
В этой статье есть алгоритм аппроксимации: http://portal.acm.org/citation.cfm?id=844363
Даже если они сами не были правильными, потратив время на то, чтобы пройти по ссылкам из Википедии Виталия, можно быстро обнаружить этот алгоритм:
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
Разделите каждый узел в графе на два узла. Один узел будет принимать все входящие ребра к исходному узлу, а другой будет иметь все исходящие ребра. Затем опустите направление на всех ребрах, чтобы граф не был направлен. Затем вы можете запустить стандартный алгоритм MST на графе (Prim, Kruskal), и вы убедитесь, что каждый исходный узел может быть перемещен любым другим исходным узлом.
Выберите любой узел и верните его.
Возможно, вы имели в виду найти наибольший сильно связанный подграф (возможно наименьшее количество удаленных узлов) или охватывающий подграф минимального веса (удаление узлов запрещено) ?
Это задача направленного дерева Штейнера. Как дерево Штейнера, это NP-Hard.
Некоторые приблизительные алгоритмы можно найти здесь:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps