如何按顏色劃分二部圖？

Question

例如，假設我有一個圖形G =（V，E），其中

V = {A，B，C，d}
E = {（A，B），（A，d）， （C，D）}

這個圖是二部分的，因此可以分解爲兩個不相交的集{A，C}和{B，D}。我的第一個猜測是我可以簡單地走圖併爲每個頂點分配交替的顏色。這是這種情況，還是比這更復雜/更簡單？有沒有已知的算法？

Answer 1

您的第一個猜測是正確的 - 遍歷圖形和備用。

算法應該很簡單。我會保留兩個節點的隊列來訪問，每種顏色一個。 Pop節點交替離開隊列，標記其顏色，並將任何未訪問的相鄰節點推入相反顏色的隊列。當訪問節點的數量+兩個隊列的長度=圖中節點的數量時終止。

Answer 2

如果您確信該圖是biparte，那麼你可以指定顏色交替它們用於遍歷每個頂點，因爲它認爲：

一個圖是二部圖當且僅當它是2-着色。

Answer 3

維基百科（http://en.wikipedia.org/wiki/Bipartite_graph）

如果二分圖連接，其bipartition可以通過從任何任意選擇的頂點v的距離的奇偶性來限定：一個子集由頂點的在連到距離v並且另一個子集由距離v的奇數距離的頂點組成

因此，可以通過使用該奇偶校驗技術將頂點分別分配給每個連接的兩個子集U和V來有效地測試圖是否是二分的組件，然後檢查每個邊以驗證它是否分配了端點t o不同的子集。

Answer 4

遍歷圖和交替，如果它沒有成功，這意味着你的圖不是雙方的。

Answer 5

以防萬一任何人的好奇，這裏是我想出了代碼：

def dfs(root, colorings): 
    to_visit1 = deque() 
    to_visit2 = deque() 
    to_visit1.append(root) 
    while len(to_visit1) != 0 or len(to_visit2) != 0: 
     dfs_color(to_visit1, to_visit2, True, colorings) 
     dfs_color(to_visit2, to_visit1, False, colorings) 

def dfs_color(queue, opposite_queue, color, colorings): 
    while len(queue) != 0: 
    v = queue.pop() 
    if v in adjacency_list: 
     colorings[v] = color 
     neighbors = adjacency_list[v] 
     del adjacency_list[v] 
     for neighbor in neighbors: 
     opposite_queue.append(neighbor) 

誠然，這不是我最好的代碼。我使用True/False作爲顏色，因爲當我使用遞歸時，可以很簡單地說not color。當然，我必須改變它，因爲我在更大的圖表上吹掉了我的堆棧。此外，爲了在適當的地方給予學分，此代碼基於DFS的維基百科代碼。

雖然已經指出，我認爲這可能只是一個變相的BFS。

Answer 6

我在我的graph drawing tool中實現了它，你可以在JavaScript中看到我的代碼。

我只是將第一個頂點標記爲左邊的partity，然後遞歸地將它的鄰居標記爲右邊的partity，遞歸地將它們的鄰居標記爲左邊的partity ...如果找到正確標記的節點，則停止遞歸該分支。如果發現標記不正確的節點，則圖形不是二部分。

也許是可以做到的簡單，但在過去的幾個月裏我有一些硬的Prolog - 哈斯克爾編碼天，也許這影響了我的大腦，現在我看到遞歸的一切:-D