大门|大门CS 2010 |问题28

简单图的度序列是图中节点的度按降序排列的序列。下列哪个序列不能是任何图的度序列？

(I) 7, 6, 5, 4, 4, 3, 2, 1
(II) 6, 6, 6, 6, 3, 3, 2, 2
(III) 7, 6, 6, 4, 4, 3, 2, 2
(IV) 8, 7, 7, 6, 4, 2, 1, 1 

（A） 一和二 （B） 三、四 （C） 仅限IV （D） 二、四 答复: （D） 说明： 解决这个问题的通用算法或方法是

1：程序isV alidDegreeSequence（L）

2:对于列表中的n，我要

3：如果L在当前元素旁边没有n个元素，那么返回false

4：将列表中接下来的n个元素减量1

5：按度顺序排列，即按降序排列

6：如果列表中的任何元素变为负数，则返回false

7：返回true

这种方法的基本原理来自简单图的性质。枚举f alse返回，1）如果L在当前1之后没有足够的元素，或2）如果列表中的任何元素变为负数，则表示没有足够的节点以简单的图形方式容纳边，这将导致违反简单图的两个条件之一（两个节点之间没有自循环和多条边），如果没有其他条件的话。

看见 https://www.geeksforgeeks.org/data-structures-and-algorithms-set-25/

这个解决方案是由 维内特·普斯瓦尼。

另一个：

度序列d1，d2，d2。如果非负整数的dn是图的度序列，则它是图的。现在我们引入一个强大的工具来确定特定序列是否是哈维尔和哈基米的图形

哈维尔-哈基米定理：

→ 根据这个定理，设D是序列d1，d2，d2。dn与d1≥ d2≥ d2≥ . . . n的dn≥ 2和di≥ 0

→ 那么D0是通过以下方式获得的序列：

→ 丢弃d1，以及 → 从D的下一个d1条目中减去1。 → 这就是度序列D0应该是：d2-1，d2-1，d3-1，dd1+1-1，dn → 那么，D是图形的当且仅当D0是图形的。

现在，我们将这个定理应用于给定的序列：

选项I）7,6,5,4,4,3,2,1→ 5,4,3,3,2,1,0 → 3,2,2,1,0,0 → 1,1,0,0,0 → 0,0,0,0所以它是图形化的。

选项II）6,6,6,6,3,3,2,2→ 5,5,5,2,2,1,2（按升序排列）→ 5,5,5,2,2,2,1 → 4,4,1,1,1,0 → 3,0,0,0,0 → 2，-1，-1，-1,0但是d（顶点的度数）是非负的，所以它不是图形。

选项III）7,6,6,4,4,3,2,2→ 5,5,3,3,2,1,1 → 4,2,2,1,1,0 → 1,1,0,0,0 → 0,0,0,0所以它是图形化的。

选项IV）8,7,7,6,4,2,1,1，这里顶点的度数是8，顶点的总数是8，所以这是不可能的，因此它不是图形化的。

因此，只有选项I）和III）是图形顺序，答案是选项D

这个解决方案是由 拉德瓦马尔。 这个问题的小测验