약한 연결이있는 방향성 그래프에서 DAG가 약하게 연결된 최대 가중치를 찾는 알고리즘이 있습니까? 모든 절단에는 약하게 연결되어있는 집합이 있습니다 (하나의 집합에서 하나 이상의 집합 경로가 있음). 다른)? 아니면 NP 어려운 문제입니까? 이 주제에 대한 이전 질문은 연결이 약하거나 연결이 강한 https://mathoverflow.net/questions/31864/algorithms-for-maximum-weighted-spanning-connected-dag-directed-acyclic-graph을 지정하지 않았으므로보다 정확 해지고 싶습니다.약 가중치 가중치가 최대가되는 알고리즘 DAG
약한 연결 상태는 기본 무향 그래프가 연결되어있는 것으로 보입니다. 이것은 충분히 쉽습니다. 당신은 Kruskal 또는 Prim 또는 가장 좋아하는 최소 스패닝 트리 알고리즘이 무엇이든간에 사용할 수 있습니다.
최소 무게의 강하게 연결된 부분 그래프는 NP 완성입니다. 그러한 서브 그래프는 적어도 | V | 모서리와 정확히 | V | 가장자리가 해밀턴 사이클 인 경우에만 해당됩니다.
"루트"로 정점을 선택하고 하위 그래프에서 모든 정점에서 루트까지의 경로가 있어야 할 수도 있습니다. 이것이 "최소의 흡착력"문제입니다. @matejpavouk이 지적했듯이 Chu, Liu, Edmonds 때문에 이차 알고리즘이 있습니다.
Krusal 또는 Prim이 지시 된 사이클없이 최대 가중치가있는 부분 그래프를 찾지 못한 4 개의 꼭지점이있는 예제를 찾을 수 있습니다. "약한 연결 상태는 기본 무향 그래프가 연결되어있는 것처럼 보입니다." IT는 단지 두 세트의 컷 사이에 하나 이상의 방향성이 있다는 것을 의미합니다. 이 시점에서 방향 및 무향 그래프 알고리즘에는 차이가 있으므로 Kruskal과 Prim은 실패합니다. – vkaul11
"어떤 컷의 두 세트 사이에 하나 이상의 방향성있는 가장자리가 있습니다"라는 것은 비어 있거나 모든 꼭지점이 아닌 꼭지점의 집합 S를 선택하면 S와 V - S 사이에 모서리가 있음을 의미합니다. ? 이것이 바로 "기본 그래프의 연결성"이며 Kruskal/Prim은 거기에서 작동합니다. S에서 V - S까지의 모서리와 V - S에서 S까지의 모서리를 원한다면 그것은 강력한 연결성이고 문제는 NP 완전합니다. 다른 것을 의미하는 경우 명시 적으로 지정하십시오 (기본 그래프의 연결과 원하는 것이 왜 다른지에 대한 예제를 제공하는 것이 바람직 함). – tmyklebu
희망이 없습니다. 언급 된 사례에 대한 Kruskal과 Prim 모두 실패하기 쉽습니다. A -> B (가중치 10), B -> A (가중치 6), B -> A (가중치 6) (예 : B에서 A로 두 가장자리, 그 것을 배제!). Kruskal은 먼저 A -> B edge를 선택하여 붙어 있습니다. 프림은 B에서 A로 가장자리 중 하나를 골라 붙어 있습니다. 최대 weighted acyclic subgraph는 B에서 A까지의 양쪽 가장자리를 포함하는 서브 그래프입니다. 서브 그래프이며 비순환 적입니다.
최저 라비
약한 그래프가 한 방향에서 다른 방향으로 연결되어 있습니까? – Andigor
이 cs.stackexchange.com에 더 잘 맞는 수 있습니다. – templatetypedef
Huf, 내 마음에있는 유일한 방법은 Chu-Liu-Edmonds 알고리즘을 어떻게 든 수정하는 것입니다. – malejpavouk