关于Havel算法判断度数序列能否构成简单图的思考

问题描述:

Given a list of n natural numbers d1, d2,...,dn, show how to decide in polynomial time whether there exists an undirected graph G = (V, E) whose node degrees are precisely the numbers d1,d2,···,dn. G should not contain multiple edges between the same pair of nodes, or “ loop” edges with both endpoints equal to the same node.

该问题是从度数序列中判断是否能构成简单图。首先统计度数总和是否为偶数,这是成图的充要条件。然后根据Havel定理,假设度数序列中含有n个数,对应着n个节点,而第i个节点的度数为di。接着将节点按度数大小降序排序,之后选择第一个节点,如果该节点度数比n大,则不能构成简单图;否则将第一个节点后的d1个节点逐个度数减一,这一过程可以理解为将该节点和较大的d1个节点连接,在连接的过程中如果发现某节点的度数小于0,则不能构成简单图。考虑完第一个节点后以后将不再考虑,剩下的节点重新按照度数降序排序,n = n -1,重复以上步骤。

以下是伪代码:

total_degree = sum(d)
if !total_degree % 2:
	print 'no graph'
	return -1
n = length(d)
while(n):
	sort(d)
	d1 = d[0]
	if d1 > n:
		print 'no simple graph'
		return -1
	for i = 1 to d1:
		d[i] -= 1
		if d[i] < 0:
			print 'no simple graph'
			return -1
	d[0] = 0
	n -= 1
print 'the sequence can construct a simple graph’

正确性证明:

算法每次都选取最大度数的点是为了后面有足够多的点可以抵消该点的度数,首先考虑该算法排除的情况是否确实不能构成简单图,其排除条件包括度数总和不为偶数、最大的度数超过节点数以及连接过程出现了负数度数的点,第一个是能构成图的充要条件,而第二个条件说明该节点必然存在环或平行边,第三个条件表示连接了孤立节点,这是不允许的,所以图中必然出现了环或平行边。所以该算法排除的情况都是不能构成简单图的情况。

那么是否存在该算法成功确定的序列却不能构成简单图的情况呢?这显然是不可能,因为任意的一个简单图都能转换成每个节点连接的都是度数不小于它的节点的简单图,例如,首先随机找出一个节点,连接其他d1个节点,之后就不再考虑该节点,然后在剩下的节点中找度数最大的节点,给它分配第二大的度数,即与d2个节点连接,如此类推,直到分配完所有度数。

综上所述,该算法是正确的。

复杂度分析:

一个遍历中嵌套一个排序,所以算法的时间复杂度为O(n2logn)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏达摩兵的技术空间

js实现01数字矩阵

11320
来自专栏乐沙弥的世界

SQL, PL/SQL 之NUMBER数据类型

    NUMBER数据类型在Oracle中使用的较为广泛,可以存储零值,正负数,以及定长数,对于这个数据类型有个几个概念要搞清,否则容易搞混,下面给出具体描述...

10620
来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

356100
来自专栏LeetCode

LeetCode 74 & 240 Search a 2D Matrix I,II

一个矩阵,每一行都是递增顺序,并且下一列比上一列的最大值要大。给定一个目标值,判断这个target是否在这个矩阵中。

16860
来自专栏智能算法

自动还原魔方算法数据结构

来自:CSDN博客 作者:寸辰 链接:http://blog.csdn.net/cun_chen/article/details/50261787(点击尾部阅读...

35050
来自专栏计算机视觉与深度学习基础

Leetcode 239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from t...

21750
来自专栏C语言及其他语言

【每日一题】1426: [蓝桥杯][历届试题]九宫重排

如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面...

12730
来自专栏聊聊技术

原 初学算法-分治法求平面上最近点对(Cl

641150
来自专栏数据结构与算法

洛谷P1730 最小密度路径(floyd)

很显然的一个dp方程\(f[i][j][k][l]\)表示从\(i\)到\(j\)经过了\(k\)条边的最小权值

10030
来自专栏数据结构与算法

P1418 选点问题

题目描述 给出n个点,m条边,每个点能控制与其相连的所有的边,要求选出一些点,使得这些点能控制所有的边,并且点数最少。同时,任意一条边不能被两个点控制 输入输出...

354110

扫码关注云+社区

领取腾讯云代金券