2019-05-04 16:38 已编辑华东师范大学 C++

关注

【博客】图论知识点整理

图论笔记

度数序列

对于无向图， $d_1,d_2,...,d_n$ 为每个点的度数。有 $d_1+d_2+...+d_n=2e$ （每条边被计算两次）。
有偶数个度数为奇数的点。

Havel–Hakimi算法

给定一个由有限多个非负整数组成的度数序列，是否存在一个简单图使得其度数序列恰为这个序列。令 $S=(d_1,d_2,...,d_n)$ 为有限多个非负整数组成的非递增序列。 $S$ 可简单图化当且仅当有穷序列 $S’=(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)$ 只含有非负整数且是可简单图化的。序列 $S$ 可简单图化是指存在一个无向图（无重边无自环），使得其度数序列恰为 $S$ 。
（这个其实就是很显然的东西。。主要是一个定义）

Erdős–Gallai定理

令 $S=(d_1,d_2,...,d_n)$ 为有限多个非负整数组成的非递增序列。 $S$ 可简单图化当且仅当这些数字的和为偶数，且 $\sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$
对于任意 $1\leq k\leq n$ 都成立。也不难理解。对前 $k$ 个点分配度数，除了两两能连 $\frac{k(k-1)}{2}$ 条边外，剩下的度数由后面点的度数补。因为 $d_i$ 非递增，从小到大枚举 $k$ ，维护 $d_i$ 后缀与 $k$ 取 $\min$ 的和（ $d_i,k$ 都是单调的，维护从哪开始 $\min(d_i,k)$ 的结果是 $d_i$ ）。就可以 $O(n)$ 判断了。

例题：Good Bye 2018 E，NEERC2013 K.Kids in a Friendly Class。

欧拉路与欧拉回路

给定一张无向/有向图，求一条经过所有边恰好一次的回路。有解当且仅当所有点度数为偶数(无向)/入度等于出度(有向)。任选一点开始dfs，每条边只经过一次。回溯时将回溯的边加入队列，最后队列的逆序就是答案。时间复杂度 $O(m)$ .
欧拉路径也可以用一样的方法求出（找度数为奇数的点进行DFS）。

欧拉回路：有向图：所有点的出度入度都相等；从任意一点都可实现。
无向图：所有点度数都为偶数。

欧拉路：有向图：有两个点可以入度出度不相等（差不大于一），即起点终点；起点入度小于出度，终点入度大于出度。
无向图：仅有两个点度数为奇数。
注：必须为连通图（用并查集判断）。

两笔画问题：
有解当且仅当入度为奇数的点不超过四个。将其中两个点加一条边后求欧拉路径，然后在这条边处断开成两条欧拉路即可。时间复杂度 $O(m)$ .

题目

UOJ#117(模板)、题集。

Prufer序列

这里很全，可以看这儿。

Defination：
Prufer序列是一种无根树的编码表示。对于一棵 $n$ 个点的无根树，对应唯一一串长度为 $n-2$ 的 $Prufer$ 序列。

无根树转 $Prufer$ 序列

定义无根树中度数为 $1$ 的节点是叶子节点，每次找到编号最小的叶节点删除，在序列中添加与之相邻的点。如此重复直到剩下最后两个节点。

图片说明
上图对应无根树的 $Prufer$ 序列为 $3,5,1,3$ 。

$Prufer$ 序列转有根树

给定点集 $G={1,2,\ldots,n}$ ， $Prufer$ 序列 $[a_1,a_2,\ldots,a_{n-2}]$ 。每次取出 $Prufer$ 序列中的第一个元素 $x_i$ ，在 $G$ 中找在当前 $Prufer$ 序列中没有出现的第一个元素 $y_i$ ，在 $x_i$ 和 $y_i$ 间连一条边；将 $x_i$ 从 $Prufer$ 序列中删除， $y_i$ 从 $G$ 中删除。最后 $G$ 中还剩下 $2$ 个元素，在这 $2$ 个元素间连一条边。

生成树计数

Cayley定理：完全图的生成树个数为 $n^{n-2}$ 。如果每个点的度数为 $d_i$ ，那么生成树个数为 $\frac{(n-2)!}{(d_1-1)!(d_2-1)!...(d_n-1)!}$ 。每个连通块大小为 $a_i$ ，那么添加一些边将这些连通块连通的生成树个数为 $a_1\times a_2\times...\times a_n\times(a_1+a_2+...+a_n)^{n-2}$ 。

题目

题集。

Matrix-Tree定理

无向图生成树计数：令 $G=D-A$ （基尔霍夫矩阵=度数矩阵-边矩阵），然后去除 $G$ 的任意一行一列得到 $G’$ ， $G’$ 的行列式即生成树个数。

有向图生成树计数：与无向图不同的是， $D$ 矩阵为入度/出度矩阵分别对应外向树/内向树。且删掉第 $i$ 行第 $i$ 列表示以 $i$ 为根节点的生成树个数。

题目

题集。

最小生成树 Borůvka算法

