图论复习

· · 个人记录

图论复习

强连通分量

对于一个有向图 A，若图上任意两点都能够相互到达，则称 A 是一个强连通图。

将有向图 G 的极大强连通子图 G_0 称为 G 的一个强连通分量。

tarjan 所提出的基于 dfs 求强连通分量的方法，本质上是暴力遍历图找到所有的有向环，然后对于每个点，将经过该点的有向环上的节点归入同一个强连通分量中。只不过对于已经遍历到的节点进行了记忆化，保证了复杂度。

显然缩点以后的图是一个拓扑图。

点双连通分量与割点

对于一个无向图 A，若对于图上任意两点 (u, v)，都存在至少两条起终点为 u, v 的路径 s_1, s_2，满足 s_1 中的点集与 s_2 中的点集的的交集为 \{u, v\}，则称 A 是一个点双连通图。用人话翻译就是对于任意两点都存在一组“点不相同”的路径。

将无向图 G 的极大点双连通子图 G_0 称为 G 的一个点双连通分量。

对于无向图 G 的一个点 u，若将其从图中删去后图的连通分量个数改变，则称 u 是 G 的一个割点。

显然两个点双之间是通过割点连接的（因为删掉 u 以后图的连通性改变证明这两个连通块之间互相连接的所有路径都要经过 u）。因此找到割点以后就可以找到点双了。

tarjan 提出的基于 dfs 求点双连通分量的本质依然是暴力找环。对于一个节点，若经过它的以 dfs 的方向为方向的有向环的所有节点在dfs树上都不是它的祖先，那么显然它是一个割点。当然，需要特殊处理根节点。

需要注意的是在 dfs 的过程中一个节点可能多次被置为割点，因此统计割点的个数应该在 dfs 结束以后再行统计。

边双连通分量与割边

对于一个无向图 A，若对于图上任意两点 (u, v)，都至少存在两条起终点为 u, v 的路径 s_1, s_2，满足 s_1 中的边集与 s_2 中的边集无交，则称 A 是是个边双连通图。用人话翻译就是对于任意两点都存在一组“边不相同”的路径。

将无向图 G 的极大边双连通子图 G_0 称为 G 的一个双连通分量。

对于无向图 G 的一条边 e，若将其从图中删去后图的连通分量个数改变，则称 e 是 G 的一条割边，又称为桥。

类似点双与割点的关系，两个边双之间是通过割边连接的。因此找到割边就可以找到边双了。

tarjan 提出的求边双连通分量的算法本质依然是暴力找环，只不过一条边是割边当且仅当这条边的出点所在的所有沿 dfs 方向的有向环都不能回到这条边的入点，那么该边是割边。因此应该把割点的判断条件 low[v] >= dfn[u] 改为 low[v] > dfn[u]。

2-sat问题

给定 n 个布尔变量，要求构造一组可行解，满足 m 个形如 A \Rightarrow B 的限制，其中 A, B 代表某个变量取某个值。

考虑建图，对每个变量 x 建立两个节点 x_0，x_1，一个代表取 true，一个代表取 false。对于一个 A \Rightarrow B 的限制，从 A 向 B 连一条边，再对于其逆否命题，即 \neg B 向 \neg A 连一条边。

这样，一条 u \rightarrow v 的边即意味着“若 u，则 v”，显然这个性质具有传递性，即若存在一条路径 u \rightarrow v \rightarrow w，则一定“若 u，则 w”。

显然如果存在一条 x_0 \rightarrow x_1 \rightarrow x_0 的路径，则意味着选了 x_0 则必须选 x_1，同时若选了 x_1 则必须选 x_0。此时无解。这只需要判断一下两点所在强连通分量即可，否则一定存在解。

考虑如何输出方案，缩点后，对于变量 x 的两个节点 x_0, x_1，取拓扑序较大的节点作为 x 的取值即可。

需要注意的是，在建边时一定要建出逆否命题对应的边，否则正确性是不对的。

差分约束系统

给定 n 个变量 x_i，要求构造一组可行解，满足 m 个形如 x_i - x_j \leq a_z 的不等式。

