可图和Havel-Hakimi定理

2015/01/20 12:56 pm posted in 算法&数据结构

可图（Graphic）

什么是可图，那需要先说一下度序列。

度序列是把图的多有顶点度数排列成一个序列s，则称s为图G的度序列。

度序列可以是按照顶点的顺序排列，也可以按照递增、递减的顺序排列。所谓的可图，是建立在度序列的基础上的。

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

说白了，就是如果一串度序列可以逆向生成出图，就是可图的。而判断一个序列是否是可图的，则由Havel-Hakimi定理判断。

Havel-Hakimi定理

由非负整数组成的非增序列s：d1，d2，...，dn（n>=2，d1>=1）是可图的，当且仅当序列：

s1:d2 - 1，d3 - 1，...，dd1+1 - 1，dd1+2，...，dn

是可图的。序列s1中有n-1个非负整数，s序列中d1后的前d1个度数（即d2~dd1+1）减1后构成s1中的前d1个数。

说白了就是先把第一个点（度数为d1）连线到后面d1个点，保证第一个点度数满足，然后再以此类推考虑后面的点。如果后面所有顶点满足并且度数不多不少（最后不剩，过程中没有度数为负数），即可认为，度序列是可图的。

青蛙邻居问题

POJ1659 Frogs' Neighborhood

Description

未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖)，每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连，则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ...,xn，请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行，第一行是整数N(2 1, x2,..., xn(0 ≤ xi ≤ N)。

Output

对输入的每组测试数据，如果不存在可能的相连关系，输出"NO"。否则输出"YES"，并用N×N的矩阵表示湖泊间的相邻关系，即如果湖泊i与湖泊j之间有水路相连，则第i行的第j个数字为1，否则为0。每两个数字之间输出一个空格。如果存在多种可能，只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int G[20][20];
struct Node
{
    int dnum;
    int no;
}d[20];

int cmp(Node a,Node b)
{
    return a.dnum > b.dnum;
}

int main()
{
    int N;
    cin >> N;

    while(N--)
    {
        bool flag = 1;
        memset(G,0,sizeof(G));

        int n;
        cin >> n;

        for(int i = 0;i < n;i++)
        {
            cin >> d[i].dnum;
            d[i].no = i;
        }

        for(int i = 0;i < n;i++)
        {
            sort(&d[i],&d[i] + n - i,cmp);
            int last = d[i].dnum;
            d[i].dnum = 0;
            if(last > n - i)
            {
                flag = 0;
                break;
            }

            for(int j = i + 1;j <= i + last;j++)
            {
                if(d[j].dnum - 1 >= 0)
                {
                    G[d[i].no][d[j].no] = 1;
                    G[d[j].no][d[i].no] = 1;
                    d[j].dnum -= 1;
                }else
                {
                    flag = 0;
                }
                if(!flag)
                    break;
            }
            if(!flag)
                break;
        }

        if(flag)
        {
            for(int i = 0;i < n;i++)
                if(d[i].dnum > 0)
                    flag = 0;
        }

        if(!flag)
            cout << "NO" << endl;
        else
        {
            cout << "YES" << endl;

            for(int i = 0;i < n;i++)
                for(int j = 0;j < n;j++)
                    cout << G[i][j] << (j < n - 1 ? ' ' : 'n');
        }

        if(N)
            cout << endl;
    }
    return 0;
}