竞赛图(tournament graph)

约 206 个字 预计阅读时间 1 分钟

定义：$n$ 个点的有向图，满足任意不同两点都有且仅有一条有向边

1. 将竞赛图缩点之后，缩成的所有强连通分量按照出度从小到大排成的序列，一定满足第 $i$ 个强连通分量与所有 $j>i$ 的强连通分量 $j$ 都有一条 $i\rightarrow j$ 的边
2. 竞赛图的所有强连通分量都存在一条哈密顿回路
3. 竞赛图存在一条哈密顿路径
4. 竞赛图里，任意大小为 $n>1$ 的强连通分量中，大小为 $[3,n]$ 的环均存在
5. 令 $s_i$ 为第 $i$ 个点的出度,对 $s$ 排好序后, 若满足 $\sum\limits_{i=1}^ks_i\ge\dbinom k2$ 且 $\sum\limits_{i=1}^n s_i=\dbinom n2$ , 定能构造出一种竞赛图, 反之不能