本文主要是介绍poj-1659-Frogs' Neighborhood-havel定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。
可图化的判定：d1+d2+……dn=0（mod 2）。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。
可简单图化的判定（Havel定理）：把序列排成不增序，即d1>=d2>=……>=dn，则d可简单图化当且仅当d’={d2-1，d3-1，……d(d1+1)-1， d(d1+2)，d(d1+3)，……dn}可简单图化。简单的说，把d排序后，找出度最大的点（设度为d1），把它与度次大的d1个点之间连边，然后这个点就可以不管了，一直继续这个过程，直到建出完整的图，或出现负度等明显不合理的情况。
havel定理：
1，找到序列最大的点。
2，最大点连次大点，然后再连次次大点，一直连到最大点个。被连接的点的序列-1。
3，在建图过程中如果存在出现负度，或者最大点连不完的情况，那么输出'NO‘
#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
using namespace std;
#define maxm 110*110
#define maxn 110
#define eps 0.000001
#define zero(x) ((fabs(x)<eps?0:x))
#define INF 99999999
struct list
{int x;int ip;friend bool operator < (const list &a,const list &b){return a.x>b.x;}
}num[14];
int maps[11][11];
int main()
{int T,i,j,n;scanf("%d",&T);while(T--){memset(maps,0,sizeof(maps));scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&num[i].x);num[i].ip=i;}int leap=0;for(i=1;i<=n;i++){sort(num+i,num+n+1);// for(j=i;j<=n;j++)cout<<num[j].x<<" ";// cout<<endl;for(j=i+1;num[i].x!=0;j++){if(j>n||num[i].x<0){leap=1;break;}num[i].x--;num[j].x--;maps[num[i].ip][num[j].ip]=1;maps[num[j].ip][num[i].ip]=1;}}if(leap)cout<<"NO"<<endl;else{cout<<"YES"<<endl;for(i=1;i<=n;i++){for(j=1;j<=n;j++){cout<<maps[i][j];if(j!=n)cout<<" ";else cout<<endl;}}}cout<<endl;}return 0;
}这篇关于poj-1659-Frogs' Neighborhood-havel定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
