竞赛图及其性质

咕咕咕…

竞赛图的定义

若有向简单图 $G=(V,E)$ 满足任意不同两点间都有恰好一条边（单向），则称 $G$ 为 竞赛图。

注意与 有向完全图 作区分，有向完全图是任意 $u,v \in V$ 均有边 $u \to v$ 和 $v \to u$ 。而竞赛图只有其中一条。

---

竞赛图的性质

• 竞赛图不存在自环。若竞赛图存在环，则一定存在三元环。

• 任意竞赛图均有哈密顿路径（经过每一个点的路径 $\langle v_1,v_2,\cdots,v_k\rangle$ 且 $v_i \ne v_j$ ）

• 竞赛图存在哈密顿回路当且仅当其为强连通图。

• 竞赛图缩点后为呈单向链状，每个点向其后所有点连边

• 判断竞赛图是否强连通可以将点的出度按升序排序

  若不存在 $k<n$ 使得前 $k$ 个出度之和等于 $\binom{k}{2}$ ，则原图强连通

  时间复杂度为 $\mathcal{O}(n \log n)$ 。朴素的 $\mathtt{Tarjan}$ 做法是 $\mathcal{O}(n^2)$ 的（因为 $m = n^2$ ）

---

竞赛图性质题

可以参考：

CF913F Strongly Connected Tournament 题解

---

参考文献：

[1] https://blog.csdn.net/weixin_45697774/article/details/108979515

[2] 《离散数学（第六版）》 屈婉玲

[3] https://juju527.github.io/post/jing-sai-tu-xue-xi-bi-ji/