度序列
度序列 可简单图化当且仅当:设 ,则 可简单图化。
Erdos-Gallai 定理
TIP
这个定理可以在 时间内判断度序列是否可简单图化。
度序列 可简单图化当且仅当: 是偶数,并且
竞赛图
- 竞赛图缩点之后,拓扑序靠前的强连通分量向靠后的每个分量连边。
- 竞赛图上存在边 的充要条件是 的出度大于等于 的出度。
度序列 可简单图化当且仅当:设 ,则 可简单图化。
TIP
这个定理可以在 时间内判断度序列是否可简单图化。
度序列 可简单图化当且仅当: 是偶数,并且