NOI 知识一览-2. 图论

· · 个人记录

2. 图论

本文所讨论的图一般为简单图，且一般认为 m=|E|\ge |V|=n。

2.1(a) 二分图

A. 二分图的概念与判定

联赛内容，懒得写了。

B. 匈牙利算法

用于求解二分图最大匹配问题。

对于图 G 的一组匹配，定义增广路为一条满足其起讫点均未被匹配且匹配边与未匹配边在路径上交替出现的简单路。

匈牙利算法基于的一个重要结论是：

注意到若存在一条增广路，则容易构造一个更大的匹配。由此只需证明若当前匹配非最大，则一定存在增广路。

考虑找到当前匹配与最大匹配的边集的对称差，图中每个点度数不超过 2，因此每个连通块要么是环要么是链，容易证明一定存在一条链是增广路。

实现时，我们只需依次从每个点出发尝试搜出一条增广路。由于已经被选入匹配中的点不会再被移出匹配，因此可以基于贪心证明其正确性，时间复杂度 \mathcal O(nm)。

vector<int> g[N]; bool vis[N];
bool dfs(int x) {
    if(vis[x]) return false;
    vis[x] = true;
    for(int y : g[x]) if(a[y] == 0 || dfs(a[y]))
        return a[y] = x, true;
    return false;
}

for(int i = 1; i <= n; i++) cl(vis, 0), dfs(i);

事实上，可以证明若将匹配的左部点记为 1，未匹配的左部点记为 0，则按照枚举顺序拼接左部点的匹配情况，匈牙利算法求出的最大匹配是字典序最大的。

C. KM 算法

用于求解二分图最大权完美匹配问题。

相关问题：

最大权匹配可以简单转化到此问题，有负权的情况也是平凡的。

最大权最大匹配还是直接流吧。

一个相对高等的视角是考虑用线性规划表达之：

\begin{aligned} &\max \sum w_ix_i \\ &s.t. \begin{cases}\forall k\in V, \sum_{i\in E} b_{k,i}x_i\le 1 \\ x_i\ge 0 \end{cases} \end{aligned}

其中 b_{k,i} 当且仅当 i 这条边有一个端点为 k 时为 1，否则为 0。其对偶为：

\begin{aligned} &\min \sum y_i \\ &s.t. \begin{cases}\forall i\in E, \sum_{k\in V} b_{k,i}y_k\ge w_i \\ y_i\ge 0 \end{cases} \end{aligned}

也就是说我们需要给每个点赋值一个顶标 a_i，对于每条边 (u,v,w) 需要满足 a_u+a_v\ge w_i，最小化 \sum a_i 的值。

我们不考虑直接求出 \sum a_i，而是对于一组顶标，记录其对应的相等子图包含所有满足 a_u+a_v= w_i 的边。容易证明若相等子图中存在完美匹配则这就是最大权完美匹配，这样只需求出这样的一组顶标即可解决原问题。

考虑沿用匈牙利算法的思路，每次从一个点 rt 出发寻找增广路：

int pre[N]; bool vis[N]; ll sl[N];
void KM() {
    fo(i, 1, n) {
        A[i] = B[i] = 0;
        fo(j, 1, n) A[i] = max(A[i], w[i][j]);
    }
    fo(rt, 1, n) {
        int x = rt, cur = 0; match[0] = x;
        cl(vis, 0), cl(sl, 0x3f), cl(pre, 0);
        fo(rd, 1, n) {
            int p = -1; ll V = INF;
            fo(i, 1, n) if(!vis[i]) {
                ll val = A[x] + B[i] - w[x][i];
                if(val < sl[i]) sl[i] = val, pre[i] = cur;
                if(sl[i] < V) V = sl[i], p = i;
            }
            A[rt] -= V;
            fo(i, 1, n) {
                if(vis[i]) B[i] += V, A[match[i]] -= V;
                else sl[i] -= V;
            }
            vis[p] = true, x = match[p], cur = p;
            if(x == 0) break;
        }
        while(cur)
            match[cur] = match[pre[cur]], cur = pre[cur];
    }
}

