# 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 Dire..
