圖中的切割集

我對網絡中的最大流量有疑問。我試圖在可以斷開源和目標的圖形中找到剪切集。我探索了圖形中從源到目的地的所有邊緣獨立路徑。接下來，我從這些路徑中選擇了一條邊，並將它們分組在一起。所以基本上我列舉了從每條路徑取一條邊的所有可能的組合。所以我有一組這樣的組。這是否意味着我最終找到了特定源和目的地的網絡剪輯集？這是一種有效的方法嗎？圖中的切割集

來源

2012-11-28 dashingncool

這聽起來像是指數複雜。我不能確切地說，因爲我不知道「所有邊緣獨立路徑」的含義。例如：

A 
    | 
    B 
/\ 
C D 
    \/
    E

從A到E有兩條路徑，但它們不是邊緣獨立的。

上的曲線A的最大流量是雙重的minimum cut，並有大量的標準算法，可以找到一個在（小）多項式時間。如果您滿意的剪裁可言，只是刪除所有的邊緣 - 這在運行時間爲O（E）。

你有什麼限制？

來源

2012-11-28 02:06:04

是啊！你對指數複雜性是正確的。所以，我讀了一些其他職位，如果我用的是福特Fulkerson算法，我能找到的最低削減。這怎麼可能？ – dashingncool

另外，我忘了提，我需要找到網絡中的所有可能的最小割。 – dashingncool

圖中的切割集

回答

相關問題