D. Hall 定理

E. 二分图常用结论

2.1(b) 网络流算法

A. 最大流

B. 最小割

可行边与必须边

在找到任意一组最大流方案后，可以得到两个经典结论：

容易证明只有满流边才可能被割去。

证明上述结论可以转用最大流视角考虑，前者等价于该边流量减小 1 后全图最大流减小 1，后者等价于流量增大 1 后最大流增大 1。

这样，二者的条件都是显然的。

特化到二分图匹配问题后，有如下结论：

C. 费用流

D. 上下界网络流

E. 最小割树

最小割树的概念

最小割树旨在解决如下问题：

给定一张无向连通图 G，求任意两点间最小割。

此算法（称为 Gomory-Hu 算法）可以给出一棵带边权的树 T，使得原图中 u,v 间的最小割就是 T 中两点间路径上边权的最小值。

进一步地，此树可以保证对于 u,v ，在将其路径上边权最小的边删去后，树上两个连通块构成了一组最小割的方案（这里“方案”采用的是划分点集的视角）。

推理性质

下记 L(u,v) 为 u,v 间最小割的大小。

证明可以考虑转为最大流然后讨论。

立刻得到：

证明可以考虑取最小值边 (s,t)，由引理 L(u,v)\ge L(s,t)，而取 (s,t)-最小割即可构造证明 L(u,v)\le L(s,t)。

现在我们只需要构造一棵树使得上面的条件被满足。事实上我们可以证明：

证明可以考虑分类调整。以下我们记 \delta(P)=(P,\overline{P}) 为一组割，一些地方会混用此记号表示此割的大小。

不妨设 u\in S，若 t\not\in T，那么我们取 \delta(S\cap T) 就是一组 (u,v) 割，可以证明其等于 \delta(T)。

  • 这是因为 \delta(S)+\delta(T)\ge \delta(S\cup T)+\delta(S\cap T)，其分别是 (s,t) 和 (u,v) 的两组割。由定义两组最小割的大小对应相等。

若 t\in T，构造 \delta(S\backslash T) 即可，详细证明不再展开。

Gomory-Hu 算法

