图论基础
绝顶我为峰
2021-06-18 20:51:45
# 图论基础
## 1.度数序列
有一无向图 $G=(V,E)$，$d_1,d_2,\dots,d_n$ 表示每个点的度数，显然有 $\sum_{i=1}^nd_i=2e$，度数是奇数的点一定有偶数个。
现在给出一组度数，请判断是否能生成一个合法的简单无向图。
感觉很像贪心，怎么贪呢？度数从大往小连？
事实上这样确实是对的，因为我们感性理解一下我们要尽量满足度数多的点的需求，那么我们就从大往小连即可。连的时候应当调剩余度数的点来连边。
这玩意如果暴力跑是 $O(n^2\log n)$ 的，但我们发现我们砍掉一条边的点排序后一定是个后缀，那么两部分分别是有序的，所以可以每连一条边归并一次。这样砍掉了一个 $\log$ 变成 $O(n^2)$。
但这样似乎还是不够快……可不可以不模拟建图的过程？答案是肯定的。
**$Erdos-Gallai$ 定理：一个单调不降序列可简单图化当且仅当 $\sum_{i=1}^nd_i\equiv0(mod\ 2)$ 且 $\sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$。**
于是复杂度就愉快的成了 $O(n)$。
## 2.图的遍历
众所周知，遍历图后会产生三种边：树边、返祖边和横叉边。但 dfs 比较特殊，它只会产生树边和返祖边，没有横叉边。感性理解 dfs 会把一条路一直跑到头，那么对于每个环最后一非树边都是联想祖先的。这个性质会带来很多好处。
例题1：[Cycling City](https://www.luogu.com.cn/problem/CF521E)
有三条路径等价于两个环有公共边，也就是 dfs 树上一条边可以与两条非树边组成两个不同的环，直接用非树边覆盖树边，如果有覆盖两次的就有解，直接树上差分即可。
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct edge
{
int nxt,to;
}e[200001<<1];
bool vis[200001];
vector<int> g[200001],ans;
vector<pair<int,int> > nt;
int n,m,dep[200001],d[200001],tot,h[200001],fa[200001][21];
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline void add(int x,int y)
{
e[++tot].nxt=h[x];
h[x]=tot;
e[tot].to=y;
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y])
x^=y^=x^=y;
for(register int d=dep[x]-dep[y],i=0;1<<i<=d;++i)
if(d&(1<<i))
x=fa[x][i];
if(x==y)
return x;
for(register int i=20;~i;--i)
if(fa[x][i]^fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
}
inline void solve(int x,int y)
{
puts("YES");
int cnt=0,u[3]={0},v[3]={0};
bool tag=0;
for(register int i=0;i<(int)nt.size();++i)
{
u[0]=nt[i].first,v[0]=nt[i].second;
if(dep[u[0]]>dep[v[0]])
u[0]^=v[0]^=u[0]^=v[0];
if(lca(x,u[0])==u[0]&&lca(y,v[0])==y)
{
++cnt;
u[cnt]=u[0];
v[cnt]=v[0];
}
if(cnt==2)
break;
}
if(dep[u[1]]>dep[u[2]])
{
u[1]^=u[2]^=u[1]^=u[2];
tag^=1;
}
if(dep[v[1]]>dep[v[2]])
{
v[1]^=v[2]^=v[1]^=v[2];
tag^=1;
}
int LCA=lca(v[1],v[2]),node=LCA;
ans.clear();
ans.push_back(node);
while(node!=u[2])
{
node=fa[node][0];
ans.push_back(node);
}
reverse(ans.begin(),ans.end());
printf("%d ",(int)ans.size());
for(register int i=0;i<(int)ans.size();++i)
printf("%d ",ans[i]);
puts("");
ans.clear();
ans.push_back(u[2]);
node=u[2];
while(node!=u[1])
{
node=fa[node][0];
ans.push_back(node);
}
node=v[1+tag];
ans.push_back(node);
while(node!=LCA)
{
node=fa[node][0];
ans.push_back(node);
}
printf("%d ",(int)ans.size());
for(register int i=0;i<(int)ans.size();++i)
printf("%d ",ans[i]);
puts("");
ans.clear();
ans.push_back(u[2]);
node=v[2-tag];
ans.push_back(node);
while(node!=LCA)
{
node=fa[node][0];
ans.push_back(node);
}
printf("%d ",(int)ans.size());
for(register int i=0;i<(int)ans.size();++i)
printf("%d ",ans[i]);
puts("");
}
void dfs1(int k,int f,int deep)
{
dep[k]=deep;
vis[k]=1;
fa[k][0]=f;
for(register int i=1;i<=20;++i)
fa[k][i]=fa[fa[k][i-1]][i-1];
for(register int i=h[k];i;i=e[i].nxt)
{
if(e[i].to==f)
continue;
if(vis[e[i].to])
{
++d[k];
--d[e[i].to];
nt.push_back(make_pair(k,e[i].to));
}
else
if(!dep[e[i].to])
{
g[k].push_back(e[i].to);
dfs1(e[i].to,k,deep+1);
}
}
vis[k]=0;
}
void dfs2(int k,int f)
{
for(register int i=0;i<(int)g[k].size();++i)
{
dfs2(g[k][i],k);
d[k]+=d[g[k][i]];
}
if(d[k]>=2)
{
solve(f,k);
exit(0);
}
}
int main()
{
n=read(),m=read();
for(register int i=1;i<=m;++i)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
for(register int i=1;i<=n;++i)
if(!dep[i])
{
nt.clear();
dfs1(i,0,1);
dfs2(i,0);
}
puts("NO");
return 0;
}
```
例题2：$n$ 个点 $m$ 条边的有向图，问图中是否存在长度为奇数/偶数的有向环。
先解决比较简单的奇环：二分图判定，如果不是二分图就肯定有奇环，否则没有。
然后是麻烦一些的偶环：dfs 树上对于每条返祖边判断两边深度差，如果是奇数那么有偶环。如果没有，那么只含一条非树边的环全是奇环。这时我们发现如果两个奇环相交一定出现偶环，判断是否有环相交即可。
## 3.欧拉回路
### 定义
欧拉回路指覆盖所有边的路径。
无向图存在欧拉回路的充要条件是所有点度数为偶数且联通（存在某联通块大小为 1 时忽略这个点）。
有向图存在欧拉回路的充要条件是所有点入度等于出度且联通（存在某弱联通块大小为 1 时忽略这个点）。
推广一下，如果无向图里面有 $2k$ 个度数是奇数的点，那么需要 $k$ 条路径覆盖所有边。
这很好理解，把奇数点配对，在之间连 $k$ 条“虚边”，显然虚边不共用顶点，而这时所有点度数都变成了偶数，存在一条欧拉回路。然后我们让这条回路第一条边是一个虚边，把这条路径中所有虚边断掉，就得到 $k$ 条路径。
### 求解
怎样求欧拉回路？
随便跑！
这样复杂度是 $O(\sum d_i^2)$，如果某个点度数好大就挂了，不够优秀。我们需要优化。
于是一个玄学的做法横空出世！我们还是在这张图上乱跑 dfs，每条边只走一回，但是当我们来到一个点后发现没有边可以走了，我们回溯的时候直接把这条边插入到欧拉回路的队尾，这样可以在线性时间内得到一个欧拉回路。
~~这样为啥是对的？我也不知道。~~
例题：平面上 $n$ 个点，黑白染色使得每行每列黑白点数量最多相差 $1$。
把每个点看所行向列连边，我们假定每行每列偶数个点，那么只能黑白相等，等价于一个点的入度等于出度，直接跑欧拉回路即可。
如果有奇数个点的行或列，易得一定有偶数个，那么按照上面的套路在奇数点之间连虚边然后跑欧拉回路，把虚边再删掉即可。
## 4.生成树
### 最小生成树
#### $Kruskal$ 算法
略。
#### $Prim$ 算法
略。
#### $Boruvka$ 算法
好像没听说过？
这个算法实现起来比较奇妙，初始时每个点是一个连通分量，然后每一次找到与每个连通分量相连的权值最小的边，然后加上这些边后合并连通分量。因为每进行一轮连通分量个数至少会减半，所以复杂度 $O(e\log v)$。
这个算法可以搞一些奇怪的题目。
例题：$n$ 个点的无向完全图，其中 $i,j$ 之间的边权值为 $(a_i+a_j)\ mod\ m$，求最小生成树。 $n\leq 1e5$。
Kruskal 和 Prim 似乎都不好做，我们试试这个 Boruvka 算法。
由于联通块与外部相连的边权最小的边等价于每个点向外连的边权最小的边取 $\min$，所以只考虑怎样找每个点的权值最小边即可。
不难发现对于一个点 $i$，只有两种 $j$ 可能成为最小值：第一种是点权最小的 $j$，第二种是点权大于等于 $m-a_i$ 中最小的那个。第一种可以直接取，第二种二分即可。
于是思路变得清晰：用 multiset 维护点权，每个联通块找边时先把联通块内部的点删去，然后按照上面的方法找最小边权，然后跑 Boruvka 即可。
### 生成树计数
#### $Prufer$ 序列
树生成序列：对于一棵树，每一次删掉叶子中编号最小的那个，然后把与这个这个节点相连的那个节点加入 $Prufer$ 序列末尾，然后删去这个叶子和这条边。重复上述过程直到只剩两个点。显然一棵树的 $Prufer$ 序列唯一，长度为 $n-2$。
序列生成树：找到序列中先前没有用过且没有在序列中出现的最小的数，把它和序列中第一个数连边，然后把第一个数从序列里删去，把没出现的那个数标记为用过。重复操作直到序列为空，这时会有两个点还没用过，把它们连起来。不难发现每个 $Prufer$ 序列对应的树唯一。
因为每个 $Prufer$ 序列都对应一棵树，所以 $n$ 个点不同的生成树有 $n^{n-2}$ 个。这个东西叫做 $Cayley$ 定理。
同时，不难发现点 $i$ 会在 $Prufer$ 序列里面出现 $d_i-1$ 次。因为每一删掉一个和 $i$ 有关的点都会让 $i$ 进入序列，到了只剩一条边的时候就这条边一定不会删，要么 $i$ 最后被删了，要么这个点是最后两个点，反正一定不会再出现在序列中。于是给定每个点度数，不同的生成树共有 $\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}$ 个，相当于由 $d_i-1$ 个 $i$ 组成的不同的序列的个数。
还有一个有趣的东西： $n$ 棵树，内部结构给定，第 $i$ 个大小为 $a_i$，那么这 $n$ 棵树可以产生的生成树个数是 $(\sum_{i=1}^na_i)^{n-2}\prod_{i=1}^na_i$。
为什么呢？我们先考虑把每棵树缩成点，那么在 $i$ 和 $j$ 之间连一条边就有 $a_ia_j$ 种方案，然后再将每条边的的贡献相乘。那么如果第 $i$ 棵树上连了 $d_i$ 条边，那么他对答案贡献是 $a_i^{d_i}$。
令一个 $Prufer$ 序列 $p$ 的权值是 $\prod_{i=1}^na_i$，根据上面的结论，每个点会在 $Prufer$ 序列中出现 $d_i-1$ 次，因此每个 $a_i$ 都少乘了一次，补上就得到了上面的式子。
#### 矩阵树定理
**给一个无向有权图，记 $D$ 是每个点连边权值和 $d_i$ 的对角矩阵（其中对角线位置是和 $i$ 相连的边权值和，非对角线位置填 $0$），$A$ 是这张图的邻接矩阵，$G=D-A$，然后删掉 $G$ 的任意一行一列（一般删第一行和第一列或最后一行和最后一列） $G'$，$G'$ 的行列式就是生成树的权值（生成树中所有边边权的乘积）。**
特别地，如果认为每条边边权都是 1，那么结果就是生成树个数。
这玩意可以推广到有向图的树形图计数，对于外向树，把 $D$ 中对角线上的值改成入边权值和，内向树改成出边权值和，删去第 $i$ 行和第 $i$ 列的行列式是从 $i$ 出发的树形图个数。
例题：[【模板】Matrix-Tree 定理](https://www.luogu.com.cn/problem/P6178)
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int mod=1000000007;
int n,m,t,d[301][301],a[301][301],g[301][301];
inline int pw(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
inline int solve()
{
bool tag=0;
int ans=1;
for(register int i=2;i<=n;++i)
{
for(register int j=i;j<=n;++j)
if(!g[i][i]&&g[j][i])
{
swap(g[j],g[i]);
tag^=1;
break;
}
ans=ans*g[i][i]%mod;
int d=pw(g[i][i],mod-2);
for(register int j=i;j<=n;++j)
g[i][j]=g[i][j]*d%mod;
for(register int j=i+1;j<=n;++j)
{
int d=g[j][i];
for(register int k=i;k<=n;++k)
g[j][k]=(g[j][k]-g[i][k]*d%mod+mod)%mod;
}
}
return tag? (mod-ans%mod)%mod:(ans%mod);
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&t);
for(register int i=1;i<=m;++i)
{
int x,y,w;
scanf("%lld%lld%lld",&x,&y,&w);
if(t)
{
d[y][y]=(d[y][y]+w)%mod;
a[x][y]=(a[x][y]+w)%mod;
}
else
{
d[x][x]=(d[x][x]+w)%mod;
d[y][y]=(d[y][y]+w)%mod;
a[x][y]=(a[x][y]+w)%mod;
a[y][x]=(a[y][x]+w)%mod;
}
}
for(register int i=1;i<=n;++i)
for(register int j=1;j<=n;++j)
g[i][j]=(d[i][j]-a[i][j]+mod)%mod;
printf("%lld\n",solve());
return 0;
}
```
## 5.二分图匹配
### 最大匹配
匈牙利/dinic，比较简单就不说了。
### 最大权匹配
KM/费用流，也比较简单。
### $Hall$ 定理
**对于一个二分图 $G=(X,Y,E),S(G)\subseteq X$，记 $N(S)$ 为所有与 $S(G)$ 相连的点的并集，那么当且仅当 $\forall S(G)\subseteq X,|S(G)|\leq|N(S)|$ 时存在完美匹配。**
推论：每个正则二分图都有完美匹配。
很好证明，因为如果不满足 $Hall$ 定理必然有点的度数和其他点不同。
例题：$n$ 个点的二分图，求一个边权最小的边集，使得删掉这个边集后没有完美匹配。$n\leq 20$
这题非常水，就直接枚举 $S(G)$，然后贪心的计算割掉右边一个点需要多少权值，暴力算就好了。
### $Konig$ 定理
最小点覆盖=最大匹配（相当于二分图跑网络流最大流=最小割）
最大独立集=点数-最大匹配
最小边覆盖=最大独立集
## 6.$DAG$ 上问题
### 拓扑排序
真的有人不会吗？
### 字典序拓扑排序
求一个 $DAG$ 字典序最小/大的拓扑序。
难道不是队列改成堆？
修改一下：要让 $1$ 的位置尽可能靠前，然后 $2$ 的位置尽可能靠前……这样怎么做？
正着做好像不行了……正难则反？
我们发现反过来之后要求 $1$ 最晚出现。这就很简单了，我们对反图进行拓扑排序强制不弹出 $1$，直到队列中只剩 $1$ 即可。
对于其他点全都这么跑一遍。
例题：[[NOI2010] 航空管制](https://www.luogu.com.cn/problem/P1954)
就跟上面一样，建反图，两架飞机之间的限制就反向连边，时间限制从 $c_i$ 前变成了 $n-c_i$ 后，这样就简单了，飞了 $n-c_i$ 之后把飞机加进堆即可。
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct edge
{
int nxt,to;
}e[10001];
int n,m,tot,a[2001],h[2001],D[2001],d[2001];
vector<int> v;
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
inline void add(int x,int y)
{
e[++tot].nxt=h[x];
h[x]=tot;
e[tot].to=y;
}
inline void topo(int s)
{
int cnt=0;
queue<int> q;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > t;
for(register int i=1;i<=n;++i)
if(!d[i]&&i!=s)
if(!a[i])
q.push(i);
else
t.push(make_pair(a[i],i));
while(!q.empty())
{
int k=q.front();
if(!s)
v.push_back(k);
q.pop();
++cnt;
for(register int i=h[k];i;i=e[i].nxt)
if(!--d[e[i].to]&&e[i].to!=s)
t.push(make_pair(a[e[i].to],e[i].to));
while(!t.empty()&&t.top().first<=cnt)
{
q.push(t.top().second);
t.pop();
}
}
if(s)
printf("%d ",n-cnt);
else
{
while(!v.empty())
{
printf("%d ",v.back());
v.pop_back();
}
puts("");
}
}
int main()
{
n=read(),m=read();
for(register int i=1;i<=n;++i)
a[i]=n-read();
for(register int i=1;i<=m;++i)
{
int x=read(),y=read();
++D[x];
add(y,x);
}
for(register int i=1;i<=n;++i)
d[i]=D[i];
topo(0);
for(register int i=1;i<=n;++i)
{
for(register int i=1;i<=n;++i)
d[i]=D[i];
topo(i);
}
puts("");
return 0;
}
```
### 最小链覆盖
链不能相交。
覆盖边：每条边流量下界设为 1 跑最小流。
覆盖点：拆点，每条边 $(u,v)$ 连边 $(u,v')$，答案是点数-最大匹配。
**$Dilworth$ 定理：最大反链=最小链覆盖。**
## 7.连通分量
### $Tarjan$ 算法
真的有人不会？
### 双连通分量
点联通度：最小的点集使得删去这个点集后图不连通。
边连通度：最小的边集使得删去这个边集后图不连通。
如果点联通度大于 1，那么称图点双联通，边双同理。
双连通分量是图中的极大双联通子图。
割点：删去割点后图不连通。
割边（桥）：删去桥之后图不连通。
桥的求法是跑 dfs 树，然后用非树边覆盖树边，最后没有被覆盖的全都是桥。
割点求法相当于删掉与某个点相连的所有边，那么先按照割边做，然后对于每个点，把与他相连的非树边的 tag 删掉，如果剩下的与当前点相连的树边中有没被覆盖的就是割点。
~~然而平时常用的方法求割边割点好像还是 tarjan~~
### $2-SAT$ 问题
这类问题给出若干个类似于“ $a,b$ 中至少一个为真”这样的条件，求是否有一种布尔变量的取值使所有限制都被满足。
把一个变量拆成两个点，分别代表变量取真或假。然后对于每个限制连边，如 $a,b$ 中至少一个为真，那么从 $\lnot a$ 到 $b$,$\lnot b$ 到 $a$ 连有向边。这是符合逻辑的，易得。
然后跑 tarjan，显然一个强联通分量内部要么都选要么都不选，那么当且仅当 $a$ 和 $\not a$ 在一个强联通分量时无解，否则有解。
## 8.最短路
### 最短路算法
略。
### 最短路径树
有向图中从一个点出发，到达所有点的边构成一棵树，这棵树的权值最小。
### 差分约束
显然根据最短路有不等式 $dis_v\leq dis_u+w(u,v)$，那么我们拿到一些类似这样的不等式时，可以类比最短路建图。
### 正权图
偏心距：$\mathrm{ecc}(u)=\max\{dis(u,v)\}$
直径：$d=\max\ \mathrm{ecc}(u)$
半径 $r=\min\ \mathrm{ecc}(u)$
中心：半径取到的那个点。
绝对中心：可以在边上。
前面四个东西都很好求，我们看看绝对中心的求法。
考虑一条边 $(u,v)$ 上一点 $p$，有第三点 $w$，那么折线长度是 $\min(dis(p,u)+dis(u,w),dis(u,v)-dis(p,u)+dis(v,w))$。
于是偏心距的最大值是 $n$ 条折线形成的最大值的折线。
排序维护即可。