Chapter 3 -- Graph ( 3 )

發表於 更新於 分類於 ， 閱讀次數： Disqus：

Application of BFS -- Testing Bipartiteness

Definition

The nodes of graph can be partitioned into two sets \(X\) and \(Y\) and one every edge has one end in \(X\) and the other end in \(Y\).We call it bipartite graph ( bigraph ) . 一個 graph 的 nodes 可以分成兩個集合，且每一條 edge 兩端連接的端點均屬不同集合者稱之為 bipartite graph ( bigraph ) 。

從此定義我們可以推得兩個 bipartite graph 性質

  • \(X\cap Y=\phi\)
  • \(\forall x_1,x_2\in X\Longrightarrow x_1\ isn't\ the\ neighbor\ of\ x_2\Longrightarrow\not\exists\ edge\ between\ x_1\ and\ x_2\)

了解其定義後，我們要問的問題是，給定一個 graph，我們如何判定是否為 bipartite graph ? 直覺一點的方式就是直接將每一個 edge 的兩個端點塗上兩個不同的顏色，然後看看是否會有衝突的地方。

如果寫成 procedure 的話 (假設 \(G\) 是 connected graph以簡化運算)

1
2
3
4
1. 先任選一點 s∈V,並且將其著色成紅色
2. 對它的所有 neighbors 著色成藍色
3. 重複對 neighbors 塗 紅/藍 色直至所有點都被著色完成
4. 若為 bipartite graph 則所有 edges 的兩端都為不同顏色

這個 procedure 要 implement 其實就是用 BFS，只是在 BFS procedure 中每一個 layer 再多加一個著色的動作即可。

[ 補充 ]

實際上，有一個定理可以幫助我們更方便來做判定 :

\(Graph\ G\ is\ bipartite,\ if\ and\ only\ if\ it\ doesn't\ have\ any\ odd\ cycle.\) 如果 \(G\) 是一個 bipartite graph，則不存在奇數 circle。也就是說，\(G\) 裡面的每一個 circle，都是由偶數條 edges 所構成。

Claim : \(G\ is\ a\ connected\ graph\ and\ L_0,L_1,\cdots are\ the\ layers\ produced\ by\ BFS\ starting\ at\ node\ s\) 1. \(There\ is\ no\ edge\ of\ G\ joins\ two\ nodes\ of\ the\ same\ layer\ \Longleftrightarrow\ if\ G\ is\ bipartite.\) 2. \(There\ is\ an\ edge\ of\ G\ joins\ two\ nodes\ of\ the\ same\ layer\ \Longleftrightarrow\ G\ contains\ an\ odd-length\ cycle.\)

Proof :

(2.\(\Longrightarrow\)) 假設在第 \(L_j\) 層有一條 edge 相連兩個 nodes \(x,y\)，由於 BFS 均可以 tree 的型態表示，此兩點 \(x,y\) 與原點 \(s\) 之間必然各自存在一條 path，且這兩條 paths 會在某一層 \(L_i\) 中某一點 \(z\) 交會。

從上圖可以知道 \(x,y,z\) 三個 nodes 會形成一個 cycle，其 length\(=1+2\times (j-i)\) \(\therefore\ x,y,z\) 三個 nodes 會形成一個 odd cycle \(\Longrightarrow\) G is not a bipartite graph

(2.\(\Longleftarrow\)) Clearly by definition.

(1.) Clearly by 2.

Connectivity in directed graphs

Definition

  • Nodes \(u,v\) are mutually reachable if \(\exists\) a path from \(u\) to \(v\) and also \(\exists\) a path from \(v\) to \(u\) 若兩點間互相存在一條 path 可以從一點到另一點，則稱之為 mutmally reachable。
  • A directed graph is strongly connected if \(\forall\) pairs of nodes are mutually reachable. 一個有向圖若任兩點均為 mutually reachable，則稱其為 stronglly connected。
  • The strongly (connected) component \(S\) containing \(s\) in a directed graph is the maximal set if \(\forall v\in S\) s.t. \(v\) and \(s\) are mutually reachable. 所有和 \(s\) 為 mutually reachable 的 nodes 形成一個 strongly component。

Lemma

\(If\ u\ and\ v\ are\ mutually\ reachable,\ and\ v\ and\ w\ are\ mutually\ reachable,\ then\ u\ and\ w\ are\ mutually\ rea chable.\)

Testing strongly connectivity

如果給定一個 directed graph ，我們可以如何檢查它是否為 strongly connected ? 最直覺也是最笨的方式就是做兩次 BFS，第一次先檢查 \(s\) 可以到達的點有哪些，第二次再檢查這些點能不能回到 \(s\)。

然而這樣的複雜度太高，因此稍微調整一下。

1
2
3
4
5
6
7
8
TestStronglyConnectivity(G):

1. 選擇任一點作為起始點 s
2. R=BFS(s,G)  
#針對此起始點對 G 做BFS
3. R'=BFS(s,G') where G' = the graph that it's edges are reverse direction of all edges of G
#製造一個方向與 G 完全相反的有向圖 G'，並做一次 BFS
4. 若 R=V=R'，則 return true else false

這裡每一個步驟都是 linear time complexity，最後的總時間複雜度為 \(O(m+n)\)

關於 strongly (connected) component 有一些蠻有趣的性質

  • 任一個 directed graph 必可以拆出數個 strongly (connected) component。
  • 將 directed graph 的所有 strongly (connected) component 都各自視為一個點，那麼必會形成一個 directed acyclic graph。

Theorem

\(For\ any\ two\ nodes\ s\ and\ t\ in\ a\ directed\ graph,\ their\ strongly\ component\ are\ identical\ or\ disjoint.\) 在一個有向圖中任取兩個 nodes，這兩個 nodes 必在相同的 Strongly Component 不然就各在互斥的兩個 strongly component 中。

Proof :

( Case 1. ) \(s\) and \(t\) are mutually reachable.

Clearly be definition.

( Case 2. ) \(s\) and \(t\) are not mutually reachable.

Suppose to the contrary that \(\exists v\) s.t. \(s\) and \(v\) are mutually reachable and \(t\) and \(v\) are mutually reachable

\(\Longrightarrow\) \(s\) and \(t\) are mutually reachable. (\(\rightarrow\leftarrow\))