竞赛图
定义：\(n\) 个点，任意两点之间有一条有向边的图
性质：
-
竞赛图一定存在一条哈密顿路径
证明：考虑归纳， \(n=1\) 的时候显然成立，现在已经求出 \(n-1\) 个点的竞赛图的哈密顿路径了，发现如果第 \(n\) 个点连出去的边都是指向其他点或者都是指向自己时，一定可以把这个点放到哈密顿路径首或尾，若不满足上面的条件，则一定存在 \(u,v\) 满足有边 \((u,n),(n,v)\) ，直接把 \(n\) 放到 \(u,v\) 中间就好了
-
竞赛图缩点后成链状
这里的是呈链状，边都是从拓扑序小的连向拓扑序大的
证明：发现缩点后还是一张竞赛图，因为竞赛图一定有哈密顿回路，所以呈链状
-
竞赛图的每一个强连通分量都存在哈密顿回路
证明：跟哈密顿路径考虑方法很像，归纳，\(n=1\) 的时候显然成立，还是讨论边的指向，如果都是指向其他点或者都是指向自己时，发现这个点一定自己作为一个 \(scc\) ，否则一定可以在他所在的 \(scc\) 的环上找到两点 \(u,v\) 使得边是 \((u,n),(n,v)\) ，这样一定可以加进去
-
对于一个竞赛图中大小为 \(n\) 的强连通分量，其一定存在大小为 \(\forall len \in [1,i]\) 的简单环
证明：考虑 \(3\) 的证明，我们对于一个强连通分量是一个点一个点加的，每次加之前都会有环，加之后也有环，所以显然是对的
-
如果 \(u\) 的出度大于 \(v\) 的出度，则 \(u\) 一定可以到达 \(v\)
证明：如果 \(u,v\) 在一个强连通分量里面显然正确，当不在一个强连通分量时考虑缩点后的拓扑序
设 \(u\) 所在的强连通分量是 \(x\)，\(v\) 所在的强连通分量是 \(y\) （注意强连通分量编号是拓扑序倒序
当 \(x>y\) 时，缩点完成链状，显然可以到达
当 \(x<y\) 时，因为缩点完了已经没有环了，所以 \(v\) 连出去的点一定是强连通分量标号小于 \(y\) 的， \(u\) 连出去的点一定是强连通分量标号小于 \(x\) 的，又因为 \(x<y\) ，所以得出 \(u\) 出度小于 \(v\) 出度，寄
-
存在竞赛图满足每个点出度序列为 \(arr\) 当且仅当将 \(arr\) 排序后，\(\forall k \sum\limits_{i=1}^{k} arr_i \ge {k \choose 2}\) 且 \(\sum\limits_{i=1}^{n} arr_i = {n \choose 2}\)
证明：必要性显然
充分性考虑构造，先让出边集合 \(A\) 为 \(0,1,2,3…n-1\) ，这显然是可以构造出来的，并且满足上面的条件，现在有一些点不满足，我们换一下边的指向顺序来满足这个条件，设 \(x\) 为第一个不满足 \(A_x=arr_x\) 的地方，\(y\) 为最大的 \(A_y=A_x\) ，\(z\) 为最小的 \(A_z>arr_z\) ，发现 \(A_x < arr_x \le arr_y < A_z\) ，所以必定有一个点 \(p\) 和 \(x,z\) 的关系是边 \((p,x),(z,p)\) 现在只要 \(swap\) 一下两条边指向就可以让 \(A_x+1\rightarrow A_x,A_z-1\rightarrow A_z\) ，发现这个操作一定是可以一直进行的，所以我们就通过不断调整调整出 \(arr\) 来了