因此，我们可以每次随机选择图上的两个点，用 Dinic 跑出二者间最小割的一个方案 (S,S')。

然后把图 G 划分为两个部分 G_1,G_2，具体地我们把 G_1 中的 S' 缩成一个点，对 G_2 中的 S 同理。

每次递归时记录当前图对应原图上的哪些点，当此点集大小为 1 时返回（注意可能有缩点搞出来的虚点），否则递归下去。

然后我们添加一条边把两边的树连上，再把新加进去的两个虚点从划分的方案中删掉，返回即可。

可以归纳证明此算法的正确性：只需证明新加的那条边合法即可。

细节不再展开，因为场上我们大概率不会直接实现此算法。

容易证明，对于任意图，Gomory-Hu 算法会运行恰好 n-1 次求最小割，因此配合 Dinic，其总复杂度是 \mathcal O(n^3m) 的。

近年来有一些算法可以对此问题做到 \mathcal O(n^2) 的复杂度，十分逆天。

Gusfield 算法

Gusfield 算法较于 Gomory-Hu 算法简单许多。

它不需要利用缩点 / 划分等一系列复杂的操作，只需要在每次跑出 u,v 的最小割后在二者间连边即可。

不过代价是其只能求出等价流树，无法构造方案。

vector<pair<int, int> > g[N]; bool vis[N];
set<int> MinCut(int u, int v) {
    memcpy(edge, Edge, sizeof(edge));
    int fl = 0; S = u, T = v;
    while(bfs()) fl += dinic(S, INF);
    set<int> res; queue<int> Q;
    Q.push(u), cl(vis, 0), vis[u] = true;
    while(Q.size()) {
        int x = Q.front(); Q.pop();
        for(int i = head[x]; i; i = Next[i]) {
            int y = ver[i];
            if(edge[i] && !vis[y]) vis[y] = true, Q.push(y);
        }
    }
    g[u].push_back(make_pair(v, fl)), g[v].push_back(make_pair(u, fl));
    fo(i, 0, n) if(vis[i]) res.insert(i);
    return res;
}
void build(vector<int> vec) {
    if(vec.size() == 1) return ;
    int u = vec[0], v = vec[1];
    auto now = MinCut(u, v); vector<int> L, R;
    for(int x : vec) {
        if(now.find(x) == now.end()) R.push_back(x);
        else L.push_back(x);
    }
    build(L), build(R);
}

Record.

F. 全局最小割

2.2 图论建模

咕咕咕。

2.3 图论杂项

A. Menger 定理

它是最大流 - 最小割定理的特例。

利用 Menger 定理可以对 n\ge 3 的点双进行推理得到一些常用推论：

它们可以用于推理图性质从而计数。注意点双的性质比边双强，一般优先从点双下手。

B. 欧拉图

判定

在上述命题的证明中，必要性是显然的，充分性的构造可以考虑通过不断地寻找图中的环并将他们相连接得到。

构造

一般采用 Hierholzer 算法。

其核心是不断往当前回路的某个点中递归地插入环，这体现在 DFS 过程的实现中等价于在回溯的同时找别的环，也即一路 DFS 下去，然后倒序加入搜过的边。

可以证明上述算法的正确性，一个详细解释可以见 AlexWei 的博客。

事实上，只要保证搜索的起点和访问边的顺序，这种求法求出的路径满足字典序最小，因为每个点的后继都取到了理论最小值。

void dfs(int x) {
    for (int y = 1; y <= n; y++)
        if (g[x][y] >= 1) {
            g[x][y]--, g[y][x]--;
            dfs(y);
        }
    ans[++cnt] = x;
}

dfs(1), reverse(ans + 1, ans + cnt + 1);

混合图的构造需要利用网络流确定出入度。

计数

有向欧拉图的欧拉回路是可以计数的，这称为 BEST 定理。

对于任意有向欧拉图 G，容易证明可以取出其一棵以 1 为根的内向生成树 T。

对于每个点 x，我们再把 x 的所有非树边的出边随意确定一个顺序（特别地，1 号点的所有出边中编号最小的应当排在首位）。之后我们考虑使用这些枚举的信息构造一条欧拉回路。

具体地，我们从 1 号点出发，按照出边的顺序依次选择当前点的一条没走过的非树边走，如果所有非树边都走过就走树边。

由于每个点出入度相同，这样走一定不会卡在某个点走不了了，也就是说一定可以走会到 1。若这条路径不是欧拉回路，唯一可能是走完以后还存在一个不包含 1 的弱连通块有边未被走过。取出这个弱连通块中在树中深度最小的点 u，由于 u 此时出入度相等且不为 0，那么它的树边一定还在（否则就是之前在还有非树边的情况下走了一条树边），矛盾。因此这样构造出的路径一定是欧拉回路。

现在再证明每条欧拉回路唯一对应一种枚举方案：我们取出 1 号点的所有出边中编号最小的边，钦定它是回路中走的首条边。我们对 x\in [2,n] 找到 x 的最后一条出边作为树边（显然其一定不会成环），把剩下的边按照走的顺序排好，就得到了唯一的枚举方案。

综上，有向欧拉图的欧拉回路数为：

T_1\prod_{x=1}^n (d_{out}(x)-1)!

其中 d_{out}(x) 为 x 的出度，T_1 为以 1 为根的内向生成树数。这也间接证明了 \forall x,T_1=T_x。

C. 竞赛图

竞赛图与哈密顿路

证明：归纳地证明之，当我们在图中加入 n 这个点时，考虑 1\sim n-1 形成的哈密顿链，不妨重标号为 1\to2\to\cdots\to n-1：

  1. 若有边 n\to 1 或 (n-1)\to n，则直接连上了；
  2. 否则反证可知一定存在一个 p 使得 p\to n,n\to (p+1)，接到这里即可。

证明：

找到任意一条哈密顿路重标号为 1\to2\to\cdots\to n，再找到最后一个连向 1 的点 x(>1)，构成一个环 1\to2\to\cdots\to x\to 1。

接下来我们不断地找到第一个点 y 使得 y 连向 \{1,2,\cdots,x\} 中的点，由于强连通性所以这样一个点必定存在。

然后我们设 y 连向的最前面的点是 u，构造一条包含 \{1,2,\cdots,y\} 中所有点的回路：

1\rightsquigarrow (u-1)\rightsquigarrow (x+1)\rightsquigarrow y \rightsquigarrow u \rightsquigarrow x \rightsquigarrow1

这样我们使得环扩大了一些。不断重复这个过程直至 x=n 即可。

由此，我们知道任意竞赛图都可以被看作若干哈密顿回路连接而成的链，不妨称此为“竞赛图的 SCC 链结构”。

兰道定理

十分强大的定理。

定义竞赛图 G 的比分序列为把所有点的出度升序排序有后的序列。我们证明 d_{1\cdots n} 是合法的比分序列当且仅当：

\forall i\in [1,n] \sum_{j=1}^i d_j\ge \frac{i(i-1)}{2}

此外，竞赛图中的若干 SCC 中的点所队应的出度一定依次排列（即链上倒数第 k 个 SCC 中的所有点一定排在链上第 k+1 个 SCC 中的所有点之前），且当且仅当 p 满足 \sum_{j=1}^p d_j= \frac{p(p-1)}{2} 时 p 是不同 SCC 的出度间的分割位置（不存在一个 p 之前的点和 p 之后的点属于同一个 SCC）。

证明：

原定理的必要性是显然的，对于前 i 个点的导出子图，这些边贡献的出度至少有 \frac{i(i-1)}{2} 条。

充分性可以构造证明：先构造竞赛图，对所有 i>j 连边 i\to j，这样当前的比分序列为 u_i=i-1。

我们找到首个 u_i\ne d_i，易证一定有 u_i<d_i。我们找到一个 u_k>d_k，由 d 单调 u_k\ge u_i+2，由此可证一定可以找到 p\not\in \{k,i\} 使得 k\to p\to i，翻转之。不断操作直至 u,d 相同即可。

对于下面的推论，“依次排列”的性质是显然的，第二点同样考虑前 i 个点的导出子图就可以证明。

一道值得提到的例题是 CF1268D：

给定一张竞赛图，定义一次操作为选取一个顶点并翻转其所有邻边的方向。

求出是否存在一个操作序列使得图强连通，若存在则求出最小操作次数，以及操作次数最小的操作方案数，对 998244353 取模。

依赖于一些结论，本题最后的部分是平凡的：

因此对 n<7 直接暴力，否则先判断强连通再枚举翻转哪个点，之后判断 SCC 的个数可以通过比分序列实现。

D. 弦图

远古科技。

概念与基本性质

弦图是一种特殊的图，很多在一般图上的 NP-Hard 问题在弦图上都有优秀的线性时间复杂度算法。

极小点割集与单纯点

证明：

考虑删去 S 后的图含 x,y 的连通块分别为 A,B，那么若 (u,v) 间无边，那么考虑 u,v 在 A,B 中的邻居 u_A,u_B,v_A,v_B，容易证明它们一定存在。再考虑 u_A,v_A 二者间的最短路和 u_B,v_B 二者间的最短路构成环，简单讨论四个点相等的情况可以通过弦图的定义推理出 (u,v) 有边。

证明：考虑从 n\ge 4 处开始归纳。

对完全图，第一条显然成立，否则取 (u,v) 不相邻，找出任一 u,v 的极小点割集 I，设去掉 I 后 u,v 所在的连通块分别为 A,B。

由归纳假设，A\cup I 的导出子图若不是完全图则一定有两个不相邻的单纯点，其中必定有一个在 A 中；若是完全图则 A 中任意点都是单纯点。同理 B 中一定也有一个单纯点，由于 A,B 间无边，可以直接取这两个单纯点完成构造。

完美消除序列

我们定义点集的排列 p_{1\cdots n} 是完美消除序列，当且仅当 p_i 在 p_{i\cdots n} 的导出子图中是单纯点。

容易发现，一个弦图一定存在完美消除序列：每次取出任意单纯点即可构造。

此外，存在完美消除序列的图一定是弦图：每个环在序列中第一次出现的点一定与其环上相邻点有边。根据完美消除序列的定义，这两个相邻点一定有边。

至此我们得到"图存在完美消除序列"和"图是弦图"两条件是等价的。

MCS 算法

中文名最大势算法（Maximum Cardinality Search），可以在 \mathcal O(n+m) 内判断图是否为弦图并对弦图求完美消除序列：

然后判定找到的 p_{1\cdots n} 是否合法：

下面给出 SP5446 代码。

const int N = 1e6 + 10;

int n, m; vector<int> g[N];
int val[N], p[N], w[N]; list<int> a[N];
list<int>::iterator pos[N]; unordered_set<int> G[N];

void Main() {
    fo(i, 0, n) {
        val[i] = p[i] = w[i] = 0;
        g[i].clear(), G[i].clear(), a[i].clear();
    }
    fo(i, 1, m) {
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v), g[v].push_back(u);
        G[u].insert(v), G[v].insert(u);
    }
    fo(i, 1, n) pos[i] = a[0].insert(a[0].end(), i);

    int id = 0;
    fr(i, n, 1) {
        id++; while(a[id].empty()) id--;
        int x = a[id].back();
        a[id].pop_back(), p[i] = x, w[x] = i;
        for(int y : g[x]) if(!w[y]) {
            a[val[y]].erase(pos[y]), val[y]++;
            pos[y] = a[val[y]].insert(a[val[y]].end(), y);
        }
    }

    fo(x, 1, n) {
        pair<int, int> c = make_pair(n + 1, -1);
        for(int y : g[x]) if(w[y] > w[x])
            c = min(c, make_pair(w[y], y));
        if(c.second == -1) continue;
        int u = c.second;
        for(int y : g[x]) if(w[y] > w[x] && u != y)
            if(G[u].find(y) == G[u].end())
                return puts("Imperfect"), void();
    }
    puts("Perfect");
}

