hellogaon

네트워크 유량(Network Flow)은 네트워크 플로우라고도 불리며 이를 설명하기 전,유량 그래프(Flow Graph)에 대해서 먼저 알아봅시다.유량 그래프란 각 간선에 용량이라는 추가 속성이 존재하는 방향 그래프로각 간선은 유량을 흘려보낼 수 있는 파이프 역할을 합니다.이 그래프에서는 소스(Source)와 싱크(sink)가 존재하며소스는 유량이 시작되는 정점, 싱크는 유량이 도착하는 정점을 뜻합니다.유량 그래프에서는 아래와 같은 3가지의 속성을 만족합니다. 1. 용량 제한 속성 : 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.2. 유량의 대칭성 : u에서 에서 v로 유량이 들어올 경우 v입장에서는 u로 음수의 유량을 보내는 것과 같다.3. 유량의 보존 : 소스와 싱크를 제외하고 각 정점에 들..