度序列

度序列 可简单图化当且仅当:设 ,则 可简单图化。

Erdos-Gallai 定理

TIP

这个定理可以在 时间内判断度序列是否可简单图化。

度序列 可简单图化当且仅当: 是偶数,并且

竞赛图

  1. 竞赛图缩点之后,拓扑序靠前的强连通分量向靠后的每个分量连边。
  2. 竞赛图上存在边 的充要条件是 的出度大于等于 的出度。