查找圖中所有切割的算法

Question

我正在尋找一種有效的算法，可以幫助我列出圖中的所有切割。該圖是一個流網絡（有向圖），並具有固定的源和接收器。我想知道哪些是所有可能的剪輯集合，一邊是源文件，另一邊是匯點。

請注意，重點是找到所有剪切集合，而不是最小剪輯。

例如， 考慮與以下邊列表的圖表： 秒 - >一 - >噸 秒 - >乙 - >噸

的割集的上圖是： {sa，sb}，{at，bt}，{sa，sb，at}，{sa，sb，bt}，{sa，sb，at，bt}

Answer 1

因爲您有指數量的削減。 你的源代碼是S，T中的接收器，其中S-T是剪切的。 現在考慮一下： 對於每個頂點，它可以在S或T中。 將所有頂點想象成一個長二進制數，其中1表示頂點i在S中，0表示它在T中。

你有多少種選擇？如果你有n個頂點，你可以有多少個不同的二進制數？答案是2^n，但我們可以忽略sink和soruce，但它並不是母親，我們仍然有O（2^n）用於不同的切割。