의 양방향 최소 스패닝 트리 최소 가중치를 갖는 서브 - 그래프를 제공하는 데 사용하지만, 그래프에서 다른 정점 어떤 정점에서 이동을 허용 할 수있는 알고리즘 (임의의 두 꼭지점 사이의 경로가 항상 존재한다는 가정하에). 이러한 알고리즘은가중 가장자리와 유향 그래프 기븐 유향 그래프
을 존재 하는가? 그들은 신속하게이 알고리즘을 발견 Vitalii의 위키 백과 링크를 따라 시간을내어, 스스로를 잘하지 않았다하더라도
이는 NP-하드 것으로 보인다.
나는 해밀턴 순환 문제를 줄일 수 있다고 믿는다 : 그래프 G (V, E)가 주어지면 나타나는 모서리에 대해 가중치 1을 표시하고 모서리에 대해 가중치 100 (| V | +1) '티. DG는 체중의 스팬 서브 그래프와 정확히 연결된 최소 체중 | V | G가 해밀턴주기를 가지고있는 경우에만. http://portal.acm.org/citation.cfm?id=844363
분할 두 개의 노드로 그래프의 모든 노드. 하나의 노드는 들어오는 모든 모서리를 원본 노드에 적용하고 다른 노드는 모든 모서리를가집니다. 그런 다음 모든 모서리에 방향을 놓으십시오. 그래야 그래프가 움직입니다. 그런 다음 그래프의 표준 MST 알고리즘을 실행할 수 있습니다 (프림의, 크루스 칼의) 당신은 모든 원래의 노드가 다른 모든 원래의 노드로 여행을 할 수 있도록 할 것이다. 강력한 서브 그래프 문제에 걸쳐 연결 최소 무게 :
불행하게도 이것은 최종 그래프에 불필요한 가장자리를 추가하기 때문에 작동하지 않습니다. 가장자리를 가질 필요가 없더라도 최소한 하나의 노드에 여분의 가장자리가 첨부됩니다. 예를 들어 정점 A, B, C 및 에지 AB, BA, BC, CB, AC, CA, 단지 에지 AB, BC, CA. 될 수있는 그래프의 최소 스패닝와 그래프 그러나 당신의 방법을 사용하여 그 3 개의 모서리는 서로 붙지 않을 것이고, MST를 마무리하기 위해 추가적인 모서리가 추가되어야 할 것입니다. –
어떤 노드를 선택하고 그것을 돌려 :
용지가 여기에 근사 알고리즘을 가지고있다.
는 아마도 가장 강력하게 연결 서브 그래프 (노드의 최소 수를 가능한 한 제거) 찾을 찾으셨습니까, 또는 서브 그래프에 걸친 최소 무게는 (어떤 노드 제거는 허용되지 않습니다)?제목은 '스패닝 트리'라고 말합니다. 그래서 나는 후자를 추측합니다. –
@ 모론 : 아, 나는 그것을 놓쳤다. 어떤 경우에, 당신의 대답은 정확하다. –
이것은 디렉터드 스타이너 트리입니다. Steiner Tree는 NP-Hard입니다.
당신은 여기에 몇 가지 aproximate 알고리즘을 찾을 수 있습니다
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.8774&rep=rep1&type=ps
하지만 Steiner Tree는 루트가 필요합니다. 그렇지 않습니다. – highBandWidth
알고리즘에 의해 최적의 루트 버텍스를 찾을 수 있지만 버텍스 세트와 함께 루트를 지정할 수 있습니다. – jwinandy
에드몬드의 알고리즘은 그래프의 모든 노드가 루트에서 액세스 할 수 있음을 보장, 모든 노드가 다른 모든 노드에서 액세스 할 수없는 것이다. –
이것은 NP 하드입니다. -1. –
내 링크의 NP 분류와 원래의 질문과의 관련성은 무엇입니까? – Mathew