Warning: session_start(): open(/tmp/sess_d8b906671db1885cbf76dc82c3fdc848, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
===== 竞赛图的性质 =====
竞赛图是指任意两点间恰有一条有向边的有向图。简记 $u\to v$ 表示 $u$ 到 $v$ 存在一条有向边。
==== 性质 1 ====
任意竞赛图都存在一条哈密顿通路。
**证明**：$n=1$ 时显然。$n\ge2$ 时，考虑归纳法，设 $n-1$ 时的哈密顿通路为 $p_{1},p_{2},\cdots,p_{n-1}$。新加入 $n$ 时，若存在 $i$ 使得 $p_{i}\to n$ 且 $n\to p_{i+1}$，那么将 $n$ 放在 $p_{i}$ 之后即可。
否则，假如所有点都向 $n$ 有边，将 $n$ 放在 $p_{n-1}$ 后即可，反之亦然。
否则，必然有 $p_{n-1}\to n$，$n\to p_{1}$，那么 $p_{2},\cdots,p_{n-1},n,p_{1}$ 满足要求。
==== 性质 2 ====
任意强连通的竞赛图都存在一条哈密顿回路。
**证明**：$n\le3$ 时显然。$n\ge4$ 时，考虑归纳法，设 $n-1$ 时的哈密顿回路为 $p_{1},p_{2},\cdots,p_{n-1}$。新加入 $n$ 时，若存在 $i$ 使得 $p_{i}\to n$ 且 $n\to p_{i+1}$，那么将 $n$ 放在 $p_{i}$ 之后即可。
否则，由于图强连通，不可能所有点都向 $n$ 有边或 $n$ 向所有点有边。因此必然有 $p_{n-1}\to n$，$n\to p_{1}$，那么 $p_{2},\cdots,p_{n-1},n,p_{1}$ 满足要求。
==== 性质 3 ====
任意竞赛图强连通分量缩点之后，所有边必然由拓扑序小的点指向拓扑序大的点。
**证明**：缩点之后的图存在一个哈密顿通路，这条通路显然是按拓扑序排序的。假如存在一条由拓扑序大的点指向拓扑序小的点的边，会产生一个环，与该图是 DAG 矛盾。
==== 性质 4 ====
若某个竞赛图存在一个长度为 $n(n\ge4)$ 的环，那么存在一个长度 $n-1$ 的环。
**证明**：设环为 $p_{1},\cdots,p_{n}$，若存在 $p_{i}\to p_{i+2}$，显然将 $p_{i+1}$ 删去即可。否则，我们证明将 $p_{1}$ 删除后，剩下的点仍然强连通。$p_{2}$ 可以走到所有的点，$p_{3}\to p_{4}\to p_{2}$，因此 $p_{3}$ 也可以走到所有的点。对于 $i\ge 4$，$p_{i}\to p_{i-2}$，因 此 $p_{i}$ 同样可以走到所有的点。由于它强连通，因此存在一个长度为 $n-1$ 的环。
===== 兰道定理 =====
定义一个竞赛图的比分序列 $s_{1},\cdots,s_{n}$ 为将图中所有点出度从小到大排序后的序列。$\{s\}$ 是一个度数序列当且仅当 $\forall 1\le is_{w}$ 的 $w$（如果不存在的话，$\sum_{i=1}^{n}s_{i}>\sum_{i=1}^{n}t_{i}$，矛盾）。如图所示：
$$
\begin{matrix}
&s_{1}&\cdots&s_{u-1}&s_{u}&\cdots&s_{v}&s_{v+1}&\cdots&s_{w-1}&s_{w}&s_{w+1}&\cdots&s_{n}\\
&\parallel&\vdots&\parallel&\lor&\vdots&\lor&\parallel\lor&\vdots&\parallel\lor&\land&?&\vdots&?\\
&t_{1}&\cdots&t_{u-1}&t_{u}&\cdots&t_{v}&t_{v+1}&\cdots&t_{w-1}&t_{w}&t_{w+1}&\cdots&t_{n}\\
\end{matrix}
$$
可见，$t_{w}>s_{w}\ge s_{v}>t_{v}$，即 $t_{w}\ge t_{v}+2$，$|\text{out}(w)|+|\text{in}(v)|=n-1+|\text{out}(w)|-|\text{out}(v)|\ge n+1$。考虑到可能存在 $w\to v$，从集合中删去 $w,v$ 后，有 $|\text{out}(w)|+|\text{in}(v)|\ge n-1$。根据抽屉原理，至少存在一个点 $a\neq w,v$， $w\to a\to v$。
考虑将 $w\to a\to v$ 反转为 $v\to a\to w$，会导致 $t_{w}=t_{w}-1,t_{v}=t_{v}+1$。注意到 $t_{v}