竞赛图及其性质

咕咕咕…

竞赛图的定义

若有向简单图 \(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/