Network Flow

• 그래프의 가중치는 '거리' 이외에도 '용량' 의 개념이 중요하다.

• 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 유량을 보낼 수 있는지를 계산하는 문제를 네트워크 유량(network flow) 문제라고 한다.

• 유량 네트워크 : 각 간선에 용량(capacity) 라는 추가 속성이 존재하는 방향 그래프이다. 이 그래프는 다음 세가지 속성을 만족해야 한다.
  • (u->v 로 가는 간선의 용량을 c(u,v), 실제 흐르는 유량을 f(u,v)라 가정한다)
  • 용량 제한 속성 : f(u, v) <= c(u, v)
  • 유량의 대칭성 : f(u, v) = -f(v, u), v로 유량을 보낼 경우, u 의 입장에서는 -v를 보낸 것이라 생각할 수 있다.
  • 유량의 보존 : 각 정점에 나가고 들어오는 용량의 합은 정확히 같아야 한다. (한 정점에서 다른 모든 정점으로 보내는 유량의 합은 0이다)

• 유량 네트워크 문제는 소스(source)와 싱크(sink) 가 존재하며, 소스에서 출발하여 싱크에 도착해야 한다. 소스와 싱크는 유량의 보존 법칙이 성립하지 않는다.

• 문제를 푸는 방법 : 포드-풀커슨 알고리즘, 애드몬드-카프 알고리즘, 디닉 알고리즘 등

• • 문제의 종류 : 이분 매칭, MCMF

참고 자료

• 종만북 : 991 페이지 ~