[国庆 青岛正睿]某些图论知识 笔记

不知道有什么用...但既然dls讲了就记记吧。

度数序列

对于无向图，\(d_1,d_2,...,d_n\)为每个点的度数。
有\(d_1+d_2+...+d_n=2e\)（每条边被计算两次）。
有偶数个度数为奇数的点。

Havel–Hakimi算法

给定一个由有限多个非负整数组成的度数序列，是否存在一个简单图使得其度数序列恰为这个序列。
令\(S=(d_1,d_2,...,d_n)\)为有限多个非负整数组成的非递增序列。
\(S\)可简单图化当且仅当有穷序列\(S’=(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)\)只含有非负整数且是可简单图化的。
序列\(S\)可简单图化是指存在一个无向图（无重边无自环），使得其度数序列恰为\(S\)。
（好像就是非常显然的东西。。）

Erd?s–Gallai定理

令\(S=(d_1,d_2,...,d_n)\)为有限多个非负整数组成的非递增序列。
\(S\)可简单图化当且仅当这些数字的和为偶数，且\[\sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^m\min(d_i,k)\]

对于任意\(1\leq k\leq n\)都成立。
也不难理解。对前\(k\)个点分配度数，除了两两能连\(\frac{k(k-1)}{2}\)条边外，剩下的度数由后面点的度数补。
因为\(d_i\)非递增，从小到大枚举\(k\)，维护\(d_i\)后缀与\(k\)取\(\min\)的和。就可以\(O(n)\)判断了。

[国庆 青岛正睿]某些图论知识 笔记

原文：https://www.cnblogs.com/SovietPower/p/9757651.html