우주수첩의 우주먼지

# Ford-Fulkerson Algorithm Max-Flow 문제를 해결할 수 있는 대표적인 알고리즘이다. 주어진 그래프 G와 현재 Flow f로 정의되는 잔여 그래프(residual graph) Gf를 이용해서 해결된다. # Residual graph 초기화 G의 vertex와 edge를 모두 G0로 copy한다. G0의 edge 중 one-way-path edge를 edge(v,u)를 G0에 추가한다. 이때 edge(v,u)의 capacity는 0으로 정의한다. one-way-path : edge(u,v)는 있으나 edge(v,u)는 없는 경우 2번의 작업상태에 있는 그래프를 G'이라고 칭할 예정이다. #Augumenting path : 증가 경로 G'의 source 에서 sink 까지 가는 pa..

# 네트워크 플로우 (Network Flow) - 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는지를 측정하는 알고리즘 # 필요 용어 정리 capacity (용량): edge가 수용할 수 있는 값 flow (유랑) : 실질적으로 보내는 값 source : indegreee가 0인 vertex sink : outdegree가 0일 vertex (수첩의 개입) 이라고 정의하기에는 너무 두루뭉실 뜬구름이 뭉게뭉게여서 다시 설명을 하자면 육상 트랙의 라인 수 == capacity 트랙에서 한 번에 뛰어야 하는 선수의 수 == flow 라고 생각하면 앵간 편하지 않을까 싶기도 한댱 ㅇㅅㅇ... 뭔가 일반화된 그래프의 시각으로 봤을 때 start 점이 source / finish 지점이 sink라고..