Given a list of n natural numbers d1, d2,...,dn, show how to decide in polynomial time whether there exists an undirected graph G = (V, E) whose node degrees are precisely the numbers d1, d2, · · · , dn. G should not contain multiple edges between the same pair of nodes, or “ loop” edges with both endpoints equal to the same node.

1，Havel-Hakimi定理主要用来判定一个给定的序列是否是可图的。

2，首先介绍一下度序列：若把图 G 所有顶点的度数排成一个序列 S，则称 S 为图 G 的度序列。

3，一个非负整数组成的有限序列如果是某个无向图的序列，则称该序列是可图的。

4，Havel-Hakimi定理：给定一个非负整数序列{d1,d2,...dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。

简单地说就是：

1.从小到大排序

2.最大度数n置为0，其后的n个数均减1

3.如果出现负数或所有度数全为0，则跳出，第一种情况不能简单图化，第二种可以。。。如果没出现以上两种情况，则回到第一步

举例：

实例演示：

判断序列S:=6，5，4，3，3，3，2，0 是否可图。

证：a. 删除首元素6，将除去第一个元素后面的6个元素减一，得到：S1 = 4,3,2,2,2,1,0

b.删除首元素4，将除去第一个元素后面的4个元素减一，得到：S2 = 2,1,1,1,1,0

c,删除首元素2，将除去第一个元素后面的2个元素减一，得到：S3 = 0,0,1,1,0

d.重新排序：S4 = 1,1,0,0,0

e.删除首元素1，将除去第一个元素后面的1个元素减一，得到：S3 = 0,0,0,0

则最后得到的是非负序列，证明 序列式可图的！

判断序列S:=7，6，4，3，3，3，2，1 是否可图。

证：a. 删除首元素7，将除去第一个元素后面的7个元素减一，得到：S1 = 6,3,2,2,2,1,0

b.删除首元素6，将除去第一个元素后面的6个元素减一，得到：S2 = 2,1,1,1,0,-1

最后得到的是存在负数的序列，证明 序列式不可图的！
 

1.1问题分析

  给定一串度d1.d2…dn，在多项式时间内，使得判断是否构成一个图：

    且，限制条件如下：

（1）不能有多条边连接同一个节点

（2）不能成环（自己环自己）

即要求为简单图，根据要求我们可以将原序列按度的大小，从大到小进行排列，依次记为d1,d2,…,dn;删除首元素之后，将其后的每个度减一，若出现为负数，则不可成图；当首元素为0时，重新进行排序，重复以上操作。记整个序列为D

贪心选择：每次选择 最大度进行处理

最优子结构：除去最大度之后的序列

1.2 pseudo-code

bool HavelHakimi(int n)
{
    for(i = 0;i < n-1;++i)
    {
        sort(arr+i,arr+n,greater<int>());
        if(arr[i] + i >= n) return false;
        /*
        前面的i个顶点的度数已经足够了，现在剩余n-i个顶点，
        现在从这n-i个顶点里面找出一个顶点它的度数为arr[i]，
        arr[i]就代表与这个顶点相连的顶点个数，必然有arr[i]<n-i成立。
        */
        for(j = i+1;j <= arr[i]+1;j++)
        {
            arr[j]--;
            if(arr[j] < 0) return false;
        }
    }
    if(arr[n-1] != 0) return false;
    return true;

1.3时间复杂度分析

    for循环中间套一个排序和for循环

     O (n 2 logn)

1.4 算法正确性证明

     该算法每次都寻找当前最大度节点，为了后面有足够多节点来和该度相匹配。该算法排除了如下不能构成简单图的条件：度数总和不为偶数，这是能构成图的充要条件；最大的度数超过节点数，说明该节点必然存在环或平行边；连接过程出现了负数度数的点，表示连接了孤立节点。并且因为任意的一个简单图都能转换成每个节点连接的都是度数不小于它的节点的简单图，所以算法正确。