havel定理

定义：给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化
具体操作方法：

• 1.我们把所有度数列进行升序排序
• 2.从最大的度数开始， 把当前最大的度数去掉， 其他的度数-1
• 3.判断当剩下的度数中有负数的存在\(则无法可简单图化\) ，反之， 没有的话继续进行如果\(结束都没有出现负数就代表可以可图化\)
  例子一：

给出序列序列：

4 7 7 3 3 3 2 1
降序排序

7 7 4 3 3 3 2 1
删除第一个数字7，将其后7个数都减去1,并重新排序

6 3 2 2 2 1 0
重复步骤

2 1 1 1 0 -1
发现有负数，则这个序列不能组成简单图

例子二：

5 4 3 3 2 2 2 1 1 1
删除数字5，将其后5个数都减去1，并重新排序

3 2 2 2 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0
…以此类推，直至

0 0 0
所以可以组成简单图

havel定理

原文：https://www.cnblogs.com/gaohaoy/p/13166346.html