隨機圖分區

Question

我試圖測試圖分區的一些模型（這些來自現實世界中，圖緩慢自動分區）。要做到這一點，我需要能夠將這個圖形統一隨機分割成連續的分量（我們給出的圖形最初也是連接的）。如果不需要連續性標準，我相信這將是隨機劃分一組可以進行組合分析的問題。有誰知道有任何方法將圖隨機分成子圖（即隨機抽樣一個分區），或者，如果沒有這種方法是已知的，要隨機抽樣一組元素？隨機化分區數量然後隨機化成員資格的方法將不起作用，因爲每個分區大小的可能分區數量不同。

Answer 1

您必須區分edge-cut partitioning和vertex-cut partitioning，其中沿着邊或頂點劃分圖。這會顯着影響您的問題，因爲不同頂點切割的數量遠大於邊緣切割的數量。原因在於，您只將頂點分配給頂點切割中的分區 - 與將頂點分配給分區的邊緣切割相反 - 並且邊數多於頂點（例如n個頂點的O（n^2）邊）。因此，組合較大的頂點切割導致需要檢查連通性的更多數量的子圖。一種天真的隨機化方法是枚舉所有分區，迭代選擇一個分區，並檢查選定分區中所有子圖的連通性。那你就拿第一個。在這種情況下，所有的解都有相同的概率（均勻隨機）。