Znzryb's Blog
0%

完全理解环以及回路相关问题 （图论中，找最大环是 NP-hard 问题，所以不可能找最大环，这是因为找出最大环的方法可以非常轻松的判定以及找到图中的哈密顿环）

Posted on Edited on

图论中，找最大环是 NP-hard 问题，所以不可能找最大环。

找“最大环”（即无向图或有向图中的最长简单环，Longest Cycle Problem）是一个经典的 NP-Hard 问题。它和旅行商问题（TSP，Traveling Salesperson Problem）有着极深的渊源，本质上它们都是哈密顿环（Hamiltonian Cycle）问题的衍生和泛化。

我们可以从以下几个方面来理解为什么它是 NP-Hard，以及它和 TSP 的共性所在：

1. 为什么找最大环是 NP-Hard 问题？

在计算复杂性理论中，证明一个问题是 NP-Hard 的最标准方法，就是将一个已知的 NP-Hard/NP-Complete 问题规约（Reduce）到它。对于“最大环”问题，最直接的规约对象就是哈密顿环问题。

  • 哈密顿环问题：给定一个包含 VV 个顶点的图，问是否存在一个简单环，它恰好经过图中的每一个顶点一次？这是一个非常著名的 NP-Complete 问题。

  • 规约过程：假设你拥有一个能够在多项式时间内求出任意图“最大简单环”的神奇算法。现在给你一个未知的图，你只需要运行这个神奇算法求出图中的最大环，然后看看这个最大环的长度是不是正好等于顶点总数 VV。

    • 如果等于 VV，说明图里存在哈密顿环。
    • 如果小于 VV，说明图里不存在哈密顿环。

图图论中，找最大环是 NP-hard 问题，所以不可能找最大环，这是因为找出最大环的方法可以非常轻松的判定以及找到图中的哈密顿环。

存在欧拉回路的这个条件也很简单**，就是每个顶点的度数都是偶数，那么一定存在一条欧拉回路（在联通无向图中）**

欧拉路径存在的充要条件（在无向连通图上），就是奇数度数节点数量等于0 或者 2（也就是要么是一条回路，也就是 0，要么是起点和重点可以少一条边）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
if (odd_cnt!=0 && odd_cnt!=2) {
    cout<<"NO\n";
    return;
}

vector<ll> ans_ls;
auto dfs=[&](auto && self,ll u) -> void {
    while (!g[u].empty()) {
        auto it=g[u].begin();
        auto [to,id]=*it;
        g[u].erase(it);
        g[to].erase({u,id});
        self(self,to);
        ans_ls.push_back(id);
    }
};
dfs(dfs,max(start_node,g.begin()->first));
// 判断图是否联通，如果不联通，也是错的。
if (SZ(ans_ls)!=N) {
    cout<<"NO\n";
    return;
}
reverse(all(ans_ls));
cout<<"YES\n";
for (auto u:ans_ls) {
    cout<<u<<" ";
}
cout<<"\n";

为什么 Euler 路径红色这样子写有问题呢？其实也很容易理解，因为我们要把 ans_ls 反过来的呀！所以说，肯定需要先遍历完后续的点，才能塞入这条边啊！其实简单来说，就是要和正常的反过来！

image

Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路）

Codeforces Round 1026 (Div. 2)-CF-1026-E. Melody