圖形理論：分割圖形

我有這個問題。我有一個包含n個節點的圖，我想將其分解爲x個節點和n-x個節點的兩個子圖，但需要約束剩餘邊數最大化（或最小化切割邊的數量）。圖形理論：分割圖形

不知道這是否合理。不是一個圖論的人，但這是我的問題的抽象版本。我應該看看哪些算法可以幫助我？

這不是一個家庭作業問題。雖然我覺得有趣的問題！

我打算在C中實現。

來源

2012-04-17 JoshDG

x是一個參數還是隻是尋找2個子圖？如果x不是一個參數，是不是隻需要尋找具有最少邊數的節點並將其從圖中刪除？ – brianestey 2012-04-17 05:53:14

是的..抱歉，我應該讓這個更清楚。假設x是10，總節點是25.我需要兩個圖，一個有10個節點，另一個有15個，通過「切割」最少數量的邊。 – JoshDG 2012-04-17 05:54:56

絕對是一個有趣的問題。實際上，我關於尋找單個節點的第一個假設是錯誤的 - 我想出了一個不正確的圖。祝你找到解決方案！ – brianestey 2012-04-17 06:06:51

其中x = n-x稱爲最小二等分問題並且是NP難度的特殊情況。這也使得你的問題非常困難。在維基百科文章graph partitioning中描述了幾種啓發式算法，包括局部搜索（例如，開始於隨機剪切並反覆交換減少剪切大小的頂點對）和頻譜方法（例如計算和閾值第二特徵向量）。如果n很小，整數編程也是一種可能。

來源

2012-04-17 12:42:38 uty

這就是答案。 – 2012-04-17 12:49:09

哎呀。對於非計算機科學家來說，可能太高級了。如果x很小，使用遺傳算法可能會更好嗎？只需取一堆x = 10的隨機集合，對於圖分成兩部分的情況，就最小切割而言，取前10％，然後將這些變爲一代？你認爲這可能有效嗎？或者，它完全取決於數據集。我想我也可以嘗試一下。 – JoshDG 2012-04-17 15:29:29

本地搜索很容易實現：只需從剪輯開始，並嘗試通過稍作更改來改進。計算特徵向量並不算太壞，但確實需要一些數學知識。整數編程很難，但有免費的庫。我不喜歡組合問題的遺傳算法，但是如果你願意投入足夠的週期，它們可能比本地搜索更好。 – uty 2012-04-17 16:14:31

也許深度首先搜索節點。我們一次分配一個節點，並統計到目前爲止的切割次數。如果這個數字超過了最佳解決方案的數量，那麼我們放棄這一個並且回溯。

給予了充分的節點集合S的，讓P和P」是節點的setsuts，最初是空的，和K的切割邊緣的數量，初步0
令S *，K *是最知名的解決方案和它的切邊數量，K *最初是無限的。
選擇一個節點N開始與和其分配給S.
對於每個未指定的節點M：
1. 分配M至S」，並從M個S中添加的邊緣的數目，以節點K.
2. 如果K> K *，那麼沒有基於此的解決方案將擊敗最好的，因此將M分配給S.
3. 如果| S | > X，那麼這個集合變得太大了;原路返回。
4. 否則，從4
遞歸如果所有節點分配和K < K *，然後讓S * = S和K * = K.

我一直在想象這個作爲Prolog類型的算法，但在C中執行它不應該太難。回溯只意味着取消分配最後分配的節點。

來源

2012-04-17 06:08:15 Edmund

基本上，您正在查看min-cut問題的修改版本。

一種方法是修改karger's algorythm 在Karger的算法中，您沿着隨機邊收縮頂點，直到最終只有兩個頂點，其餘邊表示切割。既然它是隨機的，你只需要做很多次這樣的操作，並且在切割中保留最少邊的解決方案。

在修改後的版本中，一旦頂點摺疊了x次，您可以停止摺疊並計算出口邊緣（這將成爲您的案例中的切入點），執行適當的時間，並且您有一個解決方案。棘手的部分是計算出多少次重複計算以將置信度提高到令人滿意的極限

來源

2012-04-17 06:56:57 AntonioD

最小切割問題沒有固定'x' [切割邊的一個頂點的數量]，並且具有特定的'source'和'sink'。如果你想減少問題，請將其添加到答案中。 – amit 2012-04-17 07:02:16

我認爲對Karger's的某種修改可以解決這個問題。最小切割問題本身沒有水槽和源，只是有些algorythms將問題減少到最大流量問題。我會編輯答案，如果我能想出一個很好的修改卡爾的處理固定的x案件（有一個明顯的方法，但不知道它給出正確的結果） – AntonioD 2012-04-17 07:29:06

圖形理論：分割圖形

回答

相關問題