竞赛图相关
stripe_python · · 算法·理论
定义 竞赛图是
Landau 定理
引理 竞赛图缩 SCC 后形成链状图,每个拓扑序在前的 SCC 向在后的所有 SCC 连边。
设竞赛图节点
Landau 定理
证明 参见 https://www.cnblogs.com/acha/p/9042984.html,此处不再赘述。
Redéi 定理 & Camion-Moon 定理
竞赛图哈密顿路 & 哈密顿回路构造问题。
Redéi 定理 任何一个竞赛图都至少存在一条哈密顿路。
构造 考虑增量构造。假设我们已经排好了
直接模拟的复杂度为
Camion-Moon 定理 一个竞赛图存在哈密顿回路,当且仅当它是强连通的。
构造 先用 Redéi 定理的构造找出一条哈密顿路,然后在路径上顺序扫描。
想象我们当前位于点
我们尝试将
-
若存在
(c_i, x) \in E, (x, c_{i+1}) \in E ,可以直接将x 插入c_i.c_{i+1} 之间。 -
否则,我们维护集合
A=\{u \mid (c_i,u) \notin E\} ,B=\{u \mid (u,c_i) \notin E\} ,即不被任何环内节点指向的A 和不指向任何环内节点的B 。不妨设x \in A 。
由于图是强连通的,必然存在y \in B, (y,x) \in E 。只要将x,y 一起插入环中。
我们在环中随意找一条边,比如c_1 \to c_2 。根据A,B 的定义,有(c_1,y),(x,c_2) \in E 。将c_1 \to y \to x \to c_2 插入即可。
精细实现复杂度
QOJ5407 基础图论练习题
给定一张
n 个节点的竞赛图。对所有点对(u,v) 求出,翻转边(u,v) 后 SCC 的数目。
:::::success[题解]
根据 Landau 定理只要求得
设
设修改令
- 若
a \le b ,只有k \in [L_a,R_b) 的f_k \gets f_k-1 ,变化量为[*=1]-[*=0] 。 - 若
a \ge b+2 ,只有k \in [R_b,L_a) 的f_k \gets f_k+1 ,变化量为-[*=0] 。 - 若
a=b+1 则无变化。
对
:::::
P3561 [POI 2017] Turysta
给定一张
n 个节点的竞赛图。对于每个点u 求出从u 出发的最长简单路径,输出构造。
::::::success[题解]
利用 Landau 定理推论找出所有 SCC 并缩点后,DAG 的形态是链状图。
考虑找出每个 SCC 的哈密顿回路。根据 DAG 的形态,直接取一段后缀的哈密顿回路拼起来,就能构成一条简单路径。
这样,这个问题的做法就显然了:利用 Camion-Moon 定理的构造求得 SCC 的哈密顿回路。对于一点
精细实现复杂度
::::::