Двухстороннее минимальное остовное дерево ориентированного графа

Question

Учитывая ориентированный граф со взвешенными ребрами, какой алгоритм можно использовать для получения подграфа, который имеет минимальный вес, но допускает перемещение из любой вершины в любую другую вершину графа (при условии, что пути между любыми двумя вершинами всегда существует).

Существует ли такой алгоритм?

Answer 1

Несмотря на то, что они не были правы сами по себе, но нашли время, чтобы перейти по ссылкам Виталия на Википедию, быстро нашли этот алгоритм:

http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm

Answer 2

Это выглядит как NP-Hard: проблема минимального веса сильно связанного остовного подграфа.

Я полагаю, что проблема гамильтонова цикла может быть сведена к этому: учитывая граф G (V, E), построим орграф DG с весом 1 для появляющихся ребер и весом 100 (| V | +1) для ребер, которые т. DG имеет минимальный весовой сильно связный остовный подграф веса точно | V | тогда и только тогда, когда G имеет гамильтонов цикл.

В статье приведен алгоритм аппроксимации: http://portal.acm.org/citation.cfm?id=844363

Answer 3

Разделить каждый узел в графе на два узла. Один узел примет все входящие ребра к исходному узлу, а другой будет иметь все исходящие ребра. Затем опустите направление на все ребра, чтобы график был ненаправленным. Затем вы можете запустить стандартный алгоритм MST для графа (Прима, Крускала) и убедиться, что каждый исходный узел может быть пройден любым другим исходным узлом.

Answer 4

Это проблема Directed Steiner Tree . Как Дерево Штейнера, это NP-Hard.

Вы можете найти некоторые приблизительные алгоритмы здесь:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps

Answer 5

Выберите любой узел и верните его.

Возможно, вы имели в виду найти самый большой сильно-связанный подграф (возможно наименьшее число удаленных узлов) или минимальный весовой охват подграф (удаление узлов не допускается)