口胡图论

前言

本文大多是口胡，可能有误。

大多数都是参考 oi-wiki，

还有一些其他巨巨的博客。

还有 二分图最大权匹配，一般图匹配，一般图最大匹配... 没学, 懒得学了，不常考(flag)。

最短路

oi-wiki

最短路算法

• floyd: \(O(n^3)\)。

• spfa: \(O(nm)\)。

  判负环存在，严谨做法是建个超级源点，跑spfa，入队次数 \(> n\) 有负环。

• dijkstra:

  优先队列：\(O(m \log m)\)。

  线段树：\(O(m \log n)\)。

• Primal-Dual 原始对偶算法 / Johnson 全源最短路径：

  实际上是：dijkstra跑负边权。
  1. 跑一遍 spfa，得到初始势能 \(h_i\)。
  2. 将dijkstra 边权设为 \(w(u, v) + h_u - h_v\)。
  3. (费用流里的操作)再将 \(h_i\) 加上 \(\text{dis}_i\)。

  最后原图的 \(s -> t\) 的最短路是 \(\text{dis}_t + h_t - h_s\)。

差分约束

• 作用：求几个有两个未知量的一次不等式的解。

• 最短路最后求出来的 \(\text{dis}\)数组满足: \(\text{dis}(u) + w \geq \text{dis}(v)\)。
  对约束条件按照上面的形式连边就能跑出一个解。

• 连边：对于 \(a = b\) 这样，连两个边， \(\leq\) 和 \(\geq\)。

• 负环：无解。

k 短路

oi-wiki k短路

口胡一下 A*:

设计评估函数 \(f(u) = g(u) + h(u)\)

其中 \(g(u)\) 是起点到 \(u\) 的最短路，\(h(u)\) 是终点到 \(u\) 的最短路(反图)。

优先队列里存 \((x, g(x))\)，初始是 \((s, 0)\)。

选评估函数最优的点，向相邻点扩展。

当一个点被访问 \(k\) 次时就是 k 短路。

要指定一个点，不然一条最短路径会被多个点重复算。

时间复杂度 \(O(nk \log n)\)。

同余最短路

• 就是同余下的最短路，难点在于建出图。

• 主要利用同余等价类中选出最优。

树

定义：\(n\) 个点，\(n - 1\) 条边的连通无向图(有时有向)。

遍历

• dfn 序

  特点：子树所有点连续。

• bfs 序

  特点：深度相同的点连续。

• 欧拉序?(或者说是括号序)

  特点：连续一段内出现奇数次的是树上的路径。

树的直径

oi-wiki树的直径

• 定义：树上两点的最大距离。

• 求法：

  1. 两次dfs。
  2. 树形dp。

• 性质：若树上所有边边权均为正，则树的所有直径中点重合。

树的重心

oi-wiki树的重心

• 定义：以重心为根时，最大子树的最小

• 性质：

  1. 以重心为根时，子树大小不超过总大小的一半。

  2. 所有节点到重心的距离和最小，到两个重心的距离和相等。

  3. 两颗树合并时，新的重心只会原来两个重心的路径上。

  4. 增加或减少一个叶子，树的重心最多移动一条边。

树链剖分

• 重链剖分

  构造：按照子树大小连重链。

  性质：树上一条路径可以分为 \(O(\log n)\) 段。

• 长链剖分

  构造：按照子树最深深度剖分。

  性质：优化与深度有关的dp的空间。

树上启发式合并

• 做法：每次保留重儿子信息，暴力跑轻儿子。

• 解决问题：一般是 静态子树内问题。

• 操作完所有子树的时间复杂度 \(O(n \log n)\)。

• 注意的地方：弄出dfs序比较好对子树操作。

虚树

• 用处：构建只有出关键点和任意两个点之间的 LCA 的树，优化时间。

• 构建：

  1. 按照 dfs 序排序，先加入 1 号点方便，后面特判一下 1 号点避免重复加入。

  2. 用一个栈维护一个链，从栈顶到栈底的 dfs序逐渐变小。

  3. 求出当前节点和栈顶节点的 lca，弹出栈底直到将栈顶往下第 2 个节点 dfs 序 \(\leq\) lca 的 dfs 序，弹的过程中要连边。

  4. 等于就只弹栈顶，否则就替换栈顶，这样总是能是一条链。

  5. 最后加入当前节点。

