Havel

HDU 2454 Degree Sequence of Graph G

Havel定理判定简单图

被上下界网络流烦傻了,暂时不想写代码太长的题。

虽然是一道水题,但也是建立在一定理论基础上的。

再科普一下简单图,没有重边没有自环的图就是简单图。区别有向图和无向图,也就是说,有向图的反向边不算重边。

给定一个非负整数序列{dn},若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。进一步,若图为简单图,则称此序列可简单图化

可图化的判定:

\( \sum_{i=1}^{n}d_{i} mod 2 == 0 \) 。关于具体图的构造,我们可以简单地把奇数度的点配对,剩下的全部搞成自环。

可简单图化的判定(Havel定理):

把序列排成不增序,即 \( d_1 \geq d_2 \geq \ldots \geq d_n \),则d可简单图化当且仅当
\( d' = \left{ d_2-1 , d_3-1 \ldots d_{d_1+1}-1 , d_{d_1+2} , d_{d_1+3} , \ldots d_n \right} \) 可简单图化。简单的说,把d排序后,找出度最大的点( 设度为\( d_1\) ),把它与度次大的d1个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况。

题意:
题目很长……没怎么看,就是给你几个点,再给你每个点的度数,问你能否构成简单图。

思路:
裸题,按照定理模拟一下即可。

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;

int deg[maxn];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        bool flag = true;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", deg + i);
            sum += deg[i];
            if (deg[i] >= n)
                flag = false;
        }
        if (sum & 1)
            flag = false;
        if (!flag) {
            puts("no");
            continue;
        }
        for (int i = 0; i < n; i++) {
            sort(deg + i, deg + n, greater<int>());
            int d = deg[i];
            if (d < 0 || i + d >= n) {
                flag = false;
                break;
            }
            for (int j = 1; j <= d; j++)
                deg[i + j]--;
        }
        puts(flag ? "yes" : "no");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注