최대 흐름 알고리즘을 사용하여 그래프에서 최소 절단을 어떻게 찾을 수 있습니까?
그래프에서 최소 컷을 찾아야합니다. 흐름 네트워크에 대해 읽었지만 찾을 수있는 것은 Ford-Fulkerson, push-relabel 등과 같은 최대 흐름 알고리즘뿐입니다. 최대 흐름 최소 절단 정리를 고려할 때 이러한 알고리즘 중 하나를 사용하여 찾을 수 있습니까? 최대 흐름 알고리즘을 사용하는 그래프의 최소 컷? 어떻게?
지금까지 내가 찾은 최고의 정보는 "포화"가장자리, 즉 흐름이 용량과 같은 가장자리를 찾으면 해당 가장자리가 최소 절단에 해당한다는 것입니다. 사실인가요? 나에게 100 % 옳지 않은 것 같습니다. 최소 절단의 모든 모서리가 포화되는 것은 사실이지만 최소 절단 "경로"를 벗어난 포화 모서리도있을 수 있다고 생각합니다.
소스 정점에서 잔여 네트워크의 가장자리를 따라 깊이 우선 검색을 수행하고 (즉, 흐름이있는 가장자리의 포화되지 않은 가장자리와 뒤쪽 가장자리) 이러한 방식으로 도달 할 수있는 모든 정점을 표시합니다. 컷은 표시된 정점에서 표시되지 않은 정점으로 이어지는 모든 모서리로 구성됩니다. 분명히 이러한 가장자리는 포화 상태이므로 횡단되지 않았습니다. 언급했듯이 최소 절단의 일부가 아닌 다른 포화 된 모서리가있을 수 있습니다.
까다 롭고 싶지는 않지만 제안 된 솔루션이 제안 된대로 옳지 않습니다.
올바른 해결책 : 실제로해야 할 일은 Residual-Network Gf ( wikipedia에서 읽어보십시오 )의 bfs / dfs 와 정점을 표시하는 것입니다. 그런 다음 from-vertex 및 표시되지 않은 to-vertex가 표시된 항목을 선택할 수 있습니다.
'포화되지 않은 가장자리를 따르는 것'이 충분하지 않은 이유 : 그림과 같이 흐름 알고리즘이 가장자리를 포화 시킨다는 것을 고려하십시오. 내가 방문한 정점을 "불포화 가장자리를 따라가는"접근 방식으로 녹색으로 표시했습니다. 분명히 유일한 올바른 min-cut은 EF의 가장자리이며 제안 된 솔루션은 AD (그리고 심지어 DE)도 반환합니다.
E에서 D까지의 에지가 있으므로 E에서 D까지의 에지가 있으므로 에지 EF가 마크 된 from-vertex 및 마크가없는 유일한 네트워크가되기 때문에 Residual 네트워크를 대신 고려하면 dfs / bfs가 정점 D를 방문 할 것입니다. to-vertex.
참고 : Falk의 알고리즘을 사용하여 최소 정점과 최대 정점이있는 최소 컷을 모두 찾을 수 있습니다. 후자의 경우 알고리즘은 역전되어야합니다. 소스 대신 싱크 정점에서 검색하십시오. 관련 질문보기 : 네트워크 흐름 : 새 에지 추가
이해하는 한 가지 방법은 각각 s와 t를 포함하는 두 세트 S와 T로 컷을 정의하는 것입니다.
이제 잔여 네트워크의 s에서 도달 할 수있는 S의 모든 정점을 추가하고 나머지 가장자리를 T에 넣습니다. 이것은 하나의 컷이됩니다.
둘째, 잔여 네트워크의 t에서 도달 할 수있는 모든 정점을 T에 놓고 나머지 정점을 S에 배치하여 절단을 형성 할 수 있습니다.
이 비디오를 통해 s와 t에서 도달 할 수있는 정점을 찾는 방법을 알아보십시오.
https://www.youtube.com/watch?v=FIJaXfUIXJA&index=4&list=PLe-ggMe31CTduQ68XQ-sVj32wYJIspTma
따라서 최소 컷을 얻는 방법에 대한 정확한 절차를 제공하려면 :
- Ford-Fulkerson 알고리즘을 실행하여 최대 유량을 찾고 잔차 그래프 1 을 얻습니다 .
- 잔차 그래프 에서 BFS 를 실행 하여 잔차 그래프의 소스에서 도달 할 수있는 정점 세트를 찾습니다 (잔차 그래프에서 용량이 0 인 에지를 사용할 수 없다는 점을 고려). 중요 : 잔차에 역방향 에지를 사용해야합니다. 도달 가능한 정점의 올바른 세트를 찾는 그래프 !!! (이 알고리즘 참조)
- 도달 할 수있는 정점에서 도달 할 수없는 정점까지 의 원본 그래프의 모든 가장자리 는 최소 절단 가장자리입니다. 이러한 모든 가장자리를 인쇄하십시오.
1 에지의 용량이 원래 용량에서 흐름을 뺀 것처럼 정의 된 그래프입니다 (최대 흐름 네트워크의 흐름).
최대 유량을 계산 한 결과 에지를 검색 할 수 (u,v)잔여 그래프로부터 잔류 그래프에서 에지 거기되도록 v행 u및 f(v,u) = c(u,v)[이는 에지가 포화 수단]
이러한 간선을 목록에 추가 한 후 (u,v)잔차 그래프에서 u에서 싱크 t까지의 경로가 없다는 기준을 사용하여 이러한 간선 을 선택할 수 있습니다 . 이 조건이 충족되면 이러한 모서리가 (S,T)절단 부분을 형성합니다.
이 알고리즘의 실행 시간은 O(E) * O( V + E ) = O( E^2 )
나는 이것이 다른 사람들이 말하는 것이라고 생각하지만 불분명하다는 것을 알았으므로 여기에 내 설명이 있습니다.
소스 노드에서 그래프의 플러드 채우기를 수행하고, 남은 용량이있는 에지를 따라 이동하여 방문한 각 정점을 표시합니다. 이를 위해 DFS를 사용할 수 있습니다. 정점의 뒤쪽 가장자리에는 앞쪽 가장자리를 따라 흐르는 흐름과 같은 잔여 용량이 있다는 것을 상기하십시오 (예 : r (u, v) = 가장자리에 대한 잔여 용량 (u, v), r (v, u) = flow (u , V)).
실제로 이것은 그래프의 ST 컷의 S 부분을 결정합니다.
최소 절단은 이제 한 정점이 위의 홍수 채우기에서 표시되고 다른 정점이 표시되지 않도록 가장자리 세트가됩니다. 이들은 잔여 용량이없는 모서리 (그렇지 않으면 DFS에서 횡단했을 것임)가되고 함께 최소 절단을 형성합니다.
이러한 가장자리를 제거한 후 표시되지 않은 정점 세트가 절단의 T 섹션을 형성합니다.
'programing' 카테고리의 다른 글
| ess-mode에서 emacs가 underbar를 <-로 바꾸는 것을 막는 방법 (0) | 2021.01.15 |
|---|---|
| LaTeX에서 "C ++"를 작성하는 방법 (0) | 2021.01.15 |
| setup.py가 달걀로 설치되지 않도록 중지 (0) | 2021.01.15 |
| Python 3 용 tkinter 및 ttk에 대한 새로운 튜토리얼 (0) | 2021.01.15 |
| Python argparse 및 bash 완성 (0) | 2021.01.15 |