一开始每个连通分量是一个点本身。每轮枚举所有属于不同连通分量的边，每个连通分量选择和其他连通分量相连的最小的边，然后合并。每轮连通块个数至少减半，所以最多进行 $\log V$ 轮。时间复杂度 $O(E\log V)$ 。
具体实现直接用并查集即可。代码可以看这里。

题目

一般用来做边权与点权相关，还是个完全图，求MST的题？

有 $n$ 个点的完全图，每个点的权值为 $a_i$ ，两个点之间的边权为 $(a_i+a_j)\ mod\ M$ 。求这张图的最小生成树。 $N\leq10^5,0\leq M,a_i\leq10^9$
具体怎么做忘了。。~~结合下面的题脑补一下。~~
CF888G。有一张 $n$ 个点的完全图，每个点的权值为 $a_i$ ，两个点之间的边权为 $a_i\ \text{xor}\ a_j$ 。求该图的最小生成树。 $n\leq2*10^5,0\leq ai<2^{30}$ 。

最小瓶颈生成树

使得生成树树上最大边权值最小。方法1：最小生成树一定是最小瓶颈生成树。方法2：二分答案，看点是否连通。方法3：类比找第k大值的方法(`nth_element`)，首先随机一个边权 $w$ 。然后将不超过这个边权的边加入，遍历这张图。如果图连通，那么瓶颈不超过 $w$ ，于是只需考虑边权不超过 $w$ 的边；否则将这些连通点缩起来，考虑边权大于 $w$ 的边。每次将问题的规模缩小至一半。期望时间复杂度 $T(m)=T(\frac m2)+O(m)=O(m)$ 。

单源最短路(SSSP)

$Dijkstra$ （贪心）或者 $Bellman Ford$ （动态规划）。时间复杂度 $O(m\log n)$ 或者 $O(nm)$ 。

一些变种

边权是 $0/1$ ：双端队列，如果是 $0$ 在头部插入，否则在尾部插入。

最长路径不超过 $W$ , 正权图：使用 $0...W$ 的桶+链表维护这些点（代替堆），时间复杂度 $O(m+W)$ 。

关于判负环

复杂度 $O(nm)$ 。代码实现可以记录最短路树上的深度来判环，而不是入队次数，这样会有优化。

if (dis[v] > dis[u] + w)
{
　　dis[v] = dis[u] + w;
　　dep[v] = dep[u] + 1;
　　if (dep[v] > n) return;
}

差分约束

大体过程：（具体可以看这里）

考虑最短路中的松弛操作： $if(dis[v]>dis[x]+w)\ dis[v]=dis[x]+w$ ，也就是强制使得 $dis[v]$ 满足 $dis[v]\leq dis[x]+w\Rightarrow dis[v]-dis[x]\leq w$ 。

所以对于 $x_j-x_i\leq w$ 的限制，可以连一条边 $(i\to j,w)$ 。这样求 $x_n-x_0$ 的最大值，就是求 $0\to n$ 的最短路。如果限制是 $x_j-x_i\geq w$ ，同理连边 $(i\to j,w)$ 。 $x_n-x_0$ 的最小值就是求 $0\to n$ 的最长路。如果两种限制都有，就把 $\geq$ 变成 $\leq$ 。

解的存在性：
比如求 $x_n-x_0$ 的最大值：若图中存在负环，则 $0\to n$ 的最短路无穷小，则不存在最大值（无解）。若 $0$ 和 $n$ 就不在同一连通块，则 $0\to n$ 的最短路无穷大，最大值无穷大（或者存在无数多解）。
否则有解。

PS：
$SPFA$ 可以根据入队次数判负环，也可以据此判正环。虽然效率都不高就是了。 $Dijkstra$ 不能求最长路（本质是贪心）。

如何判断解唯一：
对原图求一遍最短路。将原图取反，边权取反，求一遍最长路。
一个标号对应的是能取到的最小值，一个是最大值。
如果相同则解唯一。（没什么用）

题目

题集。

多源最短路(APSP)

$Floyd$ ： $O(n^3)$
$Johnson$ 算法（可用于负权图）： $O(nm\log n)$

$Johnson$ 算法

原理：首先给图中每个点一个权值 $h(u)$ , 把每条边的边权 $w(u,v)$ 改成 $w(u,v)+h(u)-h(v)$ 。对于 $s\to t$ 的一条路径 $p$ ，权值为
图片说明
=

