나는 평면 그래프에서 최소 절단을 찾기 위해 골을 알고있다.평면 그래프에서 최대 유량을 찾는 방법은 무엇입니까?
작동은
O (NlogN)로서 각 정점은 원래의 그래프에 대응하는면과 엣지는 두면을 연결하는 최소한의 가장자리에 대응하는 이중 그래프를 생성한다.
그런 다음 Dijkstra를 사용하여이 그래프에서 최소 경로를 찾습니다.
이렇게하면 최소 절단을 찾아 유량 값을 계산할 수 있습니다.
하지만이 흐름 값을 제공하는 원래 그래프 가장자리 세트를 어떻게 찾을 수 있습니까?
설명하는 알고리즘은 무향 그래프 (Reif 's 알고리즘)에서만 작동합니다. Hassin과 Johnson은 최대 흐름을 계산하기 위해 그것을 배제하는 방법을 보여주었습니다. 최근에 이러한 알고리즘이 O (n loglog n) 시간에 구현 될 수 있음이 나타났습니다. 방향없는 평면 그래프의 Min Cut 및 Max Flow에 대한 G.F. Italiano, Y. Nussbaum, P. Sankowski 및 C. Wulff-Nilsen 알고리즘 개선 참조. Proc. 컴퓨팅 (STOC), 산호세의 이론에 43 ACM 심포지엄, 감독 평면에서 2011 년
가장 빠른 알려진 알고리즘 (N 로그 n) http://web.engr.oregonstate.edu/~glencora/papers/other/Borradaile08-thesis-dissertation.pdf 또는 http://compgeom.cs.uiuc.edu/~jeffe/pubs/parshort.html
이 그냥가요 참조 O에서 실행 그래프 경로의 가장자리? 경로를 찾으면 모서리가 생깁니다. 맞습니까? 그게 당신이 요구하는 것입니까? –
Emm, no. 공액 그래프에서 경로를 찾습니다. 그것은 컷을 형성하는 모서리 집합입니다. 이러한 각 모서리가 파괴되면 원래 그래프는 두 개의 연결되지 않은 그래프가됩니다. – user10732