ALG 3-4: Testing Bipartiteness - An Application of BFS

Bipartite Graphs

Def. An undirected graph G = (V, E) is bipartiteif the nodes can be colored red or blue such that every edge has one red and one blue end.

(定义: 无向图G = (V, E)是双偏图，如果节点可以用红色或蓝色表示，使得每条边都有一个红色和一个蓝色端)

Applications.

• Stable marriage: men = red, women = blue.
• Scheduling: machines = red, jobs = blue.

Testing Bipartiteness

Testing bipartiteness. Given a graph G, is it bipartite? (给定一个图G，它是二部图吗?)

• Many graph problems become:
• easier if the underlying graph is bipartite (matching)
• tractable if the underlying graph is bipartite (independent set)
• Before attempting to design an algorithm, we need to understand structure of bipartite graphs.

An Obstruction to Bipartiteness

Lemma. If a graph G is bipartite, it cannot contain an odd length cycle.

(引理: 如果图G是二部图，它不可能包含奇长度环)

Proof. Not possible to 2-color the odd cycle, let alone G.

Bipartite Graphs

Lemma. Let G be a connected graph, and let L0, …, Lk be the layers produced by BFS starting at node s. Exactly one of the following holds.

(引理：设G为连通图，L0，…，Lk为从节点s开始的BFS生成的层. 则至少有下面的一个是正确的)

(i) No edge of G joins two nodes of the same layer, and G is bipartite. (G的边从不连接同一层的两个节点，且G是二部图)

(ii) An edge of G joins two nodes of the same layer, and G contains anodd-length cycle (and hence is not bipartite).

     （G其中的一条边连接了同一层的两个节点，并且G包含奇数长度的循环(因此不是二部图)）

Proof. (i)

• Suppose no edge joins two nodes in adjacent layers. （假设没有边连接相邻层中的两个节点）
• By previous lemma, this implies all edges join nodes on same level. （根据前面的引理，这意味着所有边都在同一层上连接节点）

• Bipartition: red = nodes on odd levels, blue = nodes on even levels （双分割:红色=奇数级别的节点，蓝色=偶数级别的节点）

 Proof. (ii)

• Suppose (x, y) is an edge with x, y in same level Lj.  // 假设(x, y)是一条边，x, y在Lj层中
• Let z = lca(x, y) = lowest common ancestor.　           // 令z = lca(x, y) =最近一层的共同祖先　　　
• Let Li be level containing z.                                         // 设Li是包含z的层 
• Consider cycle that takes edge from x to y,then path from y to z, then path from z to x.  // 考虑一个循环，边从x到y，然后路径从y到z，然后路径从z到x
• 

   

   

• 

   

   

ALG 3-4: Testing Bipartiteness - An Application of BFS

原文：https://www.cnblogs.com/JasperZhao/p/13975618.html