graph-coloring

-1熱度

1回答

我開始知道圖着色算法是NP-Complete問題。不過，我想知道是否可以使用啓發式方法實現任何實現，特別是區別圖着色？如果可能的話，是否有任何合適的資源來了解這一點？

0熱度

1回答

我正在開發一種算法，用於查找圖的色數並使用該數提供有效的着色。爲此，我使用二分查找找到可能的答案K，並使用遺傳算法檢查K是否可行。問題是色數分佈不均勻。例如，對於具有1000個頂點的圖，其色數最可能低於100.這種方式在我的二進制搜索中，我不需要在左邊界和右邊界之間的中間進行分割，而是找到半色的中間號碼分配。你知道我可以從哪裏獲得關於這個發行版的信息嗎？我發現一個源給我一些細節，但對於節點少於10

1熱度

2回答

Python「如果超過最大步數，打破循環」

我正在研究一個（非常複雜和不雅）Python代碼，通過蠻力3色圖形，並且在我的主代碼塊I' m試圖包含一個聲明，說「如果通過循環的最大運行次數超過（某些任意數量），跳出第一個（while a in range(0,len(vertices))）循環」。 a = 0 steps = 0 while a in range(0,len(vertices)): for j in newdic

0熱度

1回答

超圖的頂點着色，不均勻性限制NP-hard？

是一個超圖的頂點着色，沒有統一性限制NP-hard？我看過顯示k-聯合超圖的頂點着色的論文是NP-hard。然而，我找不到任何明確說明在一般情況下（而不僅僅是k均勻）超圖的頂點着色是否是NP難的來源。

0熱度

1回答

爲圖表着色，以便每個節點都是彩色的或與彩色節點相鄰

假設您有一個連通無向圖G.您希望G中的每個節點都是彩色的或與彩色節點相鄰。設計一個算法來適當地爲圖G着色。您只能對樓層（n/2）節點着色，其中n是節點的總數。我嘗試了一個解決方案，但是我發現它沒有完全解決約束問題，我想要一個微調或被告知我在錯誤的軌道上。我的解決方案基本上是運行BFS，並在每個「三級」着色節點。但是我發現了一個失敗的實例 - 只有三個節點的鏈表。如果我爲頭部或尾部着色，那麼其中

0熱度

1回答

python中地圖着色的隨機實例

我需要在python中生成隨機地圖着色問題實例來實現最小衝突求解器。我應該遵循這個策略：在單位正方形上分散n個點;隨機選擇一個點X，通過一條線段將X連接到最近的點Y，使得X尚未連接到Y，並且該線段不與其它線段交叉（例如，請參閱此處如何測試線段交叉點）。重複上一步直到不再有可能的連接。這些點表示地圖上的區域，並且這些線路將鄰居連接起來。我甚至不知道如何開始。

1熱度

1回答

使圖着色不太嚴格

我正在試驗graph coloring算法。這是一種對圖的節點進行着色的方式，使得沒有2個相鄰節點具有相同的顏色。假設我有以下數據我想「色」（分配到組），其中每個字都是一個節點：貓黑色貓灰色狗灰色狗黑我希望以下組：貓，狗黑色，灰色但如果我加入我的第四動物，這是grey（就像顏色）的名字？所以第四行變成：狗黑灰色着色算法不能顏色和名稱進行區分，所以black和grey將在最終

-1熱度

1回答

排列不同組的陣列，以便它的元素沒有鄰居相似的組

我有可以通過它的一個被分成3個不同的組的陣列的屬性： $shuffleMeGood = array( 0 => array('id' => '1', 'group' => 'banana'), 1 => array('id' => '2', 'group' => 'banana'), 2 => array('id' => '3', 'group' => 'banana'

0熱度

2回答

如何檢查圖形是否可着色？

我想查找圖形是否可以2色或不更多。雙方或非雙方。這裏是我在C++中的代碼我正在使用威爾士鮑威爾算法，但代碼中有些錯誤可能是我錯過了一些角落案例或一些邏輯錯誤。輸入n =沒有。頂點，m =否。基於0的索引 #include <iostream> #include <algorithm> using namespace std; pair <int,int> s[1001]; int

6熱度

1回答

如何計算繪製樹的方法？

如何計算使用m種顏色繪製樹節點的方式，以便每個邊的末端具有不同的顏色？歡迎任何多項式解決方案。