【Havel 定理】Degree Sequence of Graph G

【题目链接】

http://acm.hdu.edu.cn/showproblem.php?pid=2454

【别人博客粘贴过来的】

博客地址:https://www.cnblogs.com/debugcool/archive/2011/04/23/HDOJ2454.html


一句话,顶点的度序列 Havel 定理~

定义:给出一个无向图的顶点度序列 {dn},要求判断能否构造出一个简单无向图。

分析:

贪心的方法是每次把顶点按度大小从大到小排序,取出度最大的点Vi,依次和度较大的那些顶点Vj连接,同时减去Vj的度。连接完之后就不再考虑Vi了,剩下的点再次排序然后找度最大的去连接……这样就可以构造出一个可行解。
    判断无解有两个地方,若某次选出的Vi的度比剩下的顶点还多,则无解;若某次Vj的度减成了负数,则无解。
至于什么是Havel定理,上面这个构造过程就是了~

定理的简单证明如下:
    (<=)若d'可简单图化,我们只需把原图中的最大度点和d'中度最大的d1个点连边即可,易得此图必为简单图。
    (=>)若d可简单图化,设得到的简单图为G。分两种情况考虑:
        (a)若G中存在边,则把这些边除去得简单图G',于是d'可简单图化为G'
        (b)若存在点Vi,Vj使得i=dj,必存在k使得(Vi, Vk)在G中但(Vj,Vk)不在G中。这时我们可以令GG=G-{(Vi,Vk),(V1,Vj)}+{(Vk,Vj),(V1,Vi)}。GG的度序列仍为d,我们又回到了情况(a)。


【自己的理解】

真的非常感谢上面这位大哥提供的博客解析,不然我都自闭一下午了。

其实如果单纯想的话我只是想到匹配罢了,根本想不到居然可以有这样的定理。

这个Havel定理,其实是一个判断依据。

1、按照度数从大到小排序,然后依次建边。

2、建边的过程就是以该点为起点,其余都是它的目标点,然后大家都度减一

注意!!!!一定是前k大的。

最后就是判断这个度数组,是否为全零。

下面就是代码:

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std ; const int N = 1e3 + ;
int a[N] ; int main()
{
int T , n ;
for ( cin >> T ; T ; T-- ){
int tot = , edge = ;
cin >> n ;
//for( int i=1;i<=n;i++ ) cin >> a[i] ; for( int i=;i<=n;i++ ){
cin >> a[i] ;
tot += a[i] ;
} // 判断 入度和出度
if( tot & ) {
printf("no\n");
continue;
}
// 排序,从大到小
sort ( a+, a++n , [](int u,int v){return u>v;} ); bool flag = true ;
for(int i = ; flag && i <= n ; i++ ){
for(int j=i+ ; a[i] && j<=n ;j++ ){
if( a[j] == ) continue;
a[i] -- ;
a[j] -- ;
}
//注意每次操作完都需要取前K大的.
sort( a+i+ , a++n ,[](int u,int v){return u>v;} ) ;
}
for(int i=;i<=n;i++){
//cout << a[i] << " ";
if( a[i] != ){
flag = false ;
}
}
if( flag ) puts("yes");
else puts("no");
}
return ;
}

Degree Sequence of Graph G

上一篇:POJ1659 Frogs' Neighborhood(Havel定理)


下一篇:UESTC 913 握手 Havel定理+优先队列