네트워크 흐름

컴퓨터 공학의 많은 문제는 노드와 노드 간 링크로 구성된 그래프로 나타낼 수 있습니다. 예를 들어, 철도 시스템과 같이 네트워크를 통해 상품이나 자재를 운송하는 것과 관련된 네트워크 흐름 문제가 있습니다.

노드가 도시이고 그 사이의 호가 선로인 그래프로 네트워크 흐름을 나타낼 수 있습니다. 이러한 속성을 파이프라고 하는데, 이는 파이프 네트워크를 통해 흐르는 물과 속성이 유사하기 때문입니다.

네트워크 흐름의 주요 제약조건은 각 원에 용량(고정 기간 동안 호를 통해 전송할 수 있는 최대 금액)이 있다는 점입니다.

최대 흐름 문제는 용량 제약에 따라 네트워크의 모든 원호에 걸쳐 전송 가능한 최대 총량을 결정하는 것입니다.

이 문제를 연구한 첫 번째 사람은 1930년대 러시아의 수학자 A.N. 톨스토이였습니다. 아래 지도는 최대 통행량을 찾고자 했던 실제 철도망을 보여줍니다.

철도망 지도

OR-도구는 그래프 라이브러리의 네트워크 흐름 문제를 위한 여러 솔버를 제공합니다.

다음 섹션에서는 네트워크 흐름 문제의 예와 해결 방법을 보여줍니다.