networkflow

네트워크 플로우(Network Flow)

네트워크 플로우(Network Flow)란? 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘으로 네트워크 데이터 전송, 교통 체증 등 다양한 분야에서 활용되고 있음 최대 유량(Maximum Flow)이란? 최대 유량이란 가중치가 있는 방향그래프(Weighted Directed Graph) G와 시작 노드 S, 도착 노드E 가 주어졌을 때, 각 엣지의 용량(Capacity)를 고려하여 S에서 E로 흘려보낼 수 있는 유량의 최대값을 말하는 것이다. 이 때, G의 각 에지 가중치를 용량(capacity)라고 하며 (u,v)의 용량을 c(u,v)라고 쓴다. 예로, 아래와 같은 그래프 G가 있다고 할 때, A에서 D로 최대한 많은 유량을 보내려고 할 때 가장 합리적인 양은 가..

이분 매칭(Bipartite Matching)

이전 게시글인 에 이어지는 알고리즘 개념 글입니다 https://codingsmu.tistory.com/109 이분 매칭(Bipartite Matching)이란? 네트워크 플로우의 개념중에서 이분 그래프(Bipartite Graph)에서의 최대 유량(maximum flow)을 구하는 경우로, 에지의 용량(capacity)이 전부 1인 이분 그래프에서의 최대유량(maximum flow)을 구하는 문제는 이분 그래프에서의 최대 매칭(maximium matching)과 동치이다. 이때 매칭은, 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미로 이분그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉 혹은 에드몬드 카프 알고리즘을 이용해 구해줄 수 있으나, DFS를 이용하여 O(V*E)시간에 쉽게 구현할 수 있다..