0
무연 그래프를 가장자리 분리 된 최소 경로와 사이클로 분해하고 싶습니다.최소 경로와 순환으로 무향 그래프를 분해하십시오.
제 아이디어는 가장 긴 경로를 먼저 취하는 것이지만 다항식이 아닙니다.
다항식 알고리즘을 알고 있습니까?
A
답변
0
최대 흐름/최소 컷 - 최소 컷 수를 사용하여 그래프를 반으로 자르는 것이 재미있을 수 있습니다 - 가장 긴 경로 알고리즘을 실행하기 위해 조그만 크기의 부분 집합을 얻을 때까지 반복적으로 반복합니다.
0
Jens Schmidt가 설명한대로 그래프의 "체인 분해"에 관심이있을 수 있습니다.
Ear Decompositions에 관한 위키 백과 문서에 언급되어 있습니다. 나는 그것을 직접 구현했고, 좋은 간단한 알고리즘이다.