최적의 최대 유량 감소

매개 변수 k이 주어지면 최대 흐름이 가능한 한 많이 감소되도록 방향성 그래프에서 k 에지를 삭제하려고합니다. 그래프의 소스는 이고 싱크는 t이며 각 에지의 용량은 1입니다. 그래프는 사이클을 포함 할 수도 있고 포함하지 않을 수도 있습니다.최적의 최대 유량 감소

제안 된 솔루션은 순환을 "용서하는"알고리즘을 사용하여 그래프에서 토폴로지 정렬을 수행하는 것입니다. 아마도 우리를 소스로 되돌려주는 가장자리를 무시할 것입니다.

i = 0 
for each vertex u order by topological(u) 
    for each edge (u, v) order by topological(v) descending 
     if topological(v) > topological(u) then 
      delete (u, v) 
      if ++i = k then return 
     else 
      // edge doesn't contribute to max flow, ignore

겠습니까이 일을, 아니면 완전히 오프 트랙 여기입니다 : 다음 (K> = 1 가정)?

출처

2010-04-11 ArIck

"최소 컷을 찾는 것"은 Ford-Fulkerson 알고리즘과 같은 "최대 흐름"을 찾을 수있는 알고리즘으로 얻을 수 있습니다. 하지만 정확히 당신이하려는 것은 무엇입니까? 최대 유량을 줄이면 무슨 뜻입니까? –

@Christian : 아이디어는 우리가 이미 Ford-Fulkerson과 같은 알고리즘을 사용하여 최대 유량을 찾았다는 것이지만, 이제 k 가장자리를 전략적으로 삭제하여 최대한 줄일 수 있기를 바랍니다. – ArIck

글쎄, 작년 컴퓨터 과학 과목에서이 정확한 질문에 답하는 것을 기억합니다. 단지 내가 하하에게 대답 한 것을 기억하지 못합니다. P IIRC 최대 흐름 알고리즘은 그래프를 2 세트 A, B로 분할하여 가장자리를 따르는 흐름 A에서 B까지는 용량에 있으며, 이는 그 흐름이 흐름의 "초크 포인트"(군사 용어로)임을 의미합니다. 그 가장자리를 자르면 가장 확실하게 총 유량을 가장 많이 줄입니다. – ldog

나는 완전히 오프 트랙이라고 생각합니다. 알고리즘은 흐름을 전혀 줄이지 않을 수도 있지만 최대 흐름을 적어도 k만큼 줄이거 나 (또는 0으로 만들 수 있습니다.)

max-flow min-cut theorem을 알고 있습니까?

출처

2010-04-11 18:07:05

나는 "st flow의 최대 값은 어떤 flow도 s에서 t로 갈 수 없도록 제거 되어야만하는 최소 용량과 동일하다"는 것을 암시했다는 점에서 나는 알고있다. 이 상황에서 나를 도우십시오. 그래프에서 s-t 컷을 찾고 컷을 교차하는 가장자리를 제거하고 싶습니까? – ArIck

@Arlck : 직접 질문에 대답 해 보시기 바랍니다. –

최적의 최대 유량 감소

답변

관련 문제