찾기 나는 다음과 같은 알고리즘을 사용하고 <a href="https://i.stack.imgur.com/RI4aR.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/RI4aR.jpg" alt="enter image description here"></a></p> <p>다음 네트워크의 최소 컷 찾기 위해 노력하고

Question

:

1. 실행 포드-Fulkerson에 알고리즘을하고 고려를 최종 잔차 그래프.

2. 잔여 그래프에서 소스에서 도달 할 수있는 버텍스 세트를 찾습니다.

3. 도달 가능한 정점에서 도달 불가능한 정점까지의 모든 에지는 최소 절단 에지입니다. 모든 가장자리를 인쇄하십시오.

   - s->b->h->t **value: 1** 
   - s->d->e->t **value: 1** 
   - s->c->h->i->m->d->g->t **value: 0.5** 
   

   그래서 최대 유량 (따라서 최소 컷) 250과 같다 : 첫 번째 단계에서

, 제 3 개 알고리즘은 경로를 발견한다. 나중에 내가 이런 식으로 끝낼 네트워크에서 상기 경로를 제거하려고 할 때

그러나 :

도달 가능한 정점은 3.5에 해당하는 컷을 형성 S, C 및 시간입니다.

무엇이 누락 되었습니까? 일반적으로 최소 절단을 얻는 것처럼 그래프를 탐색 할 수없는 이유는 무엇입니까?

Answer 1

잔여 그래프에서 가장자리의 용량을 늘릴 때마다 반대쪽 가장자리의 용량을 같은 양만큼 늘려야합니다.

예 그래프 :

: 여기

는 후방 에지없이 잔류 그래프 (a 분 컷을 구성하지 않음) S로부터 도달 정점의 집합이다

그리고 min-cut이있는 올바른 나머지 그래프는 다음과 같습니다.

Answer 2

나는 잔류 그래프의 당신의 정의는 잔류 그래프에 에지 A-> B를 넣어 것으로, 가정의 경우 :

(방향 A-> B에 일명 앞으로 흐름과 용량 사이에 다른이가)

가장자리) b) 방향 B-> A (뒷면 가장자리라고도 함)에 약간의 흐름이 있습니다.

이 정의에서 2 단계가 잘못되었습니다.

최소 자르기를 찾으려면 처음부터 앞쪽 가장자리 만 걸어야합니다. 이제 시작점에서 R까지 도달 할 수있는 꼭지점을 표시하고 R '으로 끝낼 수 있습니다. 이제 R과 R '사이의 모서리가 잘립니다. 그리고 절단의 크기는 R과 R '사이의 흐름입니다.