Erdos-Gallai定理
数列 ( d 1 , d 2 , . . . , d n ) ( n − 1 ≥ d 1 ≥ d 2 ≥ . . . ≥ d n ≥ 0 ) (d_1,d_2,...,d_n)(n-1\ge d_1\ge d_2\ge ...\ge d_n\ge 0) (d1,d2,...,dn)(n−1≥d1≥d2≥...≥dn≥0)可简单图化的充要条件是：
- ∑ i = 1 n d i \sum_{i=1}^nd_i ∑i=1ndi为偶数
- ∀ r ( 1 ≤ r ≤ n ) , ∑ i = 1 r d i ≤ r ( r − 1 ) + ∑ i = r + 1 n min { r , d i } \forall r(1\le r\le n),\sum_{i=1}^rd_i\le r(r-1)+\sum_{i=r+1}^n\min\{r,d_i\} ∀r(1≤r≤n),∑i=1rdi≤r(r−1)+∑i=r+1nmin{ r,di}
证明
必要性：
考虑编号 1 ∼ r 1\sim r 1∼r的点，内部连边数不超过 1 2 r ( r − 1 ) \frac{1}{2}r(r-1) 21r(r−1)，与其他点连边总数不超过 ∑ i = r + 1 n min { r , d i } \sum_{i=r+1}^n\min\{r,d_i\} ∑i=r+1nmin{ r,di}。即得 ∑ i = 1 r d i ≤ r ( r − 1 ) + ∑ i = r + 1 n min { r , d i } \sum_{i=1}^rd_i\le r(r-1)+\sum_{i=r+1}^n\min\{r,d_i\} ∑i=1rdi≤r(r−1)+∑i=r+1nmin{ r,di}。
充分性:
用数学归纳法证明。
① n = 1 n=1 n=1时，构造平凡图即可。
②假设 n = k − 1 n=k-1 n=k−1时结论成立。当 n = k n=k n=k时，证明过程略（可以看这篇https://blog.csdn.net/hdmmblz/article/details/86506433）。
推论
数列 ( d 1 , d 2 , . . . , d n ) ( n − 1 ≥ d 1 ≥ d 2 ≥ . . . ≥ d n ≥ 0 ) (d_1,d_2,...,d_n)(n-1\ge d_1\ge d_2\ge ...\ge d_n\ge 0) (d1,d2,...,dn)(n−1≥d1≥d2≥...≥dn≥0)可简单图化当且仅当数列 s o r t e d ( d 2 − 1 , d 3 − 1 , . . . , d d 1 + 1 − 1 , d d 1 + 2 , . . . , d n ) sorted(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n) sorted(d2−1,d3−1,...,dd1+1−1,dd1+2,...,dn)可简单图化。
证明
充分性：
若 s o r t e d ( d 2 − 1 , d 3 − 1 , . . . , d d 1 + 1 − 1 , d d 1 + 2 , . . . , d n ) sorted(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n) sorted(d2−1,d3−1,...,dd1+1−1,dd1+2,...,dn)可简单图化，则将节点 1 1 1与节点 2 ∼ d 1 + 1 2\sim d_1+1 2∼d1+1连边，即可得到度数列为 ( d 1 , d 2 , . . . , d n ) (d_1,d_2,...,d_n) (d1,d2,...,dn)的简单图。
必要性:
若 ( d 1 , d 2 , . . . , d n ) (d_1,d_2,...,d_n) (d1,d2,...,dn)可简单图化为图 G G G。设 G − v 1 G-{v_1} G−v1的度数列 为 ( d 2 ′ , d 3 ′ , . . . , d n ′ ) 为(d_2',d_3',...,d_n') 为(d2′,d3′,...,dn′)，则：
∀ r ( 2 ≤ r ≤ n ) , ∑ i = 2 r d i ′ ≤ ( r − 1 ) ( r − 2 ) + ∑ i = r + 1 n min { r − 1 , d i ′ } \forall r(2\le r\le n),\sum_{i=2}^rd_i'\le (r-1)(r-2)+\sum_{i=r+1}^n\min\{r-1,d_i'\} ∀r(2≤r≤n),∑i=2rdi′≤(r−1)(r−2)+∑i=r+1nmin{ r−1,di′}
设 s o r t e d ( d 2 − 1 , d 3 − 1 , . . . , d d 1 + 1 − 1 , d d 1 + 2 , . . . , d n ) = ( d 2 ′ ′ , d 3 ′ ′ , . . . , d n ′ ′ ) sorted(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)=(d_2'',d_3'',...,d_n'') sorted(d2−1,d3−1,...,dd1+1−1,dd1+2,...,dn)=(d2′′,d3′′,...,dn′′)。则：
∀ r ( 2 ≤ r ≤ n ) , ∑ i = 2 r d i ′ ′ ≤ ∑ i = 2 r d i ′ , ∑ i = r + 1 n d i ′ ′ ≥ ∑ i = r + 1 n d i ′ \forall r(2\le r\le n),\sum_{i=2}^rd_i''\le \sum_{i=2}^rd_i',\sum_{i=r+1}^nd_i''\ge \sum_{i=r+1}^nd_i' ∀r(2≤r≤n),∑i=2rdi′′≤∑i=2rdi′,∑i=r+1ndi′′≥∑i=r+1ndi′
∴ ∑ i = 2 r d i ′ ′ − ∑ i = r + 1 n min { r − 1 , d i ′ ′ } ≤ ∑ i = 2 r d i ′ − ∑ i = r + 1 n min { r − 1 , d i ′ } ≤ ( r − 1 ) ( r − 2 ) \therefore \sum_{i=2}^rd_i''-\sum_{i=r+1}^n\min\{r-1,d_i''\}\le \sum_{i=2}^rd_i'-\sum_{i=r+1}^n\min\{r-1,d_i'\}\le (r-1)(r-2) ∴∑i=2rdi′′−∑i=r+1nmin{ r−1,di′′}≤∑i=2rdi′−∑i=r+1nmin{ r−1,di′}≤(r−1)(r−2)
因此 s o r t e d ( d 2 − 1 , d 3 − 1 , . . . , d d 1 + 1 − 1 , d d 1 + 2 , . . . , d n ) sorted(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n) sorted(d2−1,d3−1,...,dd1+1−1,dd1+2,...,dn)可简单图化。
Havel算法
可以通过度数列构造一个简单图
具体做法就是利用推论，每次把点 1 1 1和点 2 ∼ d 1 + 1 2\sim d_1+1 2∼d1+1进行连边，然后把序列重新排个序。朴素实现复杂度 O ( n 2 log n ) O(n^2\log n) O(n2logn)
京公网安备 11010502036488号