최대 흐름 그래프 알고리즘

Question

방향성이없는 그래프에서 최대 흐름을 찾기 위해 어떤 알고리즘을 사용해야하는지 알고 있습니까? 지금까지 내가 이해, 미연 신 네트워크는 여기에 기본적으로 예를 들어, 두 개의 "일반" 갈비와 두 "가짜" 리브에 의해 연결된 정점으로 다중 그래프로 그래프를 회전

가에 사용

Ford-Fulkerson 알고리즘.

그러나 멀티 그래픽의 경우 어떻게 처리해야합니까?

Answer 1

당신이 가장자리 미 배향의 경우

 5 
* ------ * 

는 두 개의 중심의 가장자리으로 바꿀 수 있습니다

 5 
    ------> 
*   * 
    <------ 
    5 

포드-Fulkerson에 방법은 완벽하게 같은 그래프에서 작동합니다.