对竞赛图的一些研究
来玩点组合数学，更多详细证明可能得明天了。
定义
\(n\) 个点 \(\binom{n}{2}\) 条边的有向完全简单图。
定理1
竞赛图强连通分量缩点之后会形成一条链，拓扑序在前的节点会往后面每一个节点连边。
定理2
竞赛图必然包含一条哈密顿通路
定理3
强连通竞赛图必然包含一条哈密顿回路
上述两条定理可以看这里
定理4
强连通竞赛图中任何一个点必然被包含在一个三元环中。
显然。
定理5 & Moon Theory
强连通竞赛图中必然存在 \(i\in [3,n]\) 元环。
根据定理4归纳即可。
定理6 & Landau's Theorem
将出度序列从小到大排序得到 \(s_i\)，设 \(sum_i=\sum_{j=1}^{i}s_j\)，则该图是竞赛图当且仅当 \(\forall 1\le k\le n, sum_k\ge \binom{k}{2}\)。
还有如果是强连通竞赛图则不存在 \(1\le k\le n-1,sum_{k}=\binom{k}{2}\)
定理7
竞赛图的每一个强连通分量可以看成一个前缀集合，集合中的点到集合外的点的方向全是里 \(\to\) 外。
最大流
\(|maxflow(u,v)-maxflow(v,u)=|deg_u-deg_v|\)，这里 \(deg_u\) 是点 \(u\) 的出度。简单分类讨论即可。
强连通竞赛图计数
\(f_n=2^{\binom{n}{2}}-\sum_{j=1}^{i-1}f_j2^{(i-j)(i-j-1))}\)