Существует ли алгоритм для нахождения максимального веса, охватывающего слабосвязный DAG в ориентированном графе, где каждый разрез имеет слабосвязные множества (существует хотя бы один направленный путь от одного множества к другому)? Или это сложная задача NP? В предыдущем вопросе по этой теме не было указано https://mathoverflow.net/questions/31864/algorithms-for-maximum-weighted-spanning-connected-dag-directed-acyclop-graph слабая или сильная связность, поэтому я хотел быть более точным.
Алгоритмы максимального взвешенного охвата слабосвязной DAG
comment
Это может быть лучше подходит на cs.stackexchange.com.
- person templatetypedef schedule 27.12.2012
comment
Хаф, единственное, что у меня на уме, это как-то модифицировать алгоритм Чу-Лю-Эдмондса...
- person malejpavouk schedule 27.12.2012
Ответы (2)
Надеюсь, это не слишком поздно. В упомянутом случае легко подвести и Крускала, и Прим. Рассмотрим граф с двумя узлами: A --> B (вес 10), B --> A (вес 6), B --> A (вес 6) (да: два ребра из B в A; ничего в графе defn исключает!). Крускал сначала выбрал ребро A -> B и застрял. Прим выберет одно из ребер от B до A, а затем застрянет. Макс. взвешенный ациклический подграф — это тот, который содержит оба ребра из B в A. Это подграф, и он ацикличен!
Лучший Рави
person
Ravi
schedule
20.09.2013
Имеет ли слабосвязный граф связи из одной вершины в другую в обоих направлениях?
- person andigor; 02.04.2015
Под застреванием вы имеете в виду работу в бесконечном цикле или невозможность продвижения, потому что ни одно ребро не соответствует критерию выбора? Такие расплывчатые заявления в ответ на технические вопросы меня чертовски раздражают.
- person Abhijit Sarkar; 21.12.2018
Кажется, что ваше слабое условие связности просто связано с тем, что базовый неориентированный граф связан. Это достаточно легко; вы можете использовать Kruskal или Prim или любой другой ваш любимый алгоритм минимального связующего дерева.
Сильносвязный подграф минимального веса является NP-полным; заметим, что любой такой подграф имеет по крайней мере |V| ребер и что он имеет ровно |V| ребра тогда и только тогда, когда это гамильтонов цикл.
Вы можете выбрать вершину в качестве «корня» и попросить указать путь от каждой вершины к корню в вашем подграфе. Это проблема «минимального разветвления». Как указал @matejpavouk, для этого существует квадратичный алгоритм, созданный Чу, Лю и Эдмондсом.
person
tmyklebu
schedule
27.12.2012
Я могу найти пример с четырьмя вершинами, где Крусалу или Приму не удается найти подграф с максимальным весом без направленных циклов. Кажется, что ваше слабое условие связности просто связано с тем, что базовый неориентированный граф связан. Это просто означает, что между двумя наборами любого разреза есть хотя бы одно направленное ребро. В этом вопросе существует разница между алгоритмами ориентированного и неориентированного графа, поэтому Крускал и Прим терпят неудачу.
- person vkaul11; 28.12.2012
Существует по крайней мере одно направленное ребро между двумя множествами любого разреза означает, что если я выберу набор вершин S, который не является ни пустым, ни всеми вершинами, то между S и V есть ребро — S, верно? Это именно связность базового графа, и там работают Крускал/Прим. Если вам нужно ребро от S до V-S и ребро от V-S до S, это сильная связность, и ваша задача является NP-полной. Если вы имеете в виду что-то другое, сделайте это явным (и желательно приведите пример того, почему то, что вы хотите, не совпадает со связностью базового графа).
- person tmyklebu; 28.12.2012