下证上述算法对任一弦图求出的序列一定是完美消除序列。

设 w_x 为 x 在 p 中的位置（即 w=p^{-1}），如果 p 不是完美消除序列，当且仅当存在 w(x)<w(y)<w(z) 使得存在边 (x,y),(x,z) 且不存在边 (y,z)。考虑一个引理：

这可以简单反证证明：若不存在这样一个 p，那么由于有 z 的存在所以可以得到在 y 被标记的时候有 l_x>l_y，矛盾。证毕。

这样我们考虑若 p 不合法，那么存在一条路径 z\to x\to y\to p，显然 (z,p) 间没有边，否则与弦图的定义矛盾。讨论 p 的位置：

  1. 若 w(p)<w(z)，那么由引理一又可以找到 p^\prime 在更后面满足之前 p 的性质。

    根据 (y,p^\prime) 间是否有边，无论如何都可以找到 z\to x\to y\to p\to p' 或 z\to x\to y\to p' 一条长度至少为 4 的链满足若 (z,p') 间有边就会构成无弦环。这样我们用新的 p' 回过头继续上面的讨论。

  2. 若 w(p)>w(z)，则可以用 w(y)<w(z)<w(p) 在引理一中找到一个新的 z^\prime。

    之后与上一种情况类似，我们用新的 z' 回过头与 p 继续上面的讨论。

不难发现，无论情况如何，我们都可以延长当前从 z 到 p 的"无弦链"。而序列是有限的，若干次找后一定会走到头，找不到更后面的 z'/p'，这样就导出了矛盾。

若需要更加形式化，可以考虑把这个引理写为如下形式：

证明方法与上面类似。（之后的步骤是平凡的。）

应用

最大团与点色数

考虑任意一个极大团在完美消除序列中的第一个点 x，剩下的点 y 一定都是 x 的邻居且位置在 x 之后，我们把所有这样的点集记为 S(x)，由此可以证明最大团大小就是 \max \{1+|S(x)|\}，构造显然。

此外，容易证明任意图的点色数不小于最大团大小，而在弦图中我们只需考虑按“完美消除序列的倒序”贪心染色，每次取它的所有邻居的 mex 即可。由于色数是 \max \{1+|S(x)|\} 所以一定存在一种合法染色方案。

最大独立集与最小团覆盖

最大独立集：正序按照弦图的完美消除序列遍历，贪心选择没有与已选的点有直接连边的点。

证明：显然这是字典序最小的方案。

我们找到第一个点 x 满足我们的贪心中选了它而正解中没有选 x，分类讨论：

  • 若正解中没有选 x 的任一邻居，那么把 x 加入答案依然合法；
  • 否则将 x 的某个邻居调整到 x 不劣。

最小团覆盖：对最大独立集中的每个点 x，选取 x 和排在 x 之后的 x 的邻居构成团。

（由最大独立集的构造方案可以证明所有点都被覆盖到，再利用最大独立集大小不超过最小团覆盖大小可以证明最优性。）

进阶内容可以看 yhx 的博客。

区间图

在区间图 G 中，每个点 x 都对应一个区间 [l_x,r_x]，(x,y) 之间有边当且仅当 [l_x,r_x]\cap [l_y,r_y]\ne \varnothing。

可以证明区间图一定是弦图，因此可以套用弦图算法解决区间图问题。

另外值得一提的是区间图不需要使用 MCS 求完美消除序列，将所有区间按右端点从小到大排序后的结果就是完美消除序列。

E. 平面图

概念与基本性质

对于一张图，若可以在平面上画出 G 的图解使得其中没有任何边的交叉，则称 G 是平面图。

事实上，平面图判定可以做到线性，不过让我先咕一会儿。

对偶图与最小左转法

对于任意平面图 G，定义其对偶图 G'：

最小左转法用于平面图转对偶图。

大致过程是把每条无向边拆成两条有向边，然后确定每条有向边所在的面，并把一条边所在的面和其反向边所在的面相连。

确定面时把每个点出发的所有边逆时针排序，扫一遍所有边，扫到一条边的时候把这条边所属面的所有边都遍历一遍，并确定这些边都属于此面。其中“遍历一遍”就是在走到边 u\to v 时扫描这条边在 v 的出度中的下一条边。

具体实现时正反向边可以使用 i ^ 1 的技巧。

将平面图对偶后，举 P3249 为例，我们可以刻画若干边所包围的多边形的所有面的性质（需要有可减性）。

我们以最外面面积无穷的区域为根跑出对偶图的一棵生成树，然后遍历这个多边形的边在对偶图中所对应的边。

若这条边是非树边就无需考虑，否则按照方向考虑 "加上其子树的贡献" 或者 "减去其子树的贡献"。

可以感性理解一下这样就可以得到答案，证明大概可以考虑若一棵子树根在区域内而有点在区域外，那么路径上一定有边在多边形的边界上，严谨证明不会。

实现有点阿拉丁的，Code。

F. 偏序与 Dilworth 定理

哈斯图

对于严格偏序关系 \prec，建立一张图 G，其中 x\to y 当且仅当 x\prec y 且不存在 z 使得 x\prec z\prec y，这称为哈斯图。

可以发现，哈斯图就是把偏序关系图最简化了，其余信息可以通过传递闭包得到。

Dilworth 定理

对于任意有限偏序集，其最长反链大小等于最小链覆盖大小。

（反链指任意两个元素都不可比的集合。）

证明：

首先最小链覆盖大小至少为最长反链大小，否则一定存在一条链中有两个属于反链的点，矛盾。

接下来我们归纳构造之。考虑删去集合 S 中某个没有入度的元素 x（即不存在 y\succ x），构造 S\backslash \{x\} 的最长反链与最小链覆盖。

设最小链覆盖为 T_{1\cdots k}，我们对每个 i\in [1,k]，找到 T_i 中最大的元素（即最靠链头的元素）A_i，使得存在一个最长反链包含它。记 X_i 为 T_i 上 A_i 及以后的元素，可以证明 S\backslash (\{x\}\cup X_i) 的最长反链大小一定不超过 k-1（当然易证它也不小于 k-1），否则这条反链中一定有一个 T_i 中的元素，且它在 A_i 之前，矛盾。也即，S\backslash (\{x\}\cup X_i) 的最小链覆盖大小为 k-1。

此外我们证明 A_i 两两不可比。若 A_i,A_j 可比，不妨设 A_i\succ A_j，考虑选择了 A_i 的反链在 T_j 上选择了哪个点。由定义，这个点 e 一定满足 A_j\succeq e，那么 A_i\succ e 成立，与反链的定义矛盾。

于是我们考虑若 \exists x\succ A_i，那么我们取 S\backslash (\{x\}\cup X_i) 的最小链覆盖，再加上一条 x\succ T_i 的链就可以构造出 k 的最小链覆盖，与最长反链相等。否则 x 与所有 A_i 均不可比，我们取所有 A_i 和 x 可以组成一条更大的反链。整理一下细节即可完成证明。

G. 斯坦纳树

问题是求一张图上包含一个给定的点集 U 的连通块的最小边权和。

可以考虑 DP，设 dp(i,S) 为当前包含了 S 这个点集，树根的位置在 i 处。

有两种转移，一是同一个位置的子集 (\max,+) 卷积，二是同一个集合的最短路转移，细节略去。总复杂度 \mathcal O(n3^k+m2^k\log m)。

H. K 元环计数

这里指无向图 K 元简单环计数问题，其中 K\in \{3,4\}，其它 K=\mathcal O(1) 的情况一般采用容斥实现。

此处的做法均基于边数，也存在一些复杂度形如 \mathcal O(\frac{n^c}{w}) 的做法。

三元环计数

把所有边定向，把所有边从度数大的点连向度数小的（相同则人为定一个点的顺序），容易发现在的图是 DAG。

不难发现，此时所有点的入度是 \mathcal O(\sqrt{m}) 的：只有原先度数大于 \sqrt{m} 的点才可能成为这样的点，而能连向它们的点只有 \mathcal O(\sqrt{m}) 个。

由此，我们枚举 x 与其出边 x\to y，再枚举 y 的每条边 y\to z，若存在边 x\to z 则找到一个三元环。（这个判断可以用桶完成）

由于每个点作为 y 被访问的次数至多是 \mathcal O(\sqrt{m})，总复杂度（和三元环的总个数）都是 \mathcal O(m\sqrt{m}) 的。

四元环计数

我们将图用同样的方法转成 DAG，然后计数（而不是像上面一样枚举出所有环）。

具体地我们枚举 x，对于每个点设一个计数器，枚举 x 的出边 x\to y，再枚举与 y 相连的边 (y,z)（不一定要是 y\to z），把答案加上 z 当前计数器的值，再把 z 的计数器加一。枚举完 x 后清空所有计数器。（增加答案的过程意味着我们找到了某个环 x\to y\to z\gets y^\prime\gets x，其中 y^\prime 是之前枚举过的某个 y，可以证明 y' 的个数就是计数器的值。）

这个做法的唯一问题就是会把 a\to b\gets c\to d\gets a 这样的环算两遍，这是容易处理的：我们只需要用类似的方法求出这类环的数量容斥掉即可。

后期. 图论进阶算法

A. 最小树形图

问题的形式是：对于一张有向图 G 和一个给定的点 s，我们需要找到以 s 为根的一棵 n 个点的外向树使得其边权和最小。

朱刘算法

首先需要一个引理：我们对于图中的每个点 x(\ne s)，找到其边权最小的一条入边，显然这样会形成若干个点集不交的环 C_{1\cdots k}。

我们证明，存在最小树形图方案使得对于每个 C_i，若其长为 m，则环中至少有 m-1 条边包含在最小树形图的方案中。

这个证明可以使用调整法实现，大致思路是对每个环找到树中 DFS 序最小的一个点 v_1 从前往后依次调整 v_2,v_3,\cdots。

若边 v_i\to v_{i+1} 不在树中。

Tarjan 优化朱刘算法

应用

B. 保序回归

C. 全局最小割

D. 支配树

E. 极大团搜索

F. 带花树