을 감안할 때 : 모든 노드 하나만 다른 노드 (에 연결해야합니다 구축 그래프 주어진 제약
에서 시작하여 연결할 수 있어야 나에게 그런 할머니를 줄 것이다 알고리즘이 있나요 aph 만약 가능하다면 가장 높은 노드 수를 가진 그래프를 만들거나 줄 수 있습니까?
다항식 시간으로 할 수 있습니까?
그렇지 않으면 충분한 솔루션을 충분히 빠르게 제공하는 알고리즘이 있습니까?
정확하게 이해하면 NP-Complete problem 인 Hamiltonian cycle을 찾으려고합니다.
이 n 노드의 수를하자 :
왜 문제 해밀턴 사이클을 찾는 것과 같습니다. 각 노드가 정확히 하나의 다른 노드에 연결된다는 제약 조건이 주어지면 솔루션의 가장자리는
n입니다. 각 노드에 도달 할 수 있어야하기 때문에 각 노드는 의 꼬리와 적어도 하나의 가장자리 인입니다. 그러나 해결책은 n 가장자리를 가지므로 각 노드는 꼬리로 정확히 한쪽 가장자리가됩니다. 솔루션은 따라서 경로의 조합입니다. 모든 모서리가 다른 모든 모서리에서 도달 할 수 있어야한다는 제약 조건은 솔루션을 해밀턴 순환으로 만듭니다.
올바른 예입니다. 주어진 문제는 해밀턴 사이클을 찾는 것과 같습니다. 왜 그들이 동등한지를 보여줄 수 있다면 좋을 것입니다. – interjay
이것은 해밀턴 순환이 아니며, 아마도 최소 해밀턴 경로 일 수 있습니다. NP 하드 인 세일즈맨 – watbywbarif
@amit : 주어진 제약 조건을 풀 수있는 유일한 방법은 해밀턴 사이클을 만드는 것입니다. 루트가 둘 이상의 노드에 연결되어야하기 때문에 "모든 잎이 나중에 루트에 연결되어있는"트리의 솔루션은 조건에 맞지 않습니다. – interjay
직접 최소 스패닝 트리 알고리즘을 검색하십시오.
이 확인 같습니다 또한 http://www.utdallas.edu/~rbk/papers/dmdst.pdf
문제는 NP-어렵다.
편집 : 그것은 물론, 해밀턴 사이클 문제를 http://www.proofwiki.org/wiki/Directed_Hamilton_Cycle_Problem_is_NP-complete
Heh, 최대 연결 수에 대한 제한이 주어지면 여행 판매원 문제로 축소됩니다. – watbywbarif
지정 스패닝 트리는 노드가 다른 노드로부터 도달 할 수있는 주어진 제약 조건에 맞지 않습니다. 예를 들어 다른 노드에서 루트에 연결할 수 없습니다. – interjay
@interjay 네,하지만 나중에이 조건이 추가되었습니다;) – watbywbarif
다항식 시간을 감독한다 편집 후 - O를 (N (N-1)/2), 제약하지 않는 자체가 그가 ONT 노드의 수를 따라 달라집니다. –
이것은 표준 문제입니다. 나는 당신이 노드 목록을 받았기 때문에 당신이 혼란 스럽다고 생각합니다. 왜 노드 수가 가장 많은지 물어보십시오. 노드는 변하지 않습니다 ... 무엇이 충분히 빠릅니까? 예, 다항식으로이 작업을 수행 할 수 있습니다. – Adrian
두 번째 노드 목록은지도입니까? list1의 모든 노드는 list2의 노드에 연결할 수 있습니까? 또는 어떤 세부 사항? – amit