AI를 위한 필수 수학

428

AI

를 위한 필수 수학

용되는 최대 차량 수, 경로에 운송되는 최대 상품 수, 파이프라인이 처리할 수 있는 석유 또는

물과 같은 천연 자원의 최대 양 )이 있으며 출발지에서 목적지까지 그 흐름을 최대화하는 엣지

집합을 찾고자 한다. 모든 엣지는 출발지에서 목적지를 향하고 있다는 점에 유의해야 한다.

그래프 이론에서 매우 중요한 최대-유량 최소-차단 정리

max

-

flow

min

-

cut

theorem

는 출발지와 도착

지를 연결하는 엣지 집합의 최적성 (최대 흐름 )을 결정하는 데 중요한 역할을 한다.

최대 흐름 최소 차단

max

-

flow

min

-

cut

정리는 방향성 네트워크에서 출발지로부터 도착지로의 최대

유량이 출발지와 도착지 간의 모든 통신을 차단하는 데 필요한 엣지들의 최소 가중치 합과 같

다는 의미다. 즉, 네트워크를 차단하여 출발지와 목적지 간의 통신을 한 가지 이상의 방법으로

차단할 수 있다. 그 통신을 차단하고 가중치가 가장 작은 엣지 집합을 최소 차단 집합

minimal

cut

set

이라고 한다. 이 최소 차단 집합의 값은 네트워크에서 가능한 최대 유량(흐름 )의 값과 같다.

이 결과는 매우 직관적이다. 네트워크의 엣지를 통해 전송할 수 있는 최댓값은 얼마인가? 이는

출발지와 목적지를 연결하는 데 중요한 엣지의 용량에 의해 그 상한이 결정된다.

최대 유량 문제를 선형 최적화 문제로 재정의할 수 있으며 물론 최소 차단 문제는 최대 유량 문

제의 쌍대 문제가 될 것이므로 두 문제는 같은 해결책을 가질 것이다! 이에 관해서는 ...