최소 경로 - 적어도 한 번 모든 에지

Question

나는 강하게 연결되어있는 많은 사이클이있는 그래프를 보내고 있으며, 최소한의 사이클을 얻어야합니다. 나는 그래프에서 가장 짧은 사이클 인주기를 가져와야하며, 모든 에지는 적어도 한 번 덮여 있어야 함을 의미합니다.

일부 알고리즘이나 이론적 배경을 찾고 있었지만 중국 우체부 알고리즘 만 발견했습니다. 그러나이 솔루션은 유향 그래프가 아닙니다.

아무도 도와 줄 수 있습니까? 감사합니다

편집 >> 그 그래프의 모든 모서리는 같은 비용이 - 예 1

Answer 1

이 신문을보십시오 - Directed Chinese Postman Problem. 그것은 올바른 문제 분류이지만 (더 이상 제한이 없다고 가정 할 때).

이론을 읽는 중이라면 알고리즘 설계 매뉴얼의 this page을 잘 읽으십시오.

키 견적 (지향 버전 후반) 오일러이를 확인하도록

최적 배달부 투어는 그래프 G에 해당하는 에지를 추가하여 구성 할 수있다. 특히, 우리는 G에서 홀수 차수 꼭지점의 각 쌍 사이의 최단 경로를 찾습니다. G에있는 두 개의 홀수 차수 꼭지점 사이에 경로를 추가하면 둘 다 짝수 도로 바뀌므로 오일러 그래프에 가까워집니다. G에 더할 최단 경로 집합을 찾는 것은 홀수 차수 버텍스의 그래프에서 최소 가중치 완전 일치를 식별하는 것으로 감소합니다. 여기서 에지 (i, j)의 가중치는 i에서 i까지의 최단 경로 길이입니다. j. 유향 그래프의 경우, bipartite 매칭을 사용하여 해결할 수 있습니다. 여기서 정점은 가장자리가 더 많은지 또는 가장자리가 많은지에 따라 분할됩니다. 그래프가 Eulerian이되면, 위에서 설명한 절차를 사용하여 실제주기를 선형 시간으로 추출 할 수 있습니다.

Answer 2

에 나는 그것이 최적의 의심을하지만 그래프가 사이클을 보장 가정 큐 기반 검색을 할 수 있습니다. 각 큐 항목에는 경로를 나타내는 노드 목록이 포함됩니다. 큐에서 요소를 제거 할 때 가능한 모든 다음 단계를 큐에 추가하여 노드를 다시 방문하지 않도록하십시오. 마지막 노드가 첫 번째 노드와 같으면 최소주기를 찾았습니다.

Answer 3

당신이 찾고있는 것을 "오일러 경로"라고합니다. 당신은 기본이 here 및 알고리즘에 대한이, 플러의 알고리즘이라는 알고리즘이 있으며, 충분한 정보를 찾기 위해 그것을 구글 그것을 위해 구글이나보고 here

Answer 4

네트워크가 지시 가장자리의 전체 구성하는 특별한 경우를 취할 수 있습니다 다항식 시간으로 풀면된다. 연결된 그래프의 가장자리가 모두 전달됩니다

과 : (PDF 파일의 페이지 28)을 감독 그래프 문제에 대한 알고리즘의 명확한 설명은 115 페이지에서 시작 - 나는 원래 용지가 Matching, Euler tours and the Chinese postman (1973) 생각 그래프 는 오일러 투어 지정 위한 특히 간단하고 편안한 알고리즘 ...가, 대칭

G는 제 스패닝 arborescence를 찾아 내기위한 방향성 대칭 접속 그래프 오일러 여행을 찾는 알고리즘 G. 그 다음, 축약의 루트 r을 제외하고 어떤 노드 n도 에서 에 대한 임의의 순서를 지정하면 arborescence의 가장자리 인 의 순서대로 n 길에서.루트 r의 경우, 가장자리가 r에서 멀어 지도록 순서를 지정하십시오.

이 알고리즘은 van Aardenne-Ehrenfest와 de Bruin이 특정 유향 그래프 [1]에서 모든 오일러 둘러보기를 열거하기 위해 사용되었습니다 : .