图论杂记
杂技
竞赛图（有向完全图）
竞赛图即有向完全图指的是任意两点间有且仅有一条有向边的图。
性质：
- 竞赛图没有自环、二元环；若竞赛图存在环，则一定存在三元环；若存在一个环大于三元，则一定存在另一个三元的小环。
- 任意竞赛图都有哈密顿路径（经过所有点一次的路径）。
- 图存在哈密顿回路的充要条件是强连通。
- 哈密顿问题中，对于n阶竞赛图，当n大于等于2时一定存在哈密顿道路
- 竞赛图中入度小的点一定能够达到入度大于等于该点的点，其缩点后的DAG中只有一个source、一个sink
兰道定理
兰道定理用于判定竞赛图。
将一个竞赛图的每一个点的出度从小到大排序后得到的序列称为竞赛图的比分序列。
兰道定理：