목록2025/06/01 (1)
Elevation
그래프 (8) - 최대 유량(최대 유량 최소 컷 정리)
플로우그래프에서 파생된 개념인 네트워크 유량(Network Flow)에 대해 알아보자. 그래프의 각 간선에는 유량이 흐를 수 있는 값의 제한인 용량(capacity)이 있고, 유량을 발생시키는 정점인 S(source)와 유량이 최종적으로 도착하는 T(sink)가 있을 때, S에서 T까지 이동하는 경로에서 간선의 용량을 넘지 않도록 유량을 적절히 흘려보내는 것이 network flow의 개념이다. 도로의 폭에 따라 출발점에서 도착점까지 화물을 적절히 배송해야 하는 상황이나, 대역폭에 따라 데이터를 나누어 전송하는 상황 등 말 그대로 네트워크에서의 흐름을 계산해야 할 때 이용하는 개념이라고 보면 된다. 유량에는 다음과 같은 성질이 있다.$f(u,v)\leq c(u,v)$S, T를 제외한 정점에서 $\sum..
ps/graph
2025. 6. 1. 12:06