# 关于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.

```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’```

104 篇文章41 人订阅

0 条评论

## 相关文章

11320

### SQL, PL/SQL 之NUMBER数据类型

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

10620

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

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

356100

16860

35050

### Leetcode 239. Sliding Window Maximum

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

21750

12730

641150

10030

354110