冷门性质总结

对于一个竞赛图，将其顶点按出度从小到大排序，则存在 \(k < n\) 使得前 \(k\) 个顶点的出度之和等于 \(\binom{k}{2}\) 是该竞赛图非强连通的充要条件。

兰道定理：记每个点的出度为 \(out_i\) , 这些点能构成竞赛图当且仅当将 \(out\) 从小到大排序后 \(\sum_{i=1}^{n}out_i = \binom{n}{2}\) , 且对于 \(\forall 1 \leq k \leq n, \sum_{i=1}^{k} out_i \geq \binom{k}{2}\)