题目

(1,2,2,3,5,5)可以构成简单图的度数序列。（ ）A对B错

{1,2,2,3,5,5}可以构成简单图的度数序列。（             ）

A对

B错

题目解答

答案

要确定一个序列是否可以构成简单图的度数序列，可以使用Havel-Hakimi算法，该算法通过反复验证和减少度数来判断给定的度数序列是否有效。具体步骤如下：

    初始序列：{1, 2, 2, 3, 5, 5}

    取出最大度数5，减去1：{2, 1, 1, 2, 4}

    排序：{1, 1, 2, 2, 4}

    取出最大度数4，减去1：{0, 0, 1, 1, 3}

    排序：{0, 0, 1, 1, 3}

    取出最大度数3，减去1：{-1, -1, 0, 0, 2}

在此过程中，出现了负度数{-1, -1, 0, 0, 2}，因此该序列无法构成简单图的度数序列。

因此，答案是：

B. 错

解析

考查要点：本题主要考查学生对简单图的度数序列判定方法的掌握，特别是Havel-Hakimi算法的应用。

解题核心思路：
通过Havel-Hakimi算法对给定的度数序列进行递归处理，判断是否能构造出合法的简单图。关键在于每次取出最大度数后，是否会导致出现负数或无法继续操作的情况。

破题关键点：

  1. 排序并处理最大度数：每次将序列降序排列，取出最大度数$d$，并对剩余的前$d$个数依次减1。
  2. 终止条件：若过程中出现负数，则序列无效；若最终序列全为0，则有效。

Havel-Hakimi算法步骤

初始序列

原序列：$\{1, 2, 2, 3, 5, 5\}$
降序排列：$5, 5, 3, 2, 2, 1$

第一次处理

  1. 取出最大度数：$d = 5$
  2. 剩余序列：$5, 3, 2, 2, 1$
  3. 前5个数减1：$5-1=4$, $3-1=2$, $2-1=1$, $2-1=1$, $1-1=0$
  4. 新序列：$\{4, 2, 1, 1, 0\}$
  5. 重新降序排列：$4, 2, 1, 1, 0$

第二次处理

  1. 取出最大度数：$d = 4$
  2. 剩余序列：$2, 1, 1, 0$
  3. 前4个数减1：$2-1=1$, $1-1=0$, $1-1=0$, $0-1=-1$
  4. 新序列：$\{1, 0, 0, -1\}$
  5. 出现负数：$-1$，算法终止。

结论：由于过程中出现负数，原序列无法构成简单图。