네트워크 흐름이 주어지면 주어진 가장자리 중 하나만 누워가는 것을 알게됩니다.

Question

네트워크 흐름 $ g= (v, e) $ 용량 기능 $ C $ 소스 $ S $ 및 홀 $ T $ , 그리고 2 개의 가장자리 $ e_1, e_2 $ .

가장자리 중 하나만 최소 컷에 속해 있도록 min-컷이 있는지 확인하십시오.

도움을 받기를 바랍니다.

Answer 1

먼저 네트워크의 최소 컷 값 $ C $ 을 계산합니다.

두 번째, $ e_1 $ 을 제거하고 $ e_2 $ 의 용량을 무한대로 늘리십시오.새로운 네트워크의 최소 컷 값 $ C_1 $ 을 계산합니다.

셋째, 가장자리 $ e_2 $ 을 제거하고 $ e_1 $ 의 용량을 무한대로 늘리십시오.새로운 네트워크의 최소 컷 값 $ C_2 $ 을 계산합니다.

이제 $ C-C-C_1 \ GE C (E_1) $ 또는 $ C-C_2 \ GE 여부를 확인할 수 있습니다. $ e_1, e_2 $ 중 하나가 정확히 포함 된 초기 네트워크에서 최소 컷이 있는지 확인하려면 c (e_2) $