1
이 증명은 어디에서나 건너 뛰고 Min-Cut-Max-Flow 정리의 결과라고합니다. 일반적으로 다음과 같습니다.유량 네트워크에서 min cut의 조합과 교차점을 표시하는 방법은 또한 min cut입니다.
S1과 S2를 유량 네트워크의 최소 컷이라고합시다. 그러면 S1∪S1과 S1∩S2도 분 삭감입니다.
이 사실이 정확히 어떻게 증명 될 수 있습니까?
A
답변
2
min-cut-max-flow 정리에 따르면 모든 최대 흐름과 모든 절단에 대해 교차하는 모든 호가 포화 된 경우에만 해당 절단이 최소가됩니다 (보완 여유의 유사 함, 관측 가능 컷을 가로 지르는 총 유량이 전체 유량 임). 최소 컷 S1과 S2가 주어지면 S1 ∪ S2를 횡단하는 모든 아크는 S1을 교차하거나 S2를 횡단합니다. 따라서 모든 아크는 포화됩니다. S1에 대한 동등한 ∩ S2.
관련 문제
- 1. 프롤로그 - 노동 조합과 교차점을 설명해야합니다.
- 2. 배열의 MIN()
- 3. MIN VBA
- 4. 향상시킬 min()
- 5. MIN 절에 문제가 발생했습니다.
- 6. Min/Max Chars
- 7. K'th Min 간격 집합에서
- 8. (min-device-width) 및 (min-width)는 무엇을 사용해야합니까?
- 9. MATLAB에서 max-min 검색
- 10. Meteor.js에서 $ min mongo query를 사용하는 방법은 무엇입니까?
- 11. MySQL - MIN/MAX 값에서 MIN/MAX 날짜를 가져 오는 방법
- 12. 오라클 SQL - 데이터 세트의 MIN 값을 찾기 있지만, MIN 계산에
- 13. Rand_Max * (max-min) + min << what is that?
- 14. GLSL min/max nomarlization
- 15. PowerPivot : Column - Min (Column)
- 16. SQL MIN() & GROUP BY
- 17. min() 함수의 부작용
- 18. 배열에서 Groovy pop min
- 19. 조건부 MIN 쿼리
- 20. Modelica - min 속성을 설정하십시오.
- 21. jQuery css min-height
- 22. min() arg 빈 시퀀스
- 23. min-width 사용 방법
- 24. 재귀 min-heap 오류?
- 25. min() sqlite3에서 작동하지 않습니다
- 26. LINQ에서 MIN 함수 사용
- 27. Windows Mobile min spec
- 28. TensorFlow : argmax (-min)
- 29. MIN() 함수 Ms 액세스
- 30. Max-Flow Min-Cut