Hani_Levenshtein

이번 포스팅의 주제인 이분 매칭 문제는 네트워크 플로우 연장선에 있는 문제입니다. 2020/09/09 - [알고리즘] - 포드 풀커슨 알고리즘 우선, 이분 매칭을 공부하기 위해선 이분 그래프라는 것을 알 필요가 있습니다. 이분 그래프란 두 집합으로 나뉜 그래프의 정점들의 간선이 상대 집합에 속한 정점으로 연결된 그래프입니다. 성별이나, 주종관계, 사람과 작업 등의 관계가 주어진다면 이를 이분 그래프로 표현할 수 있습니다. 여기서 이분 그래프의 각 요소들을 문제의 조건에 맞춰 대응시키는 것이 이분 매칭 문제입니다. 이런 이분 매칭 문제는 앞서 소개한 네트워크 플로우를 이용하면 쉽게 풀 수 있습니다. 이분 그래프의 각 간선을, 연결되지 않은 것(0) 과 연결된 것(1) 인 용량이 1인 간선으로 고려할 수 있..

최단 경로 문제에서는 정점 간 간선의 가중치의 합이 최소가 되는 경로의 길이를 찾으려 했습니다. 네트워크 플로우는 시작점에서 도착점까지 유량을 최대로 흘려보내는 것이 목적입니다. 어떻게 보면 가중치의 합을 최대로 만드는 것인데 여기서 용량이라는 개념이 추가됩니다. 네트워크 유량은 항상 3가지 규칙을 만족해야 합니다. 1. 용량 제한 속성 flow(u,v)