所以这么做不会改变最短路。（具体也可以看[这里](https://blog.csdn.net/howarli/article/details/73824179)） **实现：**第一次SPFA预处理 $1$ 到每个点的距离 $dis$ ，记 $h(v)=dis(v)$ 。然后把边权 $w(u,v)$ 改为 $w(u,v)+h(u)-h(v)$ 。其中 $h(u)$ 为给每个点设定的权值， $h(u)=dis[u]$ 。由不等式可以得到 $dis(u)+w(u,v)\geq dis(v)$ ，也就是改完之后所有边权非负。之后可以每个点用 $Dijkstra$ 跑。就是 $O(nm\log n)$ 啦。这样也可以实现 $Dijkstra$ 跑费用流。

半径直径 (正权图)

（后面可能就直接抄dls课件了QAQ）

$u$ 的偏心距 $ecc(u)=\max\{dis(u,v)\}$
直径 $d=\max\{ecc(u)\}$
半径 $r=\min\{ecc(u)\}\ (d\neq2r)$
中心 $arg\ \min\{ecc(u)\}$ （要求定义在点上）
绝对中心（可以定义在边上）
图片说明

绝对中心

相关：[求最小直径生成树](https://blog.csdn.net/crazy_ac/article/details/8816877)（差不多）。实现：固定一条 $(u,v)$ ，考虑上面的点 $p$ 的偏心距。假设第三个点是 $w$ , $dis(p,u)=x$ 。那么对应的折线为 $\min\{x+dis(u,w),\ w(u,v)-x+dis(v,w)\}$ 。那么偏心距为 $n$ 条折线的最大值形成的折线。按左端点排序维护一下。时间复杂度 $O(nm\log n)$

最小直径生成树

即绝对中心的最短路树。如何证明？注意一棵树 $T$ 的直径为半径的两倍(对绝对中心来说)。如果最小直径生成树 $T’$ 不包含绝对中心，那么取 $T’$ 的绝对中心 $v$ ，显然矛盾。

拓扑排序

每次去掉图中入度为 $0$ 的点。时间复杂度 $O(n+m)$ 。
如果最后不为空集，那么这个图不为DAG。（否则每个点入度不为0，即每个点可以选择一个前趋，沿着前趋走根据抽屉原理一定能找到相同点，也就是一个环。）
按照反图DFS，出栈序列就是一个合法的拓扑序列。
scc缩点顺序也是一个合法拓扑序。

求字典序最小的拓扑序

每个点有不同的标号，要使得拓扑序最小。
将拓扑排序的队列改成优先队列即可。

最小拓扑序的一个变种

使得最后的拓扑序中1的位置尽量靠前，如果相同比较2的位置，依次类推。
首先考虑如何求1最早出现的位置，可以将原图反向，然后每次弹除了1之外的元素，直到队列只剩下1为止。
这是反图中1的最晚的出现的位置，也就是原图中最早的。
根据是否在队列里，这个图被分成两部分，在对应的图中用同样的方法处理2，依次类推。
容易发现每次找尽量大的元素出队，能完成上述的过程。
所以等价于反图最大字典序。

题目

题集。

二分图匹配

Hall's marriage theorem（霍尔定理）

对于一个二分图 $G=(X,Y,E)$ ，记 $S$ 为 $X$ 的一个子集， $N(S)$ 为所有 $S$ 中所有点的相邻点的并集。一个图有完备匹配当且仅当 $X$ 的所有子集 $S$ 都有 $|S|\leq|N(S)|$ 。
对一般图的推广:
图片说明
推论: 每个正则二分图都有完备匹配。

Kőnig's theorem

最小点覆盖=最大匹配 (与最大流最小割定理等价)
最大独立集=点数-最大匹配 (独立集为点覆盖的补集)
最小边覆盖=最大独立集 (独立集中每个点需要一条边去覆盖)

DAG最小路径覆盖

覆盖所有的边：每条边下界设为1, 然后求最小流。覆盖所有的点：建立二分图，对于 $u\to v$ 的边，看做二分图中的 $(u,v’)$ ，然后答案为点数-最大匹配。 $Dilworth$ 定理: 最大反链=最小链覆盖；最短的最长链=最小反链划分数-1（？存疑。见BZOJ4160）。（当然这个不应该只放在二分图部分的）

题目

题集。

连通分量

强连通分量

$Tarjan$ 。
将一个图的所有强联通分量缩起来会得到一个DAG。

双联通分量

点连通度: 最小的点集使得删去之后图不连通
边连通度: 最小的边集使得删去之后图不连通
如果一个图的点连通度大于1，那么是点双连通的，边连通同理。
双联通分量为图中的极大双联通子图。

割点和桥

考虑DFS树，每条非树边对应着一个点到祖先的路径。对于一条非树边只要把对应的边打上标记即可。比如对于 $(u,v)$ 这条非树边，只要在 $u$ 点打上 $+1$ 的标记， $v$ 点打上 $-1$ 的标记。 $x$ 到 $fa[x]$ 的树边的覆盖次数为子树内所有标记的和。
割点同理（注意特判根节点和叶节点）。
（emm没看懂下面要干嘛）
图片说明

题目

题集。

2-SAT

一堆变量的二元限制，问是否存在合法的赋值。
图片说明

题目

例题，题集。

曼哈顿距离与切比雪夫距离

将原坐标系每个点的坐标 $(x,y)$ 变为 $(x+y,x-y)$ ，则原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。反过来，将原坐标系每个点的坐标 $(x,y)$ 变为 $(\frac{x+y}{2},\frac{x-y}{2})$ ，则原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。
例题：BZOJ3170 松鼠聚会。