跳转至

简单图论问题

拓扑排序ψ(｀∇´)ψ

用来给一个 DAG 排序。

排序过后，对于所有有向边 \((u\to v)\) 满足，\(v\) 一定在 \(u\) 的后面。

做法很简单，先把所有 \(0\) 入度的点入队。

然后做一个类似 BFS 的过程，过程当中要记得删边和点，如果出现了新的 \(0\) 入度点，就入队。

在判定严格偏序这种对应 DAG 的关系成不成立的时候也可以使用拓扑排序判定和构造解。

（如果有环就是无解，对应到拓扑排序就是最后始终存在非 \(0\) 入度点。）

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int cnt = 0;
std::queue<int> q;
for(int i = 1; i <= n; ++i) 
    if(!ind[i]) q.push(i);
while(!q.empty()) {
    int u = q.front(); q.pop();
    ord[u] = ++cnt; // topo 序
    for(auto v : G[u]) if(!(--ind[v])) q.push(v);
    // 删掉边，顺便判一下要不要入队。
}

拓扑序还可以用来转移 DP。

一般转移的时候不是找上一个（前驱），而是从当前的推到后一个（后继）。

按拓扑序枚举每一个点，再枚举它的每一个出边，进行递推即可。

欧拉图ψ(｀∇´)ψ

具有欧拉回路的无向图或有向图称为欧拉图。

具有欧拉路但不具有欧拉回路的无向图或有向图称为半欧拉图。

欧拉图中所有顶点的度数都是偶数。

若 \(G\) 是欧拉图，则它为若干个环的并，且每条边被包含在奇数个环内。

欧拉路ψ(｀∇´)ψ

通过图中所有边恰好一次的通路称为欧拉路。

就是从某点开始的一笔画问题（可以经过一个点多次）。

  • 有向联通图存在欧拉路的充要条件

    要么所有点的出度均等于入度

    要么除了两个点之外，其余所有点的出度均等于入度 。

    剩余的两个点:一个满足出度减去入度等于 \(1\) (起点) ，一个满足入度减去出度等于 \(1\) (终点)。

  • 无向联通图存在欧拉路的充要条件：度数为奇数的点只能有 \(0\) 或 \(2\) 个。

欧拉回路ψ(｀∇´)ψ

通过图中所有边恰好一次的回路称为欧拉回路。

就是一笔画且要求回到起点。

  • 有向联通图存在欧拉回路的充要条件：所有点的出度均等于入度。

  • 无向联通图存在欧拉回路的充要条件：度数为奇数的点只能有 \(0\) 个。

求具体方案

用 dfs 就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
std::stack<int>s;
inline void dfs(int u){
    for(register int i=head[u];~i;i=e[i].Next){
        int v=e[i].ver;
        if(!vis[i]){ // 当前边没有访问过
            vis[i]=true; // 注意一定要访问到就直接标记，不然复杂度会假。
            dfs(v),s.push(v);
        }
    }
}
// in main()
dfs(1); // 因为有欧拉回路，所以其实从哪个点开始都一样。
vector<int>ans; while(!s.empty()) ans.push_back(s.top()),s.pop();
reverse(ans.begin(),ans.end()); for(auto x:ans) cout<<x<<" "; // 倒序输出。

欧拉路的话也差不多，如果图本身是欧拉图直接当回路跑，如果是半欧拉图就直接把多出来的那两个点连边跑欧拉回路最后删掉加的边即可。

字典序最小的回路/路径可以看 221025C 模拟赛的 D 题

哈密顿图ψ(｀∇´)ψ

摘自 OI-Wiki

定义ψ(｀∇´)ψ

通过图中所有顶点一次且仅一次的通路称为哈密顿通路。

通过图中所有顶点一次且仅一次的回路称为哈密顿回路。

具有哈密顿回路的图称为哈密顿图。

具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。

性质ψ(｀∇´)ψ

设 \(G=<V, E>\) 是哈密顿图，则对于 \(V\) 的任意非空真子集 \(V_1\)，均有 \(p(G-V_1) \leq |V_1|\)。其中 \(p(x)\) 为 \(x\) 的连通分支数。

推论：设 \(G=<V, E>\) 是半哈密顿图，则对于 \(V\) 的任意非空真子集 \(V_1\)，均有 \(p(G-V_1) \leq |V_1|+1\)。其中 \(p(x)\) 为 \(x\) 的连通分支数。

完全图 \(K_{2k+1} (k \geq 1)\) 中含 \(k\) 条边不重的哈密顿回路，且这 \(k\) 条边不重的哈密顿回路含 \(K_{2k+1}\) 中的所有边。

完全图 \(K_{2k} (k \geq 2)\) 中含 \(k-1\) 条边不重的哈密顿回路，从 \(K_{2k}\) 中删除这 \(k-1\) 条边不重的哈密顿回路后所得图含 \(k\) 条互不相邻的边。

充分条件ψ(｀∇´)ψ

设 \(G\) 是 \(n(n \geq 2)\) 的无向简单图，若对于 \(G\) 中任意不相邻的顶点 \(v_i, v_j\)，均有 \(d(v_i)+ d(v_j) \geq n - 1\)，则 \(G\) 中存在哈密顿通路。

推论 1：设 \(G\) 是 \(n(n \geq 3)\) 的无向简单图，若对于 \(G\) 中任意不相邻的顶点 \(v_i, v_j\)，均有 \(d(v_i)+ d(v_j) \geq n\)，则 \(G\) 中存在哈密顿回路，从而 \(G\) 为哈密顿图。

推论 2：设 \(G\) 是 \(n(n \geq 3)\) 的无向简单图，若对于 \(G\) 中任意顶点 \(v_i\)，均有 \(d(v_i) \geq \frac{n}{2}\)，则 \(G\) 中存在哈密顿回路，从而 \(G\) 为哈密顿图。

设 \(D\) 为 \(n(n \geq 2)\) 阶竞赛图，则 \(D\) 具有哈密顿通路。

若 \(D\) 含 \(n(n \geq 2)\) 阶竞赛图作为子图，则 \(D\) 具有哈密顿通路。

强连通的竞赛图为哈密顿图。

若 \(D\) 含 \(n(n \geq 2)\) 阶强连通的竞赛图作为子图，则 \(D\) 具有哈密顿回路。

最后更新: May 9, 2023