mincut의 가장 작은 $ s $ -component

Question

소스 $ s $ 및 싱크 $ T $ 에서는 최대 흐름을 계산합니다. 그런 다음 $ a $ $ (a, b) $ 을 찾을 수 있음을 알고 있습니다. SPAN> 소스 $ S $ 에서 도달 할 수있는 정점 집합이 되십시오.

내 질문은이 세트 $ a $ 가능한 가장 작은 $ s $ -Component입니까? 나는 그것이 있다고 생각한다. 정확하게, $ (a ^ *, v) \ setminus a ^ * $ 은 최소 컷, $ a $ $ (a, v \ setminus a) $ 은 $ size (a ^ *) \ leq 크기 (a) $ .

다른 Min-Cut $ (C, D) $ 에 대해, $ a \ subset C $ ?. 나는 이것이 이것이 사실이라고 생각합니다. 그러나 나는 그것을 증명할 수 없다.

어떤 직관 / 힌트가 많이 감사합니다!

편집

$ s $ -component : Min-Cut은 $ G $ 의 $ (a, b) $ < / span>, 여기서 $ a $ 은 소스 $ s $ 및 $ b $ 싱크 $ t $ 이 들어 있습니다. $ s $ -component w.r.t. 그런 다음 최소 컷은 설정 $ a $ 입니다.

"small" $ s $ -Component I 의미 $ s $ - 가장 작은 카디널리티가있는 8 / span> ...에 minimal $ s $ -component w.t.에 여러 가지가있을 수 있는지 궁금합니다. I.E. $ S $ - 동일한 카디널리티를 사용하여 구성된 구성 요소는 설정되지만 세트가 같지 않습니다. 최소 $ s $ -component가 있는지 궁금합니다. 모든 $ S $ -Components에있는 정점 집합입니다.

Answer 1

나는 대답이 예라고 믿습니다. 최대 유동에서 이러한 방식으로 구성된 모든 분 컷은 가능한 모든 최소 컷 중에서도 최소한의 카디널리티가있을 것입니다.

동일한 비용으로 여러 분 컷이있을 수 있습니다. 그들은 격자 구조를 형성합니다 : 2 분 컷의 교차점은 또 다른 분이이며, 2 분의 컷의 노조는 또 다른 min-cut입니다. 이 격자의 "가장 작은"요소를 식별하여 모든 분홍의 교차로를 취함으로써 식별 할 수 있습니다. 이것은 또 다른 최소 컷이 될 것이며, 모든 분홍색의 가장 작은 카디널리티가 있습니다.

내가 이해할 때, 최대 유동으로부터 얻은 최소 절단이 항상이 "가장 작음"이라는 것을 증명할 수 있습니다. 또는 왼쪽과 싱크 $ T $ 오른쪽에서 $ s, t $ -max-flow가 항상 "가장 왼쪽"컷이 될 것입니다. 또한 다른 Min-Cut가 당신이 추출하는 것과 정확히 똑같은 것과 정확히 발견 된이 절단의 수퍼 세트가 될 것입니다.

이러한 결과에 대한 참조 및 기타 관련 자료는 다음 질문을 참조하십시오 (참고 : 개인적으로 확인하지 않으므로 자신을 두 번 확인해야합니다.) :

Ford-Fulkerson은 항상 왼쪽 최소 삭감

을 생성합니다.

https://stackoverflow.com/a/8101250/781723

https://stackoverflow.com/q/26696312/781723

https://stackoverflow.com/q/41964288/781723

Answer 2

answer you 귀하의 첫 번째 질문 : 꼭 필요한 것은 아닙니다. 기성품 최대 유량 또는 최소 컷 알고리즘은 최소 카디널리티가 아닌 임의의 최소 분할 분할을 생성합니다. 그러나 최대 흐름 출력이 원하는 것과 같이 그래프를 보강 할 수 있습니다.

$ a, v \ setminus a $ 및 $ b, v \ setminus b $ 최소 컷 파티션 : $$ \ 델타 (A, V \ SETMINUS A)=Δ (B, V \ SETMINUS B)=min_ {x \ subseteq v, s \ in x} \ 델타 ( x, v \ setminus x) $$ 이제 $ \ span 클래스="수학 컨테이너"> $ t $ 에서 다른 모든 정점에서 가장자리를 추가하십시오. $ a $ 및 $ b $ 에 해당하는 새로운 컷은 업데이트 된 가중치를 가지고 있습니다. $$ \ 델타 (A, V \ SETMINUS A) + | A | \ CDOT \ VALEPSILON, \\ \ delta (b, v \ setminus b) + | b | \ cdot \ vaepsilon $$ 각기. 첫 번째 용어가 모두 동일하기 때문에 $ \ varepsilon | $ 및 $ \ varepsilon | b | $ 은 순서를 결정합니다. 따라서 새로운 그래프에서 최소 컷은 원래 그래프의 최소 카디널리티 인 분할 파티션입니다. 유일한주의 사항은 $ \ varepsilon $ 을 충분히 선택해야합니다. 새로운 그래프에서 최소 컷이 원래 그래프에서 최소 컷인지 확인해야합니다. ...에 가중치가 정수이면 $ 1 / | v | $ 보다 작은 값은 충분합니다.

( $ \ star) $ : $ \ delta (x, v \ setminus x) $ $ x $ 및 $ v \ setminus x $ 사이의 크로스 - 모드의 가중치의 합을 나타냅니다.