如何查找圖形是否爲二部圖？

我一直在試圖理解二部圖。據我瞭解，它是一個圖G可以分爲兩個子圖U和V.So U和V的交集是一個空集和聯合是圖G.我試圖找出如果一個圖是二分或不使用BFS。仍然不清楚我們如何使用BFS找到這個問題。如何查找圖形是否爲二部圖？

讓我們說我們有圖定義如下。

a:e,f 
b:e 
c:e,f,h 
d:g,h 
e:a,b,c 
f:a,c,g 
g:f,d 
h:c,d

什麼，我這裏需要的是一步的這個圖是一個怎麼的雙方或不使用BFS一步的解釋。從GeeksforGeeks

兩者

來源

2015-05-27 user2738777

你是什麼意思的兩個子圖的交集？據我所知，二部圖是一個圖，其頂點可以分成兩組，所有邊都從一組開始，結束於另一組。 – biziclop

對於BFS，您可以從一個頂點開始，將其着色爲藍色，然後將其所有鄰居着色爲紅色，然後穿過鄰居的鄰居並將它們全部着色，等等。如果您遇到已着色的節點並且與您需要設置的節點不同，則該圖形不是雙向的。 – biziclop

@biziclop我的意思是一樣的。兩個子集是兩個子圖，交集是一個NULL集，它支持一個頂點不能同時在兩個集合中的雙重性。如果它是那麼它不是一個二部圖。 – user2738777

下面是一個簡單的算法來找出給定圖是否是Birpartite或不使用廣度優先搜索（BFS）： -

分配紅色的源頂點（放入U盤）。
用BLUE顏色對所有鄰居進行着色（置入集合V）。
使用RED顏色爲所有鄰居的鄰居着色（置入集合U）。
這樣，爲所有頂點分配顏色，使其滿足m路着色問題（其中m = 2）的所有約束條件。
分配顏色時，如果我們找到與當前頂點顏色相同的鄰居，那麼圖形不能用2個頂點着色（或者圖形不是Bipartite）。

甲二分圖是可能的，如果圖着色可能使用兩種顏色，使得在一組頂點與相同顏色着色。

此外，注： -

- >是可能的顏色的循環圖與即使使用兩種顏色週期。

- >使用兩種顏色不可能使用奇數週期對循環圖進行着色。

編輯： -

如果圖形沒有連接，它可以具有多於一個bipartition。您需要使用上述算法分別檢查所有這些組件。

因此，對於同一圖形的各種斷開子圖，您需要使用上面討論的相同算法單獨對它們進行這種雙分區檢查。所有這些各個斷開的子圖的圖將佔其自身的一組雙分區。

而且，該圖將被稱爲二分，IF和ONLY，如果其每個連通分量被證明是二分的。

來源

2015-05-27 15:48:17

如果圖表未連接，該怎麼辦？ –

@shekharsuman您的評論是錯誤的。一個沒有邊的圖形是真實的二部分，它的每條邊都是正弦曲線來回答連接到兩個部件的條件。 – amit

@EdwardDoolittle你只需要每個連接的組件都是二部的，然後它們的並集也是二部分的。， – amit

卡內基梅隆大學：

「回想一下，圖G =（V，E）被認爲是二分如果其頂點集V可以被劃分爲兩個不相交的集合V1，V2使得E.所有邊緣都在V1一個端點和V2一個端點

（來源：http://www.cs.cmu.edu/~15251/homework/hw5.pdf）。

你確定你需要使用BFS？確定圖形是否需要檢測週期長度，DFS可能比BFS更適合於週期檢測。

無論如何，一個圖，如果雙方當且僅當它沒有奇數長度的週期。如果允許使用DFS，則可以在圖上使用DFS，並檢查後端邊緣以檢測週期的存在，並使用DFS時間戳計算每個週期的大小。

來源

2015-05-29 06:08:27 Xceptional

這些只是關於二部圖的各種定義。我在問題中給出的以及你所回答的內容基本上是相同的。 – user2738777

公平點。但更重要的是，你是否真的需要在DFS上使用BFS？ – Xceptional

以下是BFS方法，用於檢查圖形是否爲二分圖。

c = 0
選擇一個節點x並設置x.class = c
讓ys是設置y.class = c
如果任何y在中ys通過BFS
- c = 1-c
- 爲y得到的節點具有鄰居z與z.class == c然後，直到沒有更多的節點發現
圖不是二分
重複圖形是二分

這假定該圖形是一個單連接部件 - - 如果不是，只需爲每個組件執行此過程。

來源

2015-05-29 11:19:08 mitchus

-1

做更簡單的方法。

運行強連通組件算法。

如果獲得的元圖的任何節點具有多於兩個頂點，那麼給定的圖不是二分的。

來源

2016-05-05 04:55:27

這是一個Prolog CLP（FD）解決方案。只需將圖中的每條邊作爲域0..1中的變量進行建模即可。然後將每個頂點作爲方程式進行建模：

X #\= Y.

然後發出標籤。如果標籤找到了解決方案，就完成了。它可能會找到多個解決方案。這裏是你的榜樣運行：

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23) 
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam 

:- use_module(library(clpfd)). 
problem(L) :- L=[A,B,C,D,E,F,G], 
    A #\= E, A #\= F, 
    B #\= E, 
    C#\= E, C#\= F, C#\= H, 
    D #\= G, D #\= H, 
    E #\= A, E #\= B, E #\= C, 
    F #\= A, F #\= C, F #\= G, 
    G #\= F, G #\= D, 
    H #\= C, H #\= D. 

?- problem(L), L ins 0..1, label(L). 
L = [0, 0, 0, 1, 1, 1, 0] ; 
L = [1, 1, 1, 0, 0, 0, 1].

作品也是在GNU序言，序言SICStus，Jekejeke Minlog等大多用任何的Prolog系統實現CLP（FD）。或者也可以使用CLP（B）或dif/2。

來源

2016-07-02 18:02:28

製作一個bfs樹。如果在樹的同一級別的頂點之間存在邊，那麼該圖不是二部分，否則它是二部分。

來源

2016-11-17 13:19:22

如何查找圖形是否爲二部圖？

回答

相關問題