图的性质

度序列

度序列 $\{d_1,\cdots ,d_n\}$ 可简单图化当且仅当：设 $d_1={\max }_i{d}_i$，则 $\{d_2-1,\cdots ,d_{d_1+1}-1,d_{d_1+2},\cdots ,d_n\}$ 可简单图化。

Erdos-Gallai 定理

TIP

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

度序列 $\{d_1,\cdots ,d_n\}$ 可简单图化当且仅当：${\sum }_i{d}_i$ 是偶数，并且

$$\sum _{i=1}^k{d}_i⩽k(k-1)+\sum _{i=k+1}^n\min (d_i,k).$$

竞赛图

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