拆分圖表分爲兩個部分，根據最小切割

Question

我實現最小切割圖聚類s和t的頂點之間，和我需要能夠分割一個 圖分成兩個部分根據至S和Ť st min-cut I建立在每個聚類步驟上，對於某些s和t頂點。基本上，我想有一個函數，它接受的曲線圖ģ，節點小號，節點噸和返回兩個不相交的集合的節點小號和Ť的。

據我所知，找到st min-cut的最簡單方法是通過利用min-cut〜max-flow對偶性，並使用推送式重標記算法來實現最大流量計算。但是push-relabel算法並沒有給我們提供關於什麼是S和T集合的信息。

那麼，什麼是正確的方式獲得S和T min-cut子集？有沒有辦法使用Push-relabel算法？在C++或Python中是否有這樣的實現？

Answer 1

您可以使用push-relabel算法計算的信息來確定最小切割。 如您所知，push-relabel算法爲每個頂點v分配值h（v）。 h（v）的可能值在區間[0，N]中，其中N是圖的頂點數。很容易證明，對於每個頂點v存在一些編號h'，使得對於每個頂點存在h（v）！= h'（參見Cormen's book，2nd Ed的練習26.4-3）。找到這樣H '，每個頂點v與H（v）的< H' 之後是在切口的一側，並且每個頂點Ü與H（U）> H」是在另一邊。