호프크로프트 카프 알고리즘(Hopcroft-Karp Algorithm)은 더 빠른 시간복잡도의 이분 매칭 알고리즘으로앞서 이분 매칭에서 배운 포드-풀커슨 알고리즘을 변형한 방법의 시간복잡도는정점 개수가 V 간선 개수가 E일 때 O(VE)였으나호프크로프트 카프 알고리즘의 시간복잡도는 O(V^(1/2)E)입니다.이 알고리즘에서 아래와 같은 새로운 용어를 사용합니다. 1. 교차 경로(Alternating Path) : 그래프 위의 경로 중 매칭되어 있지 않은 정점으로부터 시작하여매칭을 이어주고 있지 않은 간선과 이어주고 있는 간선이 교차하는 규칙이 반복되는 경로2. 증가 경로(Augmenting Path) : 양 끝 정점이 매칭되어 있지 않은 교차 경로 증가 경로가 존재하면 이를 뒤집어 반드시 매칭 크기를 1..
디닉 알고리즘(Dinic's Algorithm)은 더 빠른 시간복잡도의 최대 유량 알고리즘으로네트워크 유량의 기본 알고리즘인 포드-풀커슨 알고리즘의 시간복잡도는정점 개수가 V 간선 개수가 E이며 문제의 답이 f일 때 min(O(Ef), O(VE^2))이였으나디닉 알고리즘의 시간복잡도는 O(V^2E)입니다.이 알고리즘에서 아래와 같은 새로운 용어를 사용합니다. 레벨 그래프(Level Graph) : 모든 정점에 대하여 소스로부터 거쳐야하는 최소 간선 수를 값으로 가지는 그래프(이 때 여유 용량이 있는 간선만 사용가능)차단 유량(Blocking Flow) : 레벨 그래프 상에서 인접하면서 자신보다 레벨이 1 큰 정점으로만 흐를 수 있을 때소스에서 싱크로 흐를 수 있는 최대 유량 이후 동작원리는 아래와 같습니..
MCMF(Minimum-Cost Maximum-Flow)는 최소 비용 최대 유량이라고도 불리며네트워크의 각 간선마다 유량을 1 흘려보낼 때 드는 비용이 정해져 있을 때최대 유량을 어떻게 흘려보내야 비용의 합을 최소화 할 수 있는 지를 알아내는 방법입니다.그래프파트에서 다뤘던 간선에 비용이 있는 그래프에서의 최단경로를 매번 찾은 뒤이 경로로 흐를 수 있는 최대 유량을 찾아서 흘려보내면서이전에 찾은 경로의 비용 합 * 유량을 반복하여 계속 더해주며 구합니다.이 때의 최단 경로 알고리즘이 유량 그래프의 특성에 따라 음의 가중치가 있는 그래프에서도 가능하여야 하므로앞서 배운 벨만 포드 알고리즘의 변형인 SPFA(Shortest Path Faster Algorithm)을 사용합니다.SPFA의 시간복잡도는 벨만 포..
이분 매칭(Bipartite Matching)문제는 이분 그래프에서 최대 매칭을 구하는 문제입니다.이 때 이분 그래프(Bipartite Graph)란 정점을 두 그룹으로 나눠서 모든 간선이 서로 다른 그룹의 정점들을 연결 할 수 있도록할 수 있는 그래프로 이 그래프에서 끝 점이 공유하지 않는 간선의 집합을 구하는 문제로도 설명할 수 있습니다.이러한 문제를 네트워크 유량 문제로 접근한다면 소스와 한 그룹의 모든 정점을 잇고 다른 그룹의 모든 정점과 싱크를 이은 뒤서로 다른 그룹을 연결하는 간선을 포함해서 모든 간선을 비용이 1인 간선으로 만들어주고 최대 유량을 구하게 된다면최대 매칭을 알아낼 수 있습니다.이 때 네트워크 유량의 포드-풀커슨 알고리즘을 그대로 사용하여 문제를 풀지 않고 이분 그래프의 특성을 ..
최소 컷(Minimum Cut)은 민 컷이라고도 불리며 네트워크에서 용량이 가장 작은 컷을 말합니다.이 때 컷이란 소스와 싱크가 각각 다른 집합에 속하도록 그래프의 정점을 두 개의 집합으로 나눈 것으로소스가 속한 집합을 S, 싱크가 속한 집합을 T라 할 때S에서 T로 가는 간선들의 용량 합을 컷의 용량, 유량 합을 컷의 유량이라고 합니다.컷은 아래와 같이 2가지의 속성은 만족합니다. 1. 컷의 유량은 소스에서 싱크로 가는 총 유량과 같다.2. 컷의 유량은 용량과 같거나 더 작다. 이 때 최소 컷 최대 유량 정리(Max-Flow Min-Cut Theorem)에 의하여최소 컷은 네트워크 유량 문제에서의 최대 유량과 동일하다는 것을 이용하여 문제를 풀 수 있습니다.네트워크 그래프에서 최소 용량의 간선을 자르고..
네트워크 유량(Network Flow)은 네트워크 플로우라고도 불리며 이를 설명하기 전,유량 그래프(Flow Graph)에 대해서 먼저 알아봅시다.유량 그래프란 각 간선에 용량이라는 추가 속성이 존재하는 방향 그래프로각 간선은 유량을 흘려보낼 수 있는 파이프 역할을 합니다.이 그래프에서는 소스(Source)와 싱크(sink)가 존재하며소스는 유량이 시작되는 정점, 싱크는 유량이 도착하는 정점을 뜻합니다.유량 그래프에서는 아래와 같은 3가지의 속성을 만족합니다. 1. 용량 제한 속성 : 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.2. 유량의 대칭성 : u에서 에서 v로 유량이 들어올 경우 v입장에서는 u로 음수의 유량을 보내는 것과 같다.3. 유량의 보존 : 소스와 싱크를 제외하고 각 정점에 들..