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