点分治

• 用处：处理树上静态路径问题。

• 构建：每次找出重心，切除在子树找出重心，不断循环，时间复杂度 \(O(n \log n)\)。

• 注意递归时候的子树大小。

边分治

不太懂。

• 构建：选边尽量平均分子树。

• 多叉树变二叉树？

点分树/动态树分治

• 用处：支持点分操作的修改查询。

• 构建：将点分治的重心相连，每次分治中间记录这次分治的结果。

• 注意点：空间可能很大，时间可能很慢，码量可能很大。

最小生成树

• krukal

1. 排序贪心。

• prim

1. 选最小能合并两个连通块的边。

• Boruvka 算法

1. 给每个点求出属于的连通块。
2. 对每个点求出连出其它连通块的最小边。
3. 根据最小边将连通块合并。

最小树形图

有向图的最小生成树，要求以某个点为根能到剩下所有点

朱刘算法 \(O(nm)\)。

注意判根，判自环。

1. 贪心，给每个点找最小入边。

2. 找环，无环即是答案。

3. 有环，缩点，重新标号，给连入环的边的边权去减去环内的指向当前点的边，返回第一步。

次小生成树

1. 求解出最小生成树，尝试用没选中的边去更新选中的点， 需要维护树上路径最大值(严格次小还要维护次大值)。

瓶颈生成树

定义: 最大边权权最小的生成树。

最小生成树一定是瓶颈生成树，反过来不一定。

反证法：瓶颈生成树有一条边更小，那么就能变成更优的最小生成树。

Kruskal 重构树

• 构造：在 kruskal 算法过程，对选出来的一条边的两个点连向一个新建的点，这样就能构成一个树形结构，点权就是边权。

• 特点：这个树还是小根堆。

• 解决连通块内经过边权 \(\leq k\) 的边能到达的地方的问题。

最小斯坦纳树

• 构造：求一个无相连通图的包含钦定点的子图满足一些条件。
• 答案往往是一颗树，本质上是状压dp，枚举子集转移。
• 状态一般是 \(f_{i, S}\), 以 \(i\) 为根，选了给定的点的集合 \(S\)。
• 转移有两种，一种有顺序，就要跑最短路，另一种直接枚举子集转移。

最短路径树

• 性质：任意一点到根节点的距离都是原图中最短路。

• 构建：记录松弛时候的转移点即可，向转移点连边。

• 发现到可以和非树边搞最小环。

树的同构

• 有些树可能是同构的，通过定根交换子树位置就相等了。

• 判断我用树哈希。

prufer序列

• 用处： 将 \(n\) 个点的无根树与长 \(n - 2\) 的序列构成双射。

• 用树构建prufer序列：

  每次选择编号最小的叶子节点，将它的父亲压入序列，减它父亲的度数。
  最后剩下两个节点。

  线性构建：

  可以看成从叶子往根连的DAG，下面说的度就是入度。

  1. 标号小到大枚举，找到度为0的点，加入prufer序列。
  2. 如果加入的点编号更小，那就先更新这个点，知道加入的点标号比当前的大。

• 用prufer序列构建树：

  每次选择编号最小的当前出现次数最小的点，它父亲就是当前prufer序列的数，让这个数的出现次数 -1。
  线性构造构造类似。

• 性质：

  1. prufer序列中一个数出现的次数就是它在树上的度减一。
  2. \(n\) 个点的无根树的个数是 \(n^{n - 2}\)。
  3. 可以统计限制度数的生成树。

矩阵树定理：

参考：

oi-wiki

zhihu巨巨

%%%yyc

不允许自环

不会证明。

• 无向图生成树计数：

主要是关联矩阵 \(A\), \(B\)：

无边权的树的 \(w_i = 1\)，度矩阵在有边权的时候是出\入边的边权和。

矩阵 \(A\) 是 \(n \times m\) 的矩阵：

