ch3 图算法¶
说明：与《数据结构》中重叠的部分并未做笔记。
1. 二分图¶
【二分图】一个无向图 \(G=(V,E)\) 被称为二分图（二部图），如果其顶点可以被赋予红蓝两色，使得每条边都有一个红色端点和一个蓝色端点。
- 应用：稳定婚姻问题，机器工序分配问题。
【引理】如果一个图是二分图，那么该图不包含奇数个顶点的环。
【引理】设 \(G\) 为一个连通图，并且令 \(L_0, ..., L_k\) 为由 \(\tt BFS\) 以 \(s\) 为起点产生的层，则以下二者中恰好有一个一定成立：
- \(G\) 中没有边连接同一层的两个顶点，此时可以把奇数层的点染成红色，偶数层的点染成蓝色，则 \(G\) 是一个二分图。
- \(G\) 中有一条边连接同一层中的两个顶点，此时 \(G\) 包含一个奇环，因此 \(G\) 不是二分图。
【定理】一个图是二分图，当且仅当该图不包含奇环。
2. 有向图的连通性¶
【定义】我们称顶点 \(u\) 和 \(v\) 是相互可达的，如果既有从 \(u\) 到 \(v\) 的路径，也有从 \(v\) 到 \(u\) 的路径。
【强连通图】一个图被称为是强连通的，如果每一对顶点都是相互可达的。
【引理】令 \(s\) 为任一顶点，图 \(G\) 是强连通的，当且仅当从 \(s\) 出发，每一个顶点都是可达的。并且从每一个顶点出发，\(s\) 也是可达的。
【强连通图的判定】时间复杂度为 \(\cal{O}(m+n)\)。
- 任取顶点 \(s\)；
- 从 \(s\) 出发在 \(G\) 中运行 \(\tt BFS\)；
- 从 \(s\) 出发在 \(G^{rev}\) 中运行 \(\tt BFS\)；
- 图是强连通的，当且仅当在两个 \(\tt BFS\) 的运行中，所有的顶点都到达了。