flow network

훨씬 상세하고 잘 정리된 글이 있어 다음으로 대체

Definition

Flow network(플로우 네트워크) \(G = (V, E)\)

  • 방향 그래프
  • \((u,v) \in E\) 일때, 용량 \(c(u, v) \ge 0\)
  • \((u,v) \in E\) 일때, \((v,u)\) 가 존재하지 않음
  • 자기순환 루프를 허용하지 않음
  • 출발점(source) \(s\) 와 도착점(sink) \(t\)가 존재
  • \(\forall v \in V\)에 대해 \(s \rightsquigarrow v \rightsquigarrow t\) 경로가 존재.

A flow in G

아래 두가지 특성을 만족시키는 실수 함수 \(f : V \times V \rightarrow R\)

  • Capacity constraint: \(\forall u,v \in V\)일때, \(0 \le f(u,v) \le c(u,v)\)
  • Flow conservation: \(\forall u,v \in V - \{s,t\}\) 일때 다음을 만족
\[\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)\]
  • 플로우는 용량을 넘어설수없다
  • 시작과 끝 정점을 제외하고 각 정점에서 들어오는 플로우와 나가는 플로우는 같다

\(\left\vert f\right\vert : f\)의 값

\[\left\vert f\right\vert = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s)\]

The Ford-Fulkerson method

FORD-FULKERSON (G, s, t)
1 for each edge (u, v) ㄷ G.E
2       (u, v).f = 0
3 while there exists a augementing path p 
    from s to t in the residual network G_f
4       c_f(p) = min {c_f(u, v) : (u, v) is in p}
5       for each edge (u, v) in p
6       if (u, v) ㄷ E
7       (u, v).f = (u, v).+ C_f(p)
8       else (v, u).f = (v, u).f - c_f(p)

시작점 s, 도착점 t을 가진 플로우 네트워크 \(G = (V, E)\)와 \(G\)상의 플로우 \(f\), \(u, v \in V\)라 고려하자.

residual capacity \(c_f(u, v)\)

  • \(c_f(u, v) = c(u, v) - f(u, v)\) (if \((u, v) \in E\))
  • \(c_f(u, v) = f(v, u)\) (if \((v, u) \in E\))
  • \(c_f(u, v) = 0\) (else)

residual network(잔여 네트워크) \(G_f = (V_f, E_f)\)

\[E_f = \{(u,v) \in V \times V : c_f(u, v) > 0\}\]

역방향 간선이 존재함으로 엄밀한 플로우 네트워크는 아니지만 플로우를 정의 할 수 있다.

augmentation(증강)

\(f\)가 \(G\)의 플로우고, \(f'\)을 잔여 네트워크 \(G_f\)상의 플로우라 할때, \(f \uparrow f'\)을 \(V \times V \rightarrow R\)로의 함수로 정의

  • \((f \uparrow f')(u, v) = f(u, v) + f'(u, v) - f'(v, u)\) (if \((u, v) \in E\))
  • \((f \uparrow f')(u, v) = 0\) (else)

\(\left\vert f \uparrow f' \right\vert\)은 \(\left\vert f \uparrow f' \right\vert = \left\vert f \right\vert + \left\vert f' \right\vert\)을 만족하는 \(G\)에서의 플로우다.

증명생략

augmenting path(증강 경로)

증강 경로 \(p\)는 잔여 네트워크 \(G_f\)의 \(s\)에서 \(t\)로의 단순 경로이다. 이 잔여 네트워크의 정의로인해 경로 상의 잔여 용량을 실제 플로우 네트워크 \(G\)로의 플로우에 증가시키는 것이 가능하다.

증강 경로 \(p\)의 각 간선에서 증가시킬 수 있는 플로우의 최대량을 residual capacity of p

\(c_f(p) = min \{c_f(u,v) : (u, v)\) is on \(p\}\)

증명 생략

포드 풀커슨 메소드는 잔여 네트워크 상의 증강경로를 찾고 \(c_f(p)\)를 구하여 더하는 것이 알고리즘의 핵심이다.

Cut

\(Cut(S,T)\) \(V\)를 \(s \in S\) \(t \in T\) 가 되도록 하는 \(S\), \(T = V -S\)로의 분할이다.

\(Cut(S, T)\)의 net flow는 \(f(S, T)\)로 표시하고 다음을 만족한다.

\[f(S, T) = \sum_{u \in S} \sum_{v \in T}f(u,v) - \sum_{u \in S} \sum_{v \in T}f(v, u)\]

용량

\[c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u,v)\]

minimum cut은 네트워크의 모든 Cut 중 용량이 최소가 되는 Cut

\[f(S, T) = \left\vert f \right\vert\]

증명 생략

Max-flow min-cut theorem(최대 유량 최소 컷 정리)

다음 조건들은 동등 하다.

  1. \(f\) 는 \(G\)상의 maximum flow다
  2. 잔여 네트워크 \(G_f\) 가 증강 경로를 가지지 않는다.
  3. \(G\)상의 임의의 절단 \(cut(S,T)\)에 대해, \(\left\vert f \right\vert = c(S,T)\)

증명 생략

Edmonds-Karp algorithm

path p를 찾는 방법을 BFS로 수행.

Posted 2021-08-03
clrs