考虑建图，注意到 x_i - x_j \leq a_z 等价于 x_i \leq a_z + x_j，这与最短路的松弛方法一致。考虑建立一张 (n + 1) 个点的图，其中 0 号节点为源点，向其他所有节点连结一条权为 0 的边。然后对于每个限制，从 j 向 i 连接一条权为 a_z 的有向边。若令 x_i 为源点到第 i 个点的最短路，那么一定满足这 m 个限制。

当图中有负环时，相当于出现了一个 x_i \leq \dots < \dots \leq x_i 的不等式，这显然是无解的。

如果不等式的符号是大于号，直接在两侧同乘 -1 即可。

Kruskal 重构树

在进行 Kruskal 的过程中，将新加入的边当作一个点，将所联通的两个连通块作为左右子树。这样就得到了一棵 (2n - 1) 个点的新树。这棵树具有一些性质，比如自身是一个二叉堆。两点在原图中的瓶颈路最值即为两点在重构树上的 LCA 所代表的边的权值。

主要在处理瓶颈路有关问题的时候会有不错的效果。

欧拉路

欧拉通路指一条经过图中每条边且每条边只经过一次的通路。

欧拉回路首先是一条欧拉通路，并且还要求满足通路的起点与终点相同。

无向图存在欧拉回路的充要条件是图中没有度数为奇数的节点。

无向图存在欧拉通路的充要条件是图中存在欧拉回路或图中度数为奇数的节点有且仅有两个。对于后者，欧拉通路的起终点一定是这两个节点。

有向图存在欧拉回路的充要条件是图中所有节点出入度相等。

有向图存在欧拉通路的充要条件是图中存在欧拉回路或者只存在两个出入度不同的节点，其中一个节点出度比入度大一。对于后者，欧拉通路的起点一定是出度比入读大一的节点。

求出一条欧拉路的方法是直接 dfs，标记未通过的边即可。

图论有关概念

注意下述概念和定理适用于任意图，而不只是二分图。

匹配

匹配指的是图 G 的一个子图 G_0，满足 G_0 中任意两条边不相邻接。本部分以 G 代替原图，G_0 代替原图中的任意一个匹配子图。

最大匹配指的是边数最多的匹配子图。

交错路：指 G 的一条子路径，满足路径相邻两条边一条是 G_0 中的边，一条不是。

增广路：指第一条边和最后一条边都不属于 G_0 的交错路。

增广路定理：G 的匹配子图 G_0 是一个最大匹配当且仅当 G_0 不存在增广路。

点覆盖

点覆盖指的是图 G 的一个子图 G_0，满足 G_0 包含 G 中的所有边，且对于任意一条边都有至少一个端点属于 G_0。

最小点覆盖指的是点数最小的点覆盖子图。

边覆盖

边覆盖指的是图 G 的一个子图 G_0，满足 G_0 包含 G 中所有点，且对于其任意一个顶点都至少与一条 G_0 中的边相连。

最小边覆盖指的是边数最小的边覆盖子图。注意到概念不适用于存在度数为 0 的点的图。

（点）独立集

独立集指的是图 G 的一个子图 G_0，满足 G_0 包含 G 中所有的边，对于任意一条边，都最多有一个端点属于 G_0。

最大独立集指的是点数最多的独立集子图。

二分图

匈牙利算法实现的二分图匹配的正确性是基于增广路定理的，是一个绿与被绿的过程，其时间复杂度为两个点集大小之积，但是跑不满上界。

下面介绍三个二分图常用性质

  1. 最小点覆盖 = 最大匹配。
  2. 最小边覆盖 = 顶点数 - 最大匹配。
  3. 最大独立集 = 顶点数 - 最小点覆盖。

第三条也适用于带权图的情况。

对于不带权的二分图，第三条的证明方式是二分图的点覆盖与独立集是一一对应的。具体的，一个图去掉一个点覆盖中的节点以后，剩下的节点必然是一个独立集。

网络流

东西有点多……

这里写了一个网络流24题一句话题解，剩下有别的什么东西有空再补充叭……