图论 笔记

· · 个人记录

由于学习方式并不系统，于是就出现了这篇文章。

知识点乱序摆放，请不要介意。

持续更新。

负环判定

最小环

欧拉路径 / 回路

判定：

如何寻找：

算法的正确性可以使用归纳法证明，删去对应的一条边之后仍然满足判定条件，因此这是正确的。

时间复杂度 O(n+m)。

注意在 \text{dfs} 的时候枚举边集时每经过一条边就要把这一条边从边集中删去，否则时间复杂度会退化为 O(nm)。

一个推论：图上欧拉路径最小划分数

欧拉回路计数：有向图欧拉回路计数参见 \textbf{BEST 定理}，无向图欧拉回路计数是 \texttt{\#P(Sharp P)-Complete} 问题。（据说比 \texttt{NP} 问题还要难）

割点、点双连通分量与圆方树

下面均为在 无向图 上讨论以上元素。

注意：无向图上 DFS 时只有树边和返祖边。

桥与边双连通分量

2-SAT

有 n 个元素，每个元素有 2 种状态 (0/1)。
现在给出 m 个限制 (a_i,b_i,w_i,v_i)：若第 a_i 个元素为 w_i，则第 b_i 个元素必须为 v_i。
问是否有合法方案，并给出构造。

我们将每个元素分成 x_{i,0},x_{i,1} 两个点，考虑往里面连边。那么对于一个限制 (a_i,b_i,w_i,v_i)，则：

然后我们跑 \texttt{Tarjan}，此时所有的强连通分量均表示「若有一状态成立则所有状态均成立」。

时间复杂度 O(n+m).

这个算法只能够用作 判定 和 构造特解。而无法构造出所有合法方案。

Hall 定理

这个充要条件简单来说，就是如果在二分图上左部点的任意一个子集，它所有连向右部点的集合（邻域）大小，总是比该子集要大。

证明：

那么我们能找到一个子集，它的邻域比它小，那肯定会有左部点无法匹配。显然矛盾。

我们使用类似匈牙利算法的思想，重复以下步骤：

以此类推就能找到一条增广路。因为这张图满足 Hall 定理，所以总能找到右部点，因此可以一直增广，直到找到完美匹配。

这个定理也可以适用于二分图带权完美匹配的判定。

考虑反证法。假设存在左部点的一个子集 S，使得 |S| > |N(S)|，那么右部点的度数总和

\sum_{i\in N(S)} \deg(i)< k·|N(S)| < k·|S| \le \sum_{i\in S} \deg(i)

明明向邻域连了 \sum\limits_{i\in S} \deg(i) 条边，而邻域的度数总和居然严格小于这个总边数。故假设矛盾，因此原命题正确。

虽然这个推论好像有点反直觉。（仅凭度数大小就能判断是否存在完美匹配）

我们称所有点的度数均为 k 的二分图为 \bf k-正则二分图，那么由这个推论可知 \rm k-正则二分图 必然存在完美匹配。

二分图最大匹配

匈牙利算法

考虑每次新加入一个左部点，不断调整匹配。我们沿着左部点的每条边找右部点：

每次暴力调整时我们最多把每个右部点访问一次，故总时间复杂度为 O(nm)。

代码量很小。而且时间复杂度经常跑不满。

通过这个算法我们可以很容易得到一组方案。

网络流

新建超级源点和超级汇点。

正确性，显然。一组匹配相当于 1 个单位的水。时间复杂度已被证明为 O(m\sqrt n) (证明)。

代码量中等，但是时间复杂度优秀，并且可以有很多拓展（可以给边加上其他信息）。

二分图带权最大匹配：KM 算法

对于这个我没有什么很好的理解，只能跟着题解的思路走.....

首先将原问题转化为二分图带权「完美匹配」问题：

则此时这个图必有完美匹配。

给每个点定义一个权值，该算法称这个权值为「顶标」。我们记点 i 的顶标为 l_i。

对于一条边 (x,y)，需满足：l_x+l_y-w(x,y)\ge 0.

我们再新建一个子图。这个图由原图生成：若原图的一条边 (x,y) 满足 l_x+l_y-w(x,y)=0，则将这条边加入这个子图中。

证明： - 原图的一个完美匹配权值总和为 $\sum w(x_i,y_i)\le \sum l_{x_i}+\sum l_{y_i}

故原图的任一完美匹配总是小于等于该子图的完美匹配。

现在问题转化为给这一系列「顶标」定权，使得子图存在完美匹配。

类似于匈牙利算法。考虑加入一个左部点 x，我们调整匹配和右部点的顶标。

我们需要求出所有 x 与右部点的连边 的 d=l_x+l_y-w(x,y) 最小值和具体对应的边。然后给所有已匹配的左部点 -d，右部点 +d。然后就能保证这条最小的边的 d=0，给这条边加入子图。

重复这样的过程，最后就能求出来了。

这样的时间复杂度是 O(n^4) 的，可以使用：1.实时记录同一个右部点的 d 的最小值；2.匈牙利算法改成 bfs 形式。 优化到 O(n^3)。

KM 算法只能求解匹配问题。因为它只是一种大力强行调整匹配的算法......

事实上，二分图带权最大匹配也能用费用流做，建边与二分图最大匹配相似，只是增加了费用。

传递闭包

使用类似 \texttt{Floyd} 的算法实现即可。只不过矩阵里面的数变成了 0/1。

可以用 \texttt{bitset} 优化。

如果不一定要把任意两点的答案求出来，则容易先缩点再拓扑排序求得答案。

差分约束

构造一组解使得方程组 { x_{p_i} - x_{q_i} <= d_i 成立，或者说明无解。

这个很熟悉了。只列一下常见转化：

由于这些变量整体加/减一个值没有影响，所以我们令某一个变量为 0，然后跑 SPFA(有负权边) 即可。

无解的条件是，存在负环。

同余最短路

1. 完全背包，物体的重量很小，但是背包容量很大，问能不能拼出这个容量；
2. 完全背包，拼出最小的模 K 余 p 的数；

具体操作是我们找到一个合适的数作为这个背包的「模数」p（可以选定一个物品的重量，也可能是题目给出的）。此时状态 f(i) 表示「能拼出的重量 满足 \bmod p=i 的最小重量」。

然后把物品视作一个个转移：f((i+w)\bmod p)=f(i)+1；

然后跑最短路即可。

但是这样转移有一定的局限性，每个状态要么记「最小的重量」却不知道这个重量是如何拼出来的，要么记「能拼到这个模数的最大价值」而不知道这个价值真正的重量是多少。它丢掉了一些信息，换来的是时间复杂度的改进。

最小斯坦纳树

给定的 k(<=10) 个关键点，要求在原图上选一些边使这些关键点连通且代价之和最小。

如果没有关键点的限制，则退化为最小生成树问题。类比可以推出，最优方案必定也是一棵树。

- $i$ 的度数为 $1$：则 $f(S,i)=f(S,v)+w_{i\to v}$； - $i$ 的度数 $>1$，则 $f(S,i)=\min_{T\subset S} f(T,i)+f(\complement_S T,i)

对于第一种情况，使用 \texttt{Dijkstra} 对 f(S,\_) 进行最短路。

对于第二种情况，可以枚举子集。

注意我们要先处理第二种情况再处理第一种情况（原因：先继承前面的状态）。

注意按照 |S| 升序枚举。

时间复杂度 O(n·3^n+(n^2+m\log m)·2^n)，若用堆优化则 O(n·3^n+(n+m)\log m·2^n)。但其实并没有必要。都能状压了, n^2 轻轻松松

同时我们注意到这是模板题却使用了指数级算法。维基百科告诉我们，普通的斯坦纳树问题是 \texttt{NP-hard} 问题。

最小割树

给定一个无向图，有 Q(<=10^5) 次询问，多次求两点间最小割。

类似于最小生成树代替两点路径最小值一样，我们对于这个两点最小割也构造出一个「最小割树」。

构造方法：

  1. 选定两个点（随便选定），求出这两点在原图上的最小割。
  2. 对于我们在最小割树上连接这两个点，边权为最小割的值。
  3. 根据最小割的割边方案可以将点集分成两个互不相交的集合。
  4. 对于这两个集合继续递归求解。直到集合只剩一个元素为止。

.\triangle 性质：两点在原图的最小割 = 两点在最小割树的路径上边权最小值。

简略证明：

  1. 【引理】可行割 \ge 最小割。（显然）
  2. 【证明上界】对于每次分割成的两个集合 S_x,S_y，\forall p_0\in S_x,p_1\in S_y,Cut(x,y)\le Cut(p_0,p_1)。显然 p_0 到 p_1 是 x 到 y 的最小割的一种可行割。因此路径上的最小值必然也 \ge Cut(x,y)。
  3. 【证明下界】\forall z,Cut(x,y)\ge\min(Cut(x,z),Cut(z,y))。因为 x,y 的最小割中 z 要么在 x 一侧，要么在 y 一侧，所以 Cut(x,y) 必然是 Cut(x,z),Cut(z,y) 之一的可行割。因此路径上的最小值必然也 \le Cut(x,y)。

因此 Cut(x,y)= 最小割树路径最小值。

最坏时间复杂度 O(n·\text{最大流复杂度})=O(n^3m)。但很难达到该上界。

最小树形图

重复这样的过程：

对于（除了根的）每个点，我们找到每个点的入边中权值最小的边，并记下对应的出点，将边权累加到答案中。

由于这里只有简单环，所以我们不需要用 \texttt{Tarjan} 缩点，只需一步步往前跳，若跳到前面跳过的点则停止即可。

网络流技巧

有了 dinic，就有了全 世 界！

好文章：click / click / click / click

网络流相当于给予了你一个可以进行最优决策的自动机。因此衍生出了许多问题。

咕咕咕 只会一些简单的

杂项

输出方案

虽然这不是建图技巧，但我没位置放了

最小割的可行边和必须边

显然 \{\text{必须边}\}\subseteq\{\text{可行边}\}.

可行边的充要条件：

必须边的充要条件：

二分图匹配：超级源点和超级汇点

  1. S - x[i]：边权为 1；
  2. x[i] - y[j]：边权为 1，前提是这两个点有边；
  3. y[j] - T：边权为 1。

已被严格证明时间复杂度为 O(m\sqrt n)。

最大权闭合图（01 最小割）：「选择负权边 \to 舍弃正权边」的转化

一个非常经典的模型，可以解决许多「二元对立」的最优化问题。

有n个点，每一个点可以选或者不选。
一个点选了或者不选，要付出一定的代价或者得到一定的收益（或者说收益有正有负）。
有一些点之间有特定的关系。求最后的收益/代价最大或者最小。

注意这里权值都是正的。

对它求一个最小割，答案为「(正数的)收益总和 - 最小割」。

它的意义是：

让「承担的代价 + 舍弃的利益」最小，因此用最小割是正确的。

距离限制模型（切糕模型）

有 n 个元素，每个元素可以选择 [1,k] 中的数，每个数有一定的收益。
限制：规定元素 p_i,q_i 选择的数之差不超过 D.
求合法的最大收益
  1. 连 n 条这样的链：S\to 1\to 2\to\dots\to k\to T：代表一种元素的选择，边权为每个数的收益。当我割掉一条边就说明该元素选择了这个数(并获得该收益)。
  2. 对于限制中的 p_i,q_i：将所有的 (p_i,x+d)\to(q_i,x) 和 (q_i,x+d)\to(p_i,x) 连一条权值为 +\infty 的边。意义：当这两个元素割掉了了差值大于 d 的边，那么这里面就会有一条边使这两条链把 S,T 联通。

形象理解

对它求一个最小割即可。

网络流相关 图论经典模型

\textbf{DAG} 上最小不相交路径覆盖

结论：

\textbf{最小不相交路径覆盖数 = 顶点数 - 最大匹配数}

假设我们一开始没有任何的边，每一条路径只包含一个点。如果给其中两个路径的首末连一条边，那么这两条路径就会发生合并。也就是说，这个时候路径数就减少了 1。

如果我们把最大匹配的每组点的首末都连起来，那么路径覆盖数就是最少的。

因为每个点会指向某一个点，也有可能被某一个点指向。因此我们应该将一条边拆成两个点 in(i),out(i)：

跑一个最大流即可。

如果使用匈牙利算法，在实现过程中可以不用拆点，还可以很容易得到一组方案，我们将匹配当做一条边即可。

\textbf{DAG} 上最小可相交路径覆盖

我们对原图先用 \texttt{Floyd} 求一个传递闭包。这样转化后，两点有边相连只说明 两点存在路径。所以这个图的一条路径等价于原图的一条路径，但只是选择了这条路径上的若干个点。

如果我们对这个图求 最小不相交路径覆盖，如果两个原图上的路径相交，在新图上我们可以令其「越过」相交的点，这样就可以考虑到了相交路径了。

二分图最小点覆盖

\textbf{König 定理：二分图上最小点覆盖数 = 最大匹配数}

如何构造方案：假设我们已经通过匈牙利算法求出了最大匹配。现在我们执行下列操作：

我们梳理一下这个被标记的二分图的性质：

  1. 未被匹配的左部点和右部点 一定不存在边相连。

    否则匹配数还能增加。因此未匹配左(右)部点的边一定连向已匹配的右(左)部点。

  2. 不可能存在一条边使得 左端点被标记，右端点未被标记。

    否则在遍历这个左端点的时候，我们就会成功找到一条增广路。根据这个性质，我们便可以证明选出的点集可以覆盖所有的点。

  3. 未被匹配的左部点 一定被标记。

    因为它们一定会被作为寻找增广路的起点被标记。因此它们不会被纳入选出的点集中。

  4. 未被匹配的右部点及与其相连的左端点 一定不会被标记。

    因为和它相连的左端点一定是匹配点。若左端点被标记，那么就会顺理成章地访问到这个右部点，从而找到增广路。因此这两个端点都不会被标记。因此它们也不会被纳入选出的点集中。

  5. 对于一条匹配边，要么都未被标记，要么都被标记。

    因为不可能右端点被标记而左端点未被标记，否则右端点可以通过这条匹配边访问到左端点。再根据性质 2.，我们可以总结出该性质。因此每一条匹配边均会恰有一个端点纳入选出的点集中。

    根据性质 3~5，这个选出的点集的大小即为最大匹配数。

  6. 最大匹配数为最小点覆盖集的下界。

    这是显然的。因为对于每个匹配至少都要选择一个点才能覆盖这一条边。

根据以上性质，我们证明了该点集为合法点覆盖集且为最大匹配数，并证明了最大匹配数为最小点覆盖的下界。因此该点集为最小点覆盖集。同时顺便证明了 \textbf{König 定理}。

二分图最大独立集

结论：

\textbf{最大独立集 = 顶点数 - 最小点覆盖}

因为如果我们将最小点覆盖的点去掉，那么剩下的每条边均只剩下一个端点，因此这一定是独立集（定义）。又因为最小点覆盖是点数最小的，因此最小点覆盖的 补集是最大独立集。

即在做完上面求最大匹配 + 增广标记之后，被标记的左部点 和 未被标记的右部点 组成了最大独立集。

一般图 的最大匹配、最小点覆盖、最大独立集都是 \texttt{NP-hard} 问题。

Dilworth 定理

一些定义：

狄尔沃斯定理(Dilworth's theorem) ：亦称偏序集分解定理。

\textbf{最长反链长度 = 最小可相交链划分数}

构造方案：如果我们若想要求一个 DAG 的最长反链，那么我们先求传递闭包，然后拆点求最大独立集，那么最长反链即为最大独立集 左右部点之交。

构造方案正确性证明：显然这个构造出的反链是合法的，现在我们需要证明这个反链是最长的。由上面的构造过程有

  3. 由上面两式得：(2n-m)-\text{构造反链} \le n，即 \text{构造反链} \ge n-m.
  4. 又由 \text{最长反链} \le \text{最小可相交链划分数} = n-m，因此 \text{构造反链} = n-m.

因此我们证明了构造出的反链为 最长反链。

\textbf{最长链长度 = 最小反链划分数}

常作第一步转化用。

有上下界的网络流

无源汇上下界可行流

由于每条边现在的流量限制从 [0,r_i] 变成了 [l_i,r_i]，所以我们先钦定每条边的初始流量为 l_i，而这条边可调控的限制变成了 [0,r_i-l_i]。

对于每个点，我们算出流入这个点和流出这个点的初始流量 in(i),out(i)。

然后对于每个原来的边我们照样连 u_i\to v_i，只不过流量变成了 r_i-l_i。

最后跑一次最大流即可。合法的条件是每一条 S\to i 和 i\to T 的边都是满流的。（因为本来我们就是假定了这些边满流）

有源汇上下界可行流

现在出现了源点和汇点。此时容易发现，若我们按照无源汇的方法去连之后，只有源点和汇点不满足流量守恒。

所以我们增加一条 T\to S，流量为 [0,+\infty]。这样整个系统又能转起来了。

注意无源汇的 S/T 与这里的源汇点是不一样的。需要新建一个 SS/TT 作为真正的超级源汇点。

有源汇上下界最大流

我们按照上面的做法，可以得到可行流。现在我们需要得到最大流。

我们删除超级源点和超级汇点和新增的 T\to S 边。在残量网络再跑一次 S\rightsquigarrow T 的最大流即可。

事实上，我们只需要删除 T\to S 边，因为存在可行流亦可以说明与超级源汇点相连的边都是满流的，相当于不存在。

有源汇上下界最小流

最大流的思想是：我们先求出可行流，然后考虑在这个可行流上调整。事实上最小流也是这样的思想。

我们删除(超级源点和超级汇点和)新增的 T\to S 边。在残余网络再跑一次 T\rightsquigarrow S 的最大流即可。（意义理解：反悔流）

答案为：可行流 - T\rightsquigarrow S 的最大流。

有源汇上下界最小费用 可行流/最大流/最小流

给边权增加费用的信息即可。

以上，我们将上下界网络流转化为了普通网络流问题。因此上下界网络流的时间复杂度均与普通网络流的复杂度一致。

实战时，(先考虑)普通网络流建模 \rightarrow (不行再)上下界网络流建模 \rightarrow (最后再)费用流建模

模拟费用流

无向图三元环 / 四元环计数

1. 给定一张无向图，求出 (a,b,c) 的无序对数使得它们两两有边。
2. 给定一张无向图，求出 (a,b,c,d) 的无序环数使得它们相邻两两有边。

考虑给所有的边定向。对于一条边：

不难发现这样的图是 DAG。注意到原图中：

对于三元环，我们枚举 x 的邻接点 y，再枚举 y 的邻接点 z，然后 z 是否为 x 的邻接点。如何快速判断一个点是另一个点的邻接点？对于每个 x，我们先把所有 x 的邻接点先用个数组打个标记，然后就能快速判断了。

对于四元环也类似，我们主要计算 x 有多少不同的「只走两步」的方式可以到达 z，我们每次将 y 的邻接点 z 处的操作改打标记为 记录标记次数，这样就可以统计出来每个 z 的标记次数 cnt_z。最后直接计算 \sum \binom{cnt_z}{2}.

这个算法的时间复杂度是 O(m \sqrt m)。（注意只与边数 m 相关）。

在每轮的 x 访问它的每个邻接点的时候，我们扫描了一遍这个邻接点的邻接点集合。所以每一条边的贡献为 O(\sqrt m)。故总时间复杂度为 O(m\sqrt m)。

因此，我们通过这个算法可以得出一个小小的结论：一个图中三元环的数量上界为 m\sqrt m（注意是边数），至于与点数有关的就是 O(n^3) 了。

Kruskal 重构树

定义：我们将 Kruskal 每次连边的时候，新建一个虚点连向这两个集合作为它们的父亲，定义父亲的权值为加入的这条边的权值。最后得到一个 (2n-1) 个节点的新树。

性质（这里只讨论边权总和最小的 Kruskal 生成树）：

平面图

弦图

圆方树

支配树