목록2023/05/22 (1)

HJW's IT Blog

Algorithm: Network Flow

#개요 > Network Flow란 노드들과 그들 사이의 에지로 이루어진 흐름을 나타내는 개념 > 노드들이 출발지와 목적지로 구성되며, 에지들은 용량(capacity)를 가진다 > 목표: 출발지에서 목적지로 가는 흐름의 양을 최대화/최소화 하는것 > Flow Network란? >> 네트워크 플로우 문제를 모델링하기위한 그래프이다. >> 각 에지에 허용가능한 최대 흐름이 지정되어 있다 >> 시작점과 목적지가 지정되어 있어야 한다 >> 출발지에서 목적지로 흐르는 실제 흐름량이 나와있다 #입력 > 가중그래프 > 에지의 가중치: c(e) > 시작점 s: 들어오는 에지 x > 도착점 t: 나가는 에지 x #Flow 란? > 그래프 G,s,t 가 주어졌을 때, flow f는 각 에지 e에 정수값 f(e)를 다음 조..
알고리즘 2023. 5. 22. 17:48
이전 Prev 1 Next 다음