[Network Flow] 네트워크 플로우

# 네트워크 플로우 (Network Flow)

- 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는지를 측정하는 알고리즘

 

# 필요 용어 정리

• capacity (용량): edge가 수용할 수 있는 값
• flow (유랑) : 실질적으로 보내는 값
• source : indegreee가 0인 vertex
• sink : outdegree가 0일 vertex

---

(수첩의 개입)

이라고 정의하기에는 너무 두루뭉실 뜬구름이 뭉게뭉게여서 다시 설명을 하자면

• 육상 트랙의 라인 수 == capacity
• 트랙에서 한 번에 뛰어야 하는 선수의 수 == flow

라고 생각하면 앵간 편하지 않을까 싶기도 한댱 ㅇㅅㅇ...

 

• 뭔가 일반화된 그래프의 시각으로 봤을 때 start 점이 source / finish 지점이 sink라고 생각하면 그래프를 이미지화 하기는 편할 것 같다.

 

---

 

 

# 본새나게 해결하고자 하는 문제 정의

vertex가 n개인 graph G가 주어지고,

G의 각 edge e는 non-negative integer(0이상의 정수)인 capacity c(e)를 가지고 있다고 한다.

G에서 source s 와 sink t가 주어졌을 때

s에서 t로 흘려보낼 수 있는 최대 flow는 얼마인가?

를 생각해보는것이다.

 

# 왜 알아봐야되는데?

 

예를 들어 철인 3종 경기를 하는데 다음 단계로 넘어갈 때 선착순으로 잘린다는 극악무도한 예시를 들어보자면

 

(달리기)                 (수영)                 (사이클)

   ㅡ                       

   ㅡ                       ㅡ

   ㅡ                       ㅡ                      ㅡ

   ㅡ                       ㅡ                      ㅡ

   ㅡ                       ㅡ                      ㅡ

   ㅡ                       ㅡ

   ㅡ

   ㅡ

 

이렇게 참여할 수 있는 선수의 레일 수가 줄어든다고 예시를 들었을 때 

달리기 -> 수영 :  유량/용량 = 8/8 -> 5/5 ( 선수 3명 낙오)

수영 ->  사이클 : 유량/용량 = 5/5 -> 3/3 (선수 2명 낙오)

도착한 선수는 3명 뿐이게 된다.

 

이처럼 유량의 정체 현상이 발생할 수 있기 때문에 최적을 적절한 최대 유량을 찾는 것이 중요하다고 생각한다.

 

 

다음 포스트에서는 Maximum flow problem을 해결하는 알고리즘에 대하여 알아보도록 하게...땨.

.... 미융

 

 

Hㅏ... 진짜 망할 알응...