竞赛图学习笔记

定义：对任意 $u,v$，存在 $u\to v$ 或 $v\to u$ 的有向图为竞赛图。也可以说是有向完全图。

定理 1：竞赛图存在一条哈密顿路径。

证明：考虑通过归纳法构造证明。

假设现在有 $n-1$ 个点的竞赛图，并且我们已经找到了一条哈密顿路径 $v_{1\dots n-1}$，考虑加入一个点 $u$。

若存在 $v_{n-1}\to u$，则将 $u$ 放在哈密顿路径末尾；
若存在 $u\to v_{1}$，则将 $u$ 放在哈密顿路径开头；
否则，一定存在 $v_i\to u$ 且 $u\to v_{i+1}$（考虑若 $v_i\to u$，令 $a_i=0$，反之令 $a_i=1$，现在有 $a_1=0,a_{n-1}=1$，则必然存在从 $0$ 到 $1$ 的分界点，很经典的 trick），那么将 $u$ 插入到 $v_i,v_{i+1}$ 之间即可。

$\blacksquare$

定理 2：竞赛图缩点后，将点按照拓扑序排列，每个点都会向后面所有点连边。

证明：缩点之后会形成一个 DAG，同时任意两点之间有边，定理显然成立。$\blacksquare$

注：进一步的，每个强连通分量内的所有点都会向后面强连通分量内的所有点连边。

定理 3：竞赛图存在哈密顿回路的充要条件是强连通。

证明：必要性显然，下证充分性。我们仍使用归纳法。

假设定理对所有点数 $<n$ 的竞赛图成立。现在对于一张 $n$ 个点的强连通竞赛图 $G$，我们任意取出一点 $u$，若剩余点的导出子图 $G'$ 不强连通，则将该图中的所有强连通分量按照拓扑序排列。由于加入 $u$ 后图会变得强连通，所以必然存在第一个强连通分量内的某点 $v_f$ 使得存在边 $u\to v_f$，同理也必然存在最后一个强连通分量内的某点 $v_e$ 使得存在边 $v_e\to u$。由归纳假设我们知道 $G'$ 中每个强连通分量均有哈密顿回路，这也就意味着对每个强连通分量，我们都可以从任意点开始或结尾走出一条哈密顿路径，结合定理 2，$G'$ 中必然存在一条 $v_f\rightsquigarrow v_e$ 的哈密顿路径，再加上 $v_e\to u\to v_f$ 两条边，我们就得到了一条哈密顿回路。

另一种情况则更为简单，即 $G'$ 强连通，显然 $G'$ 中所有点和 $u$ 之间的边不可能全部同向，我们总是可以在 $G'$ 的哈密顿回路上找到相邻两点使得 $u$ 可以被插入到这两点之间。

综上，原命题得证。$\blacksquare$

另证：构造性地证明充分性。

任取哈密顿路径 $v_{1\dots n}$，由于图强连通，存在 $v_i\to v_1$，找到最大的 $i$，则我们有包含前 $i$ 个点的哈密顿回路，在此基础上增量构造。

找到 $v_i$ 之后第一个点 $v_k$ 使其向回路中有边，不妨设 $v_k\to v_j$，$v_j$ 是回路中的点。由于 $k$ 是最小的，有 $v_{j-1}\to v_{i+1}$。于是有包含前 $k$ 个点的哈密顿回路 $v_1\rightsquigarrow v_{j-1}\to v_{i+1}\rightsquigarrow v_k\to v_j\rightsquigarrow v_i\to v_1$。为点重编号，重复这一过程直到哈密顿回路包含所有点即可。用程序实现这一构造的复杂度为 $O(n^2)$。$\blacksquare$

定理 4：竞赛图若存在环，则一定存在三元环。

证明：首先自环和二元环是不可能存在的，考虑若现在有一个长度为 $k\ (k>3)$ 的环。

任取 $u\to v\to w$：

若 $w\to u$，则我们已经找到了一个三元环。
若 $u\to w$，则我们找到了一个 $k-1$ 元环，重复此过程必然会找到三元环。

$\blacksquare$

定理 5（竞赛图强连通性判定定理）：竞赛图不强连通的充要条件是将所有点按出度从小到大排列后存在 $i\ (1\le i<n)$ 使得前 $i$ 个点的出度之和为 $i(i-1)/2$。

证明：

充分性：在竞赛图中，一个大小为 $i$ 的点集内部就有 $i(i-1)/2$ 条边，所以出度之和 $\ge i(i-1)/2$，取到等号也就意味着该点集不向外部连边，图显然不强连通。
必要性：若将所有点按照出度从小到大排列，不难发现该顺序相当于将所有强连通分量按反拓扑序排列，强连通分量内部点的顺序不定。由定理 2 我们知道拓扑序靠前的强连通分量总是向靠后的分量连边，那么我们只要取出拓扑序最靠后的若干强连通分量，其就满足是序列上的一个前缀且不会向外部的点连边，设点数为 $n_0$，出度和取到最小值 $n_0(n_0-1)/2$。

$\blacksquare$

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。