每個n個頂點組中的圖分區

是否有任何圖分區方法可以按最大n個頂點的組進行分區。每個n個頂點組中的圖分區

例如：我有一個包含1000個頂點的圖，我想用最多100個頂點的子圖劃分它。如果算法發現效果更好，可以有2個子圖，每個子圖有50個頂點。

我發現了一種方法，使用k-means和k-means來「校準」簇以便在每個簇中有100個頂點，但我認爲這種方法非常耗時。

任何想法？

編輯：好吧，也許這是錯誤的要求子圖。試想一下，kmeans是如何工作的，我想在小組中分割我的圖，然後在每個組中解決TSP問題，然後將每個組與最近的組關聯起來，併爲組的中心應用3opt動作。但要做到這一點，我需要一個分區方法來找到最大n個頂點的組;算法可以找到具有n個頂點的k個組，並且如果有一些頂點可用，它將使剩下的組成爲另一個組。頂點必須彼此靠近而不是隨機選擇。

來源

2016-08-02 vladg

子圖與路徑有什麼區別嗎？ –

*「如果算法發現效果更好，可以有2個子圖，每個子圖有50個頂點。」* - 算法有什麼更好/更糟？你的約束/目標是什麼？不可能像現在這樣回答你的問題，沒有關於問題的信息 - 我是否有權制作帶有一個頂點的子圖？如果是這樣，爲什麼不是一個「好的解決方案」？子圖必須是凸的嗎？如果沒有，爲什麼不簡單地創建每個100個頂點的10個隨機子圖？請更新您的問題以獲得**明確定義的問題**。 – Holt

您需要爲此進行研究。我記得一個名爲Kernighan-Lin的啓發式算法，可以滿足您的需求。不幸的是，你需要概括它，時間真的很糟糕。我相信它在O（N^3）左右。

另一個更專業但複雜的方法是使用光譜分區。有關此主題的非常詳細的文章，您可以在Direct Science網站上使用。以下是此主題的鏈接：Spectral partitioning works: Planar graphs and finite element meshes。

我希望這會幫助你在你的追求。但我警告你，這不是一件簡單的事情。祝你好運！

來源

2016-08-02 08:48:24 student

我看到了這些方法，但我會嘗試修改某種單鏈接聚類方法來實現我的目標。 – vladg

每個n個頂點組中的圖分區

回答

相關問題