1.图的度序列
定义：如果V(G)={v1，v2,v3,...,vp};则称非负整数序列(d(v1),d(v2),d(v3),...,d(vp))为图G的度序列.(定义中的图指广义的图,含有多重边或环).
Havel定理:我们把序列排成不增序，即d1>=d2>=...>=dn，则d可简单图化当且仅当d'=(d2-1, d3-1, ... d(d1+1)-1, d(d1+2), d(d1+3), ... dn)可简单图化。这个定理写起来麻烦，实际上就是说，我们把d排序以后，找出度最大的点(设度为d1)，把它和度次大的d1个点之间连边，然后这个点就可以不管了，一直继续这个过程，直到建出完整的图，或出现负度等明显不合理的情况。
boolean havel(){
if(sum%2!=0||max>=n)
return false;//握手定理
for(int i=0;i<n;i++){
Arrays.sort(vertex,i,n); //由大到小
int a=vertex[i].id;
int m=vertex[i].dgr;
if(m>=n-i)
return false;
if(m==0)
return true;
for(int j=1;j<=m;j++){
int b=vertex[i+j].id;
map[b][a]=map[a][b]=1;
if(--vertex[i+j].dgr<0)
return false;
}
}
return true;
}
题目两道: