Havel-Hakimi定理(握手定理)
由非负整数构成的非增加序列s (度序列) d1、d2、…、dn ) n=2、d1=1)可以绘图，只有时间序列：
s 1: D21，D31，dd11，dd1 2，dn
变成图。 序列s1有n-1个非负整数，从s序列中的d1之后的最初的d1个频数，即d2~dd1 1 )中减去1后的数构成s1中的最初的d1的个数。
简单地说，将第一个点(度数d1 )连接到后面的d1点，使第一个点的度数得到满足，然后同样考虑以后的点。 如果后面的所有顶点都得到满足，且度数不少(没有剩馀最后一个，中间度数不为负)，则认为度序列是可绘制的。
为什么每次都要排队才能操作？ 因为这是最好的判断。 最后都变成0就好了。 中途不能出现负数。 不能判断不是增量。 例如，最后的0、1、0、1如图所示； 0，2，0，2不成图，而且有各种各样的最终情况，所以很难写出判断为不成图的代码。
从同一个可图序列创建的图并不一定是唯一的。
例题poj1659
# include iostream # include cstdio # includecstdlib # include cstring # include string # include cmath # include map # includeset # #define pii pairint，int # definellonglongintconstdoubleeps=1e-10； const int INF=1000000000； const int maxn=10 3； int ans[maxn][maxn]； int T，n； struct node{ int id，de； } x[maxn]； BOOLCMP(nodea，node b ) { return a.deb.de； }int main ()//Freopen(in1.txt )、) r )、stdin )； //Freopen(out.txt )、) w )、stdout )； scanf('%d '，t )； wile(t-- ) Scanf ) ' %d '，n )； for(intI=0； in； I ) scanf('%d '，x[i].de )； x[i].id=i 1； }memset(ans，0，sizeof ) ans )； int tn=n； bool can=1； while(TN0 ) sort ) x、x n、cmp； if(x[0].de==0) break； for(intI=1； i=x[0].de； I () if ) x[I].de0in ) x[I].de----； ans [ x [0].id ] [ x [ I ].id ]=ans [ x [ I ].id ] [ x [0].id ]=1； } else { can=false； 黑； }if(can==false ) break； x[0].de=0； tn--； }if(can==true ) (puts ) )是)； for(intI=1； i=n； I ) for(intj=1； j=n； j () if ) j==1) printf )、ans[i][j]； elseprintf('%d '，ans[i][j] )； } puts (' )； }elseputs('no )； if(t=1) puts (' )； //fclose(stdin )； //fclose(stdout )； 返回0； } View Code
转载于：https://www.cn blogs.com/zywscq/p/4819978.html