2
각 가장자리를 한 번만 교차하거나 각 꼭지점을 교차해야한다는 제한은 없습니다.유향 그래프에 특정 노드에서 시작하는 모든 가장자리를 사용하는 경로가 있는지 어떻게 결정합니까?
이러한 경로가 존재할 때 필요한 (Eulerian 경로 존재에 대한 노드의 등급과 같이) 필요하거나 충분한 그래프의 속성이나, 존재하지 않거나 존재하지 않는다는 것을 증명하는 알려진 알고리즘이 있습니까? 하나 (아마도 시작부터 모든 에지를 통과하는 최소 경로를 찾는다)?
강하게 연결된 구성 요소가 단일 슈퍼 노드로 무너져 내린 가장 강력한 몇 가지 가능성을 고려한 다음 결과 그래프가 모든 가장자리를 덮는 단순한 "링크 된 목록"그래프와 같은지 확인하십시오. 시작 노드/슈퍼 노드는 항상 현재 노드에서 단일 에지를 말하고, 나가는 에지 (및 슈퍼 노드라면 모든 내부 에지)를 방문한 것으로 계산하고 리프 노드에 도달하면 모든 에지가 계산되었는지 확인합니다. 이 솔루션에서는 중복되는 경우에도 원래 가장자리를 모두 보존해야합니다 (예 : 연결된 구성 요소 A, B, C를 슈퍼 노드 S로 축소 한 후 F에서 A, F에서 B로 F에서 C로 단순화 된 그래프에서 동일한 초 노드 S를 가리 키지 만 모두 보존 됨). 죄송합니다 올바르게 표현되지 않은 경우, 나는 답변을 기다리는 동안이 솔루션을 구현하려고합니다.
더 쉬운 방법이 있습니까? 아니면 사이클/연결된 구성 요소를 처리하는 더 나은 알고리즘? 그래프가 비순환 적이기 때문에 매우 쉽게 풀 수 있습니다.
그래프가 강하게 연결되어 있는지 단순히 확인하지 않습니까? – nbrooks
분명히 해 주시겠습니까? 모든 가장자리를 모두 소비하십시오. – smk
적어도 한 번 이상 건너십시오. –