竞赛图随记

JCY_ · 2023-09-29 07:51:18 · 个人记录

更好的阅读体验

竞赛图的定义

对于一张无自环的有向图 G，如果每对不同节点之间都恰有一条有向边，则称 G 是竞赛图。

竞赛图缩点后是一条链

考察竞赛图 G = (V, E) 缩点后的强连通分量，我们给它们任意指定一个拓扑序。不难发现，\forall u, v \in V，如果 u, v 所属强连通分量不同且 u 所属的强连通分量在拓扑序上更靠前，则必有 (u, v) \in E。因此，竞赛图 G 缩点后形成了一条链。

竞赛图与哈密顿路

竞赛图有哈密顿路径（Redei 定理）

证明

对于一张竞赛图 G = (V, E)，我们可以通过归纳构造出它的一条哈密顿路径。

假设我们已经在点 1 到 i - 1 的导出子图中找出了一条哈密顿路径 p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{i - 1}。

如果 (p_{i - 1}, i) \in E，我们把路径变为 p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{i - 1} \rightarrow i。

否则如果 (i, p_1) \in E，我们把路径变为 i \rightarrow p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{i -1}。

否则找到最小的下标 x 满足 (i, p_x) \in E，由不满足上述两个条件可知 x 存在且 x > 1，我们把路径变为 p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{x - 1} \rightarrow i \rightarrow p_x \rightarrow \dots \rightarrow p_{i - 1}。

初始令 p_1 \leftarrow 1，我们依次加入点 2 到 n。当 n 个点都被加入后，p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_n 即为一条哈密顿路径。

由上，我们可以 O(n^2) 构造出一个 n 阶竞赛图的哈密顿路径。

代码

fill(nxt + 1, nxt + n + 1, 0);
int l = 1, r = 1;
for (int i = 2; i <= n; ++i) {
  if (g[r][i]) {
    nxt[r] = i;
    r = i;
  } else if (g[i][l]) {
    nxt[i] = l;
    l = i;
  } else {
    for (int x = l;; x = nxt[x]) {
      if (g[i][nxt[x]]) {
        nxt[i] = nxt[x];
        nxt[x] = i;
        break;
      }
    }
  }
}

强连通竞赛图有哈密顿回路（Camion-Moon 定理）

证明

对于一张强连通的竞赛图 G = (V, E)，我们可以通过归纳在它的一条哈密顿路径的基础上构造出一条哈密顿回路。

我们找出一条哈密顿路径，把每个点按照它在哈密顿路径上的位置重标号。即重标号后我们有 \forall i \in [1, n - 1] \cap \mathbb{Z}, (i, i + 1) \in E。

假设我们已经把点 1 到 i - 1 分成了两个部分：一个环 p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_k \rightarrow p_1 和一条路径 k + 1 \rightarrow k + 2 \rightarrow \dots \rightarrow i - 1，满足 \forall x \in [1, k] \cap \mathbb{Z}, \forall y \in [k + 1, i - 1] \cap \mathbb{Z}, (p_x, y) \in E。

如果 \forall x \in [1, k] \cap \mathbb{Z}, (p_x, i) \in E，我们把路径变为 k + 1 \rightarrow k + 2 \rightarrow \dots \rightarrow i - 1 \rightarrow i。

否则，找到任意 x 满足 (i, p_x) \in E \land (p_{x - 1}, k + 1) \in E，由 (i - 1, i) \in E 可知存在这样的 x，我们把环变为 p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{x - 1} \rightarrow k + 1 \rightarrow k + 2 \rightarrow \dots \rightarrow i \rightarrow p_x \rightarrow \dots \rightarrow p_k \rightarrow p_1，然后令 k \leftarrow i。

初始我们找到最小的 x 满足 (x, 1) \in E，由 G 强连通可知 x 存在，令 k \leftarrow x, \forall i \in [1, x] \cap \mathbb{Z}, p_i \leftarrow i。我们依次加入点 x + 1 到 n。当 n 个点全部被加入后，必有 k = n，否则与 G 强连通矛盾。p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_n \rightarrow p_1 即为一条哈密顿回路。

由上，我们可以 O(n^2) 构造出一个 n 阶强连通竞赛图的哈密顿回路。

代码

fill(nxt + 1, nxt + n + 1, 0);
int l = 1, r = 1;
for (int i = 2; i <= n; ++i) {
  if (g[r][i]) {
    nxt[r] = i;
    r = i;
  } else if (g[i][l]) {
    nxt[i] = l;
    l = i;
  } else {
    for (int x = l;; x = nxt[x]) {
      if (g[i][nxt[x]]) {
        nxt[i] = nxt[x];
        nxt[x] = i;
        break;
      }
    }
  }
}
r = 0;
for (int i = l; i; i = nxt[i]) {
  if (!r) {
    if (g[i][l]) r = i;
    continue;
  }
  if (g[i][l]) {
    r = i;
  } else {
    for (int x = l; x != r; x = nxt[x]) {
      if (g[x][nxt[r]] && g[i][nxt[x]]) {
        int t = nxt[x];
        nxt[x] = nxt[r];
        nxt[r] = l;
        l = t;
        r = i;
        break;
      }
    }
  }
}
nxt[r] = l;

强连通竞赛图是泛圈的（Camion-Moon 定理推论）

对于一张 n 阶有向图 G，如果 \forall i \in [3, n] \cap \mathbb{Z}，G 含有长度为 i 的环，则称 G 是泛圈的。

证明

当 n \le 3 时定理成立，我们可以通过归纳证明该定理。

不难发现我们只需要证明 \forall n \in [4, +\infty) \cap \mathbb{Z}，n 阶强连通竞赛图含有长度为 n - 1 的环。这是因为长度为 n - 1 的环的点集的导出子图是一个 n - 1 阶强连通竞赛图，根据归纳假设 \forall i \in [3, n - 1] \cap \mathbb{Z}，它含有长度为 i 的环。又因为我们已经证明了 n 阶强连通竞赛图有哈密顿回路，即长度为 n 的环，所以原定理得证。

考察 n 阶竞赛图的一条哈密顿回路 p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_n \rightarrow p_1。我们在原图中删去点 p_1，如果剩下的部分强连通则容易找出长度为 n - 1 的环，否则剩下的部分缩点后形成了一条链。