네트워크 흐름 문제 (Network Flow Problem)

 네트워크 흐름 문제(Network Flow Problem)은 일종의 그래프를 응용한 문제입니다. Programming Challenge를 풀다가 이해가 가지 않아 찾아 보았습니다. Programming Challenge 번역판의 설명은 원서가 이상한 건지 번역이 이상한건지 읽어도 읽어도 뜻을 이해할 수 없었습니다. 혹(?) Programming Challenge 번역판의 설명만으로 모든게 다 이해되는 분...? 공감?
 네트워크 흐름 문제에서 가장 중요한 것은 가중치 그래프에서 간선(Edge)의 값의 의미를 이해하는 것입니다.  일반적인 가중치 그래프 문제에서 간선(Edge)은 해당 간선을 이동하기 위한 소요 비용으로 간선의 가중치 전체를 사용합니다. 하지만 네트워크 흐름 문제에서 가중치는 허용 가능한 크기가 됩니다. 즉, 5라는 가중치를 갖는다는 것은 최대 5의 값만큼 사용할 수 있다는 의미가 됩니다. 또한 일반적인 가중치 그래프 문제에서 간선은 단 한번 사용할 수 있습니다. 하지만 네트워크 흐름 문제에서는 N번 만큼 나누어 해당 가중치 이하로 가중치를 사용하며 간선을 이용할 수 있습니다.  그래서 흔히 파이프라인에 비유하는 것입니다. 
 국내의 블로그나 사이트에서는 관련 네트워크 흐름 문제 관련 자료를 찾기 힘들어 영문 자료를 찾던 중  해당 문제에 대한 정의와 Ford-Fulkerson method를 자세하게 설명한 PPT가 있어 소개하고자 합니다. 페이지를 넘기는 방식으로 애니메이션으로도 설명하고 있어 그나마 이해하기 쉽습니다. 물론 PPT 읽다보면 두통이 밀려오는 건 어쩔 수 없습니다. 굉장히 수학적으로 정의하고 설명하고 있기 때문입니다.

Network flow problems
구굴형이 찾아 준것인데 저는 굉장히 만족했습니다. 혹 다른 PPT 찾으실려면 Network flow problems ppt로 검색하시면 됩니다.

※참고로 저는 네트워크 흐름 문제의 개념을 찾는데 공부 시간의 반을 보내야 했습니다. 막상 풀어서 이야기하면 굉장히 쉬운 개념인데 기존 가중치 그래프에 대한 고정관념이 박혀있었기 때문이었던거 같습니다.