可图和Havel-Hakimi定理

2015/1/20 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 ≤ iN)。如果湖泊LiLj之间有水路相连,则青蛙FiFj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ...,xn,请你给出每两个湖泊之间的相连关系。

Input

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

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;
}

 注意

这个题目是Special Judge,也就是说这个题的答案是有多种的。这个是由Havel-Hakimi定理导致的,由于可图是由度数重构图,这个过程构建的图可能不是唯一的