[Network Flow Applications] Min Cut Problem

# Min Cut Problem

 

• == vertex patitioning
• Source s, sink t를 가진 directed graph G =(V,E)에서 s-t cut (s∈S, t∈T)를 만족하는 vertex들의 partition(S,T)으로 정의한다.
• 한 partition은 무조건 source만, 다른 한 쪽의 partition은 무조건 sink만 포함.
  • 한 partition에 sink 와 source를 모두 포함할 수는 없다.
• s-t cut의 capacity C(s,t)는 u∈S, v∈T를 만족하는 모든 edge의 capacity의 총 합으로 정의한다.
• 시작 vertex는 source에서, 종료 vertex는 sink에서 존재해야 한다.

 

 

# Max-flow & Min cut theorem

• Directed graph G에서 F가 flow라고 할 때 아래 조건들은 equivalent하다.

1. f는 G의 maximum flow이다.
2. Residual graph Gf는 augumenting path를 가지고 있지 않다.
3. f는 G의 Min Cut capacity이다.

• 2->3 을 이용하여 G=(V,E)인 Min Cut을 아래와 같이 구할 수 있다.
  1. G의 maximum flow f와 이 때 해당하는 residual graph Gf를 구한다.
     • Gf : 더 이상의 augumenting path를 가지고 있지 않음.
  2. Gf에서 s로부터 DFS 혹은 BFS로 positive capacity edge 만을 사용하여 reachable 한 vertexset을 S라고 하고 T를 V/S로 둠.
     • T∈S인 경우 graph에 존재하는 augumenting path가 있음을 표시. 
  3. (S,T)는 G의 Min Cut이 되며, Min Cut의 Capacity는 u∈S,v∈T를 만족하는 모든 G의 edge(u,v)의 capacity 총 합이됨.

 

참고 url : https://www.crocus.co.kr/755

최소 컷(Minimum Cut)

 

 

 

다 덤벼 ㅡ ㅅ ㅡ