1. 点 \(i\) 是边 \(j\) 的起点时，\(A_{i, j} = \sqrt{w_{j}}\)。
   2. 点 \(i\) 是边 \(j\) 的终点时，\(A_{i, j} = -\sqrt{w_{j}}\)。
   3. 否则为 0.

令 \(B = A^T\), \(B\) 是 \(A\) 的转置。

得到 \(L = AB\), 记 \(L\) 是Laplace矩阵。

实际上， \(L\) 就是原树的度数矩阵 - 邻接矩阵。

记 \(L'\) 是 \(L\) 除去任意第 \(k\) 行第 \(k\) 列。

那么就有 \(\text{det}(L')\) 是生成树个数。

• 有向图生成树计数：

当计算 内向树 个数时，只需要改 \(B\) 的定义：

1. 点 \(j\) 是边 \(i\) 的起点时，\(B_{i, j} = \sqrt{w_{i}}\)。
2. 否则为 0。

这样的 Laplace 矩阵就是出度矩阵 - 邻接矩阵。

但是 \(L'\) 是 \(L\) 除去根所在的行和列剩下的矩阵。

同理，计算 外向树，\(B\) 的定义相反：

1. 点 \(j\) 是边 \(i\) 的终点时，\(B_{i, j} = -\sqrt{w_{i}}\)。
2. 否则为 0。

得到 Laplace 矩阵就是入度矩阵 - 邻接矩阵。

注 :手玩出来的减去的好像是转置的邻接矩阵，但是这样转置行列式不变。

连通性相关

割点

• 定义：在无向连通图中，点 \(u\) 割去，原图就不连通，那么就称点 \(u\) 是割点。

一个点要是割点，有两种情况：

1. 如果是根，它被割去后，子树间一定不连通，因此子树个数 \(\geq 2\) 时，就有多个连通块。

2. 不是根 的话，它的子树能没有返祖边，那么割去这个点后，子树和父亲所在的树就相互独立了。

桥

• 定义：在无向连通图中，边 \((u, v)\) 割去，原图就不连通，那么就称边 \((u, v)\) 是桥。

求桥，如果一个儿子 \(v\)没有返祖边，那么这个点到儿子这条边就是桥。

缩点 / 强连通分量

• 定义：
  1. 在有向图中，点集中任意两点可以相互到达，就称这个图是 强连通的。
  2. 在有向图中，最大的强连通的子图，称为这个图的 强连通分量。

在 dfs树上，一个强连通分量是 dfs树 的连通子树。

tarjan 算法可以确定每个强连通分量在 dfs树上的位置。

边双连通

• 定义：无向图中，对于 \(u\) 和 \(v\), 随便删去图中一条边，\(u\) 和 \(v\) 都连通，那么称 \(u\) 和 \(v\) 边双连通。

• 边双连通有传递性。

• 判断：两点之间不存在桥。

点双连通

• 定义：无向图中，对于 \(u\) 和 \(v\), 随便删去图中一个不是 \(u, v\) 的点，\(u\) 和 \(v\) 都连通，那么称 \(u\) 和 \(v\) 点双连通。

• 点双连通没有传递性。

• 判断：两点之间不存在割点。

圆方树

oi-wiki

• 点双连通分量：

  定义：任意两点都是点双连通，圆方树的定义采用没有割点的连通图作为判定点双连通分量的依据，在只有两点时有特殊情况。

  性质：同一个点双中的两不同点 \(u,v\) 之间一定存在一条简单路径经过给定的在同一个点双内的另一点 \(w\)。

• 形态：将每个点双连通分量看成方点，里面的点就是圆点，连向方点，方点之间通过割点(圆点)相连。

• 构建：求割点，在割点处建新方点，将点双内的点连向方点，用栈实现。

• 用处：求两点所有简单路径的问题，计算的割点的问题，点双的问题，转化为树上问题。

DAG有向无环图

• 定义：顾名思义...

• 特点：

  1. 存在多个入度为 0 的点和多个出度为 0 的点。
  2. 没有环。
  3. 可以用两个点 \((u, v)\) 表示唯一一条路径。

• 判断：拓扑排序，每次删掉入度为 0 的点。

反链与链

参考文章

前提：在 DAG 中

反链：集合中任意两点不能相互到达的集合。

• Dilworth定理: 最长反链长度 = 最小可相交链覆盖

• 最长反链长度 \(\leq\) 最小可相交链覆盖

1. 因为每个反链的点都会在一条链上。

• 最长反链长度 \(\geq\) 最小可相交链覆盖

归纳证明：

1. 一个点的图显然成立。

2. 假设点集\(V\), 反链集 \(A\), 能到达 \(A\) 的所有点集合 \(B\), \(A\) 能到达的所有点的集合 \(C\)，设入度为 0 的点是源点，出度为 0 的点是汇点。

   1. 假设 \(A\) 至少有一个点不是汇点和源点。
      有以下结论:
   • \(C \neq V, B \neq V\), 由于上面假设只要成立一个，那么 \(A\) 都全是汇点或源点。
   • \(C \cap B = A\), 反证法，如果存在一个不在 \(A\) 的点，但在 \(C, B\) 的点，要么与集合 \(A\) 的某点成环，要么某两点可以相互到达，就反链个数就变了。
   • \(C \cup B = V\), 反证法，如果存在一个点不能到 \(A\) 和 \(A\) 不能到，就多一个反链。
     - 对于 \(C\) 和 \(B\) 假设成立，并且每条 \(B\) 和 \(C\) 中的链包含\(A\) 中的某个点，一条不同链对应一个不同点。\(C\) 和 \(B\) 的链 按照 \(A\) 中的点相同就进行拼接，那么链的总数不变，反链大小也不变，假设就成立了。
   2. 如果全是汇点或源点。
   • 考虑选一个 \(A\) 中的点，找到另一个 \(V\) 中的源点或者汇点，将它们删去，得到一个子图。这个子图满足反链大小是 \(|A| - 1\)， 不然就有不在汇点或者源点的反链上的点，那么假设 1 可以就证明了。
   • 根据假设，子图的最小链覆盖可以是 \(|A| - 1\), 再加上删去的那两个点的路径，就是 \(|A|\) 了，也满足假设。

   于是就有 最长反链长度 \(\geq\) 最小可相交链覆盖。

最小可相交链覆盖在下面二分图部分。

• 对偶定理：最小反链覆盖 = 最长链长度

这个 DAG dp \(O(n)\) 就能求。

LGV引理

• 用处：可以用来处理有向无环图上不相交路径计数等问题。

但是这里计算出来的答案是带权的。

有起点集合 \(A\), 终点集合 \(B\),

令 \(e(A_i, B_j)\)，是每一条 DAG 上点 \(A_i\) 到点 \(B_j\)经过的边权之积的和。

统计不相交路径，则 \(w(u, v) = 1\),边权是 1。

构造 \(|A| \times |B|\) 的矩阵 \(M\)，第 \(i\) 行第 \(j\) 列的数是 \(e(A_i, B_j)\)。

那么不相交路径数即是 \(\text{det}(M) = \sum_{p} \text{sgn}(p)\prod_{i}^{|A|}e(i,p_i)\)。

其中 \(\text{sgn}(p)\) 表示有偶数个逆序对时为 \(1\), 否则为 \(-1\)。

2-sat 问题

• 定义：给定条件 \(a = 0/1\) 或/和 \(b = 0 /1\)，求出满足一组条件的解。

实际上一组条件可以看成 一个强制关系。

例如: \(a = 1\) 或 \(b = 1\), 如果 \(a = 0\), 那么一定的 \(b = 1\)。

对于一个点可以有 真假 两种状态，对于一组关系就连一条有向边,
求解强连通分量，存在 一组变量真假状态都在同一强连通分量说明无解。

• 关于强连通分量时标的号是拓扑逆序。

  是因为存在环(强连通分量)的话，整个环里的点标的号相同，考虑把所有的环缩成点，那么剩下的就是几个有向无环图。

  首先，几个不相连的有向无环图的拓扑序之间可以随意排列穿插，虽然但是，这里把同一个有向无环图的拓扑序看成连续一段。

  那么考虑一个有向无环图，拓扑序是从入度为0的点向出度为0的点顺序标号；而 tarjan 的过程是则是反过来标号，无论访问顺序如何，标号总是拓扑序逆序。

• 关于解中变量的选择。

  在拓扑序中，对于一个变量的两种状态:

  • 如果不在同一个有向无环图上，那么就取最拓扑序最晚的那个状态，因为这样保证了同一个有向无环图的任意一点的拓扑序比其他的图的所有点的拓扑序要晚，所只要按照强制关系选就没有问题。

  • 在同一个有向无环图，不在同一个依赖链上那么就选大的，在的话，只能取拓扑序大的，拓扑序大的被依赖了。

二分图

参考：
rqy的blog
oi-wiki

• 定义：一张图的点集可以分为左部和右部，所有边的两端属于的部分不同。
• 判定
  • 小性质：二分图不存在奇环，必须走偶数条边才能回到当前的部
    。实际上，不存在奇环的图都是二分图。
  • 由于一条边两端的点所属部不同，直接dfs染色，如果遇到两端同色，就不是二分图。其实，这就是遇到了奇环。

二分图最大匹配

• 匈牙利算法：
  不断找增光路，找到一条就把匹配边取反。时间复杂度 \(O(n^2)\)。
• 网络流建模：将源点 \(s\) 连 \(1\) 的流量的边到左部, 左部右部之间有边的连 \(1\) 流量的边，再将右部的点连向汇点 \(t\)，最后所求最大流就是最大匹配数，时间复杂度 \(O(n\sqrt{e})\)。

Konig 定理

• 二分图最大匹配 = 二分图最小点覆盖

最小点覆盖就是一个最小的点集使所有边的两端的点至少有一个在这个集合里。

• 利用最大流最小割定理(在文章后面)的证明：

  1.像上方最大匹配的建模，只不过左部和右部连的边的流量是无穷大。

  2.得到割集 \((S, T)\), S，T中的点可能来自两部。

  3.由于割边不可能是无穷大的边，\(S\) 在右部的点和 \(T\) 在左部的点一定至少连了一条边(不然就不会割它了)， 恰好这些点的个数就是最小割的大小，而最小割等于最大流等于最大匹配数。

二分图最大独立集

最小点覆盖数最大独立集互为补集，就有：

• 最大独立集 = n - 最小点覆盖

二分图最大团

团:其中任意两点都有边

• 二分图最大团 = 补图最大独立集

最大独立集点两两不相邻，补图最大独立集在原图两点相邻。

DAG 最小不可相交路径覆盖

• 最小不可相交路径覆盖 = n - 最大匹配数

• 匹配一次，路径就减少一条，就是要最大化匹配数。

DAG 最小可相交路径覆盖

不可相交路径覆盖本质上是维护一条简单路径，初始时是 \((u, u)\), 通过与相邻的边匹配，最后得到不相交的路径。

可相交就代表不一定要相邻的边匹配，所以直接求出传递闭包，能到的点都可以匹配。

于是先求出传递闭包在跑最小不可相交路径覆盖。

hall定理

hall定理

• 定义：判断二分图是否存在完美匹配。

• 内容：

  1. 两部大小相同， \(|L| = |R|\)。
  2. 对于任意 \(S \subseteq |L|\)，\(S\) 能通过边到达的右部的点集 \(T\)， 都存在\(|S| \leq |T|\)。

网络流

参考:
oi-wiki

概念：

1. 网络：有向图。
2. 特殊点：源点 \(s\)，汇点 \(t\)。
   3. 容量(\(c(u, v)\))：两点的边权，经过该边的流量不超过它的容量。
   4. 流量(\(f(u, v)\))：该边的流量。剩余容量：每条边剩余的容量之和。
3. 割，去掉割集后使得流入汇点流量为0。

基本性质：

1. 容量限制：\(f(u,v) \leq c(u, v)\)。
2. 对称：\(f(u, v) = - f(v, u)\)。
3. 守恒：源点流出的流量 = 流入汇点的流量。

最大流最小割定理

• 最大流 = 最小割

口胡:

1. 最大流 \(\leq\) 最小割，因为割掉这些边的流量之和一定是0，也就是说最小割是最大流的上界。
2. 最大流 \(=\) 最小割，如果这些边集的流量不是满的，那么一定被其它的边的容量限制，割去那些边一定不劣于割去这些流量不满的边，最后的割掉的边一定是满流的边。

平面图最小割：

转化为对偶图跑最短路。

对偶图的点是原图的边分割的不相交区域，两个相邻的区域之间有一条边，边权就是这条边的容量，跑最短路就会选择一条路径把平面分割成两个区域。

全局最小割 Stoer_Wagner

• \(O(n^3)\) 求无向图的全局最小割。

不会证明。

• 大致流程

1. 找出当前最小割，阶段割。

   • 维护一个集合 \(A\), 在未加入的点中找到与集合 \(A\) 中的点相连的边的边权最大的那个加入。
   • 最后两个加入的点是源点和汇点，倒数第一个是源点，倒数第二个是汇点，最小割是 \(w_t\)。

2. 将源点和汇点合并，边权合并。

最小割树

• 时间复杂度建出 \(O(n^3m)\)， 查询 \(O(\log n)\)。

• 大致流程：

建树：

1. 求出当前点集 \(V\) 的割集 \((S, T)\)(利用残量网络)。

2. 向 \(s\) 到 \(t\) 连边为 最小割的边。

3. 分治，分别将 \(S, T\) 作为 \(V\), 回到第一步。

查询：

两点最小割就是树上两点路径上的最小边权。

上下界网络流

参考:

算法学习笔记(60): 上下界网络流 zhihu

oi-wiki

• 本质：每条边的流量有限制 \([l, r]\), 并且任意点的流量平衡。

无汇源上下界可行流

• 做法：

  • 做出差网络，每条边的容量为 \(r_e - l_e\)，但是这样网络的流与下界 \(l\) 相加后在原来的网络上可能流量不守恒。

  • 新建源汇点，如果某点入流量 > 出流量，在差网络通过源点流入流量相差的流量，这样出流量就会变多，以至于相等。

  • 反之，就是向汇点流入相差的流量。

  • 以上连的边记做附加边，跑最大流，如果存在附加边不满流，那么说明平衡条件不满足，不存在可行流。

有汇源上下界可行流

• 对于原来的汇点和源点连一条 \([0, \infty )\) 的边，就变回无汇源上下界可行流。

• 最后可行流总流量就在 \(t\) 到 \(s\) 这条附加边上。

有汇源上下界最大流

• 求出有汇源上下界可行流，此时，若有解，那么附加边的流量已经满了，可以直接删去，在残量网络里跑一遍从源点到汇点的最大流，两次流量相加即可。

有源汇上下界最小流

• 同有汇源的上下界最大流的建图，只是最后从汇点到源点跑最大流，相当于退回流量，两次流量相减。

网络流模型：

• 最大权闭合子图

  显著特点是: 有向图， 有依赖关系的选择，点有点权，有正负。
  首先有一张有向图，一条边 \((u, v)\) 表示选择 \(u\) 必选 \(v\)。

  建模：源点 \(s\) 连向正点权的点，流量就是点权，连原图的边但流量是正无穷，负点权的点连向汇点 \(t\), 流量是边权的绝对值。

  最大权 = 正点权和 - 最小割。

  因为无穷边割不掉，要么割正点，要么割负点。割正点代表不选这个点，割负点代表一定得选。

欧拉图：

前提：连通图。

欧拉回路路径的判断

1. 有向图的欧拉路径，只存在一点出度比入度大1(起点)，只存在一点入度比出度大 1(终点)。

2. 有向图的欧拉回路，所有点的出度等于入度。

3. 无向图的欧拉路径，恰好两个点的度数是奇数，剩下的都是偶数。

4. 无向图的欧拉回路，所有点度数都是偶数。

Best 定理

• 用处：统计有向图欧拉路径数量的最好的定理。

\[ec(G) = t^{root}(G)\prod_{u} (\text{deg}(u) - 1)! \]

其中：\(t^{root}(G)\) 是 \(G\) 的内向生成树的个数。

• 如果指定根，那么 $ec(G, root) = ec(G) \times \text{deg}(root) $,因为指定根可以挑 \(\text{deg}{root}\) 处断开回路，这好比是环和链的关系。