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.

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

 

 

 

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.

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

 

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.

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

 

 

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包含奇数长度的循环(因此不是二部图))

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

 

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 (双分割:红色=奇数级别的节点,蓝色=偶数级别的节点)

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

 

 

 

 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

     

     

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

     

     

 

 

 

 

 

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

 

上一篇:Python高能小技巧:了解bytes与str的区别


下一篇:17.vue自定义主题颜色皮肤