주어진 네트워크에 고유 한 최소 커트가 있습니까?

Question

G = (V, E)를 s와 t가 소스 및 싱크 인 네트워크로 둡니다.

Determining the uniqueness of a min-cut

: f는이 사이트에 비슷한 질문을 발견 할 수있다

G.에서 고유 한 분 컷이 존재하는지 여부를 결정하는 알고리즘을 찾기 G.에서 최대 유량하자

이 잔류 그래프의에서 도달 가능한 모든 정점을 찾아 우리는

봐 같은 잔류 그래프를 G.에서 분 컷 (S, T)을 발견했습니다 대답 요약이 주어진 , t에서 시작. 화살표의 반대 방향으로 t에서 도달 할 수있는 꼭지점 그룹을 봅니다 (t에 도달 할 수있는 모든 꼭지점을 의미 함).

이 그룹은 또한 최소 컷입니다.

해당 절단이 원래 절단과 동일하면 하나만 있습니다. 그렇지 않으면, 당신은 방금 2 개의 상처를 발견했기 때문에, 원래의 것이 아마도 유일 할 수는 없습니다.

컷이 원래 컷과 동일하면 컷이 고유 한 이유가 무엇인지 이해할 수 없습니다. 다른 분노가 없다고 누가 약속 할 수 있습니까?

미리 감사드립니다.

Answer 1

사실, 나는 그 해결책을 이해하지 못합니다. 그러나 원래의 질문에서 davin이 제공 한 두 번째 대답은 절대적으로 정확합니다.

난 그냥 복사 여기

Given a minimum S-T cut, (U,V) with cut-edges E', we make one simple observation: 
If this minimum cut is not unique, then there exists some other minimum cut with 
a set of cut-edges E'', such that E'' != E'. 

If so, we can iterate over each edge in E', add to its capacity, recalculate the 
max flow, and check if it increased. 

As a result of the observation above, there exists an edge in E' that when 
increased, the max flow doesn't increase iff the original cut is not unique. 

내 자신의의 몇 가지 설명을 붙여 넣습니다
당신 : 당신이 실제로 증명할 필요가있는 무엇

이

there exists an edge in E' that when increased, the max flow doesn't increase 
<=> 
the original cut is not unique 

=>입니다 e 가장자리의 용량을 1 씩 늘리고 새로운 최대 흐름을 계산하면 남아 있습니다. 같은 것이므로 e은 새로운 최소 컷에 포함되지 않습니다. (e이있는 경우, min-cut의 속성에 따라 f (e) = e의 용량으로 증가합니다). e은 새로운 최소 컷이 아니기 때문에 우리가 알고있는 컷과 동일한 볼륨을 가진 원본 그래프의 최소 컷입니다. 따라서 원래 컷은 고유하지 않습니다.

< =
원래 컷이 고유하지 당신이 E에 가장자리 e하지만 E'에서 찾을 수 있습니다 의미 (의 그들 E 및 E'를 부르 자). 그런 다음 e의 용량을 1 씩 늘립니다. 새 그래프의 최소 컷을 계산할 때는 E'이 이미 있습니다. E'은 가장자리 e을 포함하지 않으므로, 최대 유량은 의심의 여지없이 동일하게 유지됩니다.

는

Answer 2

모순에 의해 첫 번째 방법 증명하는 또 다른 옵션 : 당신이 이해 희망 : 을 -> : 의 컷 가장자리 E '로 절단 한 최소한의 (S, T)이있다 가정 해 봅시다. E '에 속한 가장자리 e의 용량을 1 증가시키고 최대 흐름이 동일하게 유지되면 e가 새로운 min-cut에 있지 않음을 알 수 있습니다. (e가 E '에 있다면, min-cut의 특성에 따라 최대 유량이 증가 될 것이다). 그러나 처음에 우리는 전자가 E - 모순이라고 말했습니다.

Answer 3

당신이 말한 알고리즘은 제안 된 알고리즘보다 효율적입니다. 알고리즘 : 그래프 G = 용

(V, E)

1. 그래프에서 최대 유동을 찾아 R 마지막 잔류 그래프하자. s의
2. 실행 BFS (들로부터 도달 가능한 노드를 찾기가), 반전 가장자리 (t의 경로가 있음 노드를 찾을 수)와 t에서 그 X
3. 실행 BFS를 호출 할 수 있습니다, 그들이
4. 경우 Y로 호출 할 수 있습니다 X + Y = V ('+'노동 조합에서와 같이) 다른 FALSE,

짧은 설명 TRUE를 반환 : V/X를

가

2 단계에서 우리는 최소 절단을 결정하는 노드를 찾을 수 (X를) .X는 마지막 나머지 그래프에서 s로부터 도달 할 수있는 모든 노드의 집합입니다. 3 단계에서 마지막 나머지 그래프에서 t가 도달 할 수있는 노드들의 집합을 찾는다. 이 세트는 t에 가장 가까운 최소 절단 인 절단 (V-Y, Y)을 정의합니다. 4 단계에서 양쪽 끝 (X + Y = V)에서 동일한 절단을 한 다음 그래프에 고유 한 최소 절단이 있습니다.

복잡도는 주로 최대 흐름을 찾는 것입니다. Edmonds Karp O (| E |^2 | V |)와 BFS O (| E | + | V |).

제안 된 대답의 복잡성은 O (| V || E |^3)입니다.