竞赛图相关

· · 算法·理论

定义 竞赛图是 n 个点 \binom{n}{2} 条边的有向图,任意 u \ne v 的点对 (u,v) 间恰有一条有向边。

Landau 定理

引理 竞赛图缩 SCC 后形成链状图,每个拓扑序在前的 SCC 向在后的所有 SCC 连边。

设竞赛图节点 u 的入度为 d_u,将 d_1 \sim d_n 升序排序,定理指出

Landau 定理 \forall k\in [1,n], \sum \limits_{i=1}^k d_i \ge \dbinom{k}{2}。取到等号的 k 构成度数序列的划分,每段都是一个 SCC。

证明 参见 https://www.cnblogs.com/acha/p/9042984.html,此处不再赘述。

Redéi 定理 & Camion-Moon 定理

竞赛图哈密顿路 & 哈密顿回路构造问题。

Redéi 定理 任何一个竞赛图都至少存在一条哈密顿路。

构造 考虑增量构造。假设我们已经排好了 1 \sim k-1 的哈密顿路 u_1 \sim u_{k-1},尝试插入 k。找到一个位置 i 使得 (k,u_i), (u_{i+1},k) \in E,将 k 插入到 u_i,u_{i+1} 之间即可。注意特判放在首尾的情形。

直接模拟的复杂度为 O(n^2)。使用数据结构上二分,可以做到 O(n \log n)。

Camion-Moon 定理 一个竞赛图存在哈密顿回路,当且仅当它是强连通的。

构造 先用 Redéi 定理的构造找出一条哈密顿路,然后在路径上顺序扫描。

想象我们当前位于点 x,左侧已经被折叠成环 c_1 \to c_2 \to \cdots \to c_m \to c_1,右侧还是一条链,链是哈密顿路的一部分。

我们尝试将 x 插入环中。分类讨论:

精细实现复杂度 O(n^2)。

QOJ5407 基础图论练习题

给定一张 n 个节点的竞赛图。对所有点对 (u,v) 求出,翻转边 (u,v) 后 SCC 的数目。

:::::success[题解]

根据 Landau 定理只要求得 f_k=\sum \limits_{i=1}^k d_i-\dbinom{k}{2}=0 的 k 的数目。

设 L_x,R_x 分别为度数 x 在升序序列 d_i 中第一次 / 最后一次出现的位置。每次翻边恰有一对 +1 和 -1,修改度数 x 可以视作修改 L_x 和 R_x。

设修改令 L_a \gets L_a-1, R_b \gets R_b+1 分讨:

对 f 计数后施前缀和即可做到 O(n^2)。代码。

:::::

P3561 [POI 2017] Turysta

给定一张 n 个节点的竞赛图。对于每个点 u 求出从 u 出发的最长简单路径,输出构造。

::::::success[题解]

利用 Landau 定理推论找出所有 SCC 并缩点后,DAG 的形态是链状图。

考虑找出每个 SCC 的哈密顿回路。根据 DAG 的形态,直接取一段后缀的哈密顿回路拼起来,就能构成一条简单路径。

这样,这个问题的做法就显然了:利用 Camion-Moon 定理的构造求得 SCC 的哈密顿回路。对于一点 u,取拓扑序不小于其所在 SCC 的所有哈密顿回路拼起来。

精细实现复杂度 O(n^2)。代码。

::::::