728x90 반응형 포드 풀커슨1 [Algorithm] network flow (포드 풀커슨, 에드몬드 카프) 최대 유량 파이썬 구현 Network flow 다음과 같은 그래프가 있다고 하자. 각 에지의 가중치는 용량인데 용량은 흐를 수 있는 유량의 최대량이다. 네트워크 플로우 문제는 시작점 s에서 t까지 보낼 때 최대값을 가지는 플로우를 구하는 문제이다. a/b라고 할 때 b는 유량의 총량인 용량을 의미하고 a는 현재 흐르는 유량을 의미한다. 당연히 a가 b보다 클 수는 없다. 다음 그림은 s에서 5만큼 t로 보낼 때의 예시이다. 최소 컷 컷이란 노드들을 두 개의 집합으로 분할하는 것이다. 시작점 s와 도착점 t는 서로 다른 집합에 있어야 한다. 아래는 두 집합 { s, a, c, d } 와 { b, t }로 나눈 예시이다. 다음과 같이 a->b, d->b, d->t 간선들이 컷에 속해있다. 해당 간선들의 비용 총합을 컷의 비용 총합.. 2023. 6. 16. 이전 1 다음 728x90 반응형
