그래프에서 모든 독립적 인 연결 찾기

Question

나는 방향이없는 그래프가 있습니다. 두 노드 사이의 모든 독립 연결을 찾는 방법에 대한 효율적인 알고리즘이 있습니까? 독립적으로이 연결은 공통 노드를 가질 수 있지만 공통 에지를 가질 수는 없다는 것을 의미합니다.

이 예에서 0에서 8까지의 2 개의 독립적 인 연결이 있습니다 (0-2-3-4-8 또는 0-5-6-7-8). 나는 이미 보아 왔던 "pseudo-erasing"edge를 사용하면서 breadth-first 검색 알고리즘을 지속적으로 사용했다. 문제는 내가 그래프를 통해 이런 식으로 갈 수 있다는 것입니다 : 0-5-4-8 이는 다른 경로를 만들 수 없기 때문에 올바르지 않습니다.

도움 주셔서 감사합니다.

Answer 1

당신이 관심있는 것은 소스와 싱크 사이의 문제를 해결하는 것입니다 (관심있는 노드 중 첫 번째 노드는 소스이고 두 번째 노드는 싱크 임).

Here이 작업에 대한 접근법을 읽을 수 있습니다. 기본적으로 나는 소스와 싱크 사이의 최대 흐름이 min cut과 같음을 증명하는 정리에 연결됩니다. 최소 컷은 소스와 싱크를 연결 해제하기 위해 제거해야하는 최소 엣지 수입니다.

Ford Fulkerson max flow algorithm을 실행하면 알고리즘이 완료된 후 역순 에지가 용량을 갖는지 고려하여 소스에서 싱크까지 다른 경로를 재구성 할 수 있습니다. 마지막 메모 - Ford Fulkerson은 고전 그래프로 고전적으로 묘사됩니다. 당신의 방향이없는 경우에 효과가 있도록하려면 각 가장자리를 반대 방향을 향한 두 개의 분리 된 가장자리로 표현하십시오. 모든 초기 용량은 1과 같아야합니다.