电子科技大学2010年图论及其应用期末考试含答案

"这是一份2010年春季学期的图论及其应用课程期末考试试卷，包含了填空题、单项选择题以及解答题，涵盖了图的性质、谱理论、连通度、度序列、欧拉图、哈密尔顿图、完美匹配等多个知识点。" 1. 图的基本概念: 图是由顶点和边构成的数据结构，可以用来表示各种关系。题目中提到了自补图、联图等概念，自补图是指通过将原图中所有边取反得到的新图，联图则是将两个图的所有顶点合并，并连接两图中对应顶点。 2. 度序列: 度序列是一个图中所有顶点的度按降序排列的结果。非负整数序列不一定都是图的度序列，必须满足条件，即度序列的和等于边数的两倍。 3. 谱理论: 谱理论研究的是图的特征值，即图的邻接矩阵或对角化矩阵的特征值，这里提到的"G的谱"就是指这个图的特征值集合。 4. 连通度: 图的点连通度和边连通度分别表示最小的点割集和边割集的大小，题目中G2的点连通度与边连通度均为3。 5. 度极大非H图族: 在图论中，度极大图是指在不增加任何边的情况下，无法再增加顶点的度数。对于n=5的度极大非H图族，需要找出所有可能的满足条件的图。 6. 完美匹配: 完美匹配是图的一种特殊匹配，其中图中的每个顶点都恰好被一条边覆盖。B选项指出正则偶图（所有顶点度数相同的偶图）存在完美匹配是正确的。 7. 强连通图: 强连通图是有向图中任何两个不同的顶点都互相可达的图。题目中提供了选择题，让判断哪个是有向图是强连通图。 8. 欧拉图与哈密尔顿图: 欧拉图是指可以从任意顶点出发走遍所有边且不重复经过任何顶点的图；哈密尔顿图则是指可以从任意顶点出发走遍所有顶点且不重复边的图。C选项正确，因为有些图既不是欧拉图也不是哈密尔顿图。 9. 匈牙利算法: 匈牙利算法主要用于寻找图中的最大匹配，尤其适用于偶图，但并非只能用于求完美匹配。 10. 最小生成树: 最小生成树是图中边权重之和最小的树形子图，覆盖了图的所有顶点。题目给出了一个具体的最小生成树构建问题。 11. k色多项式: k色多项式是图论中的一种概念，表示一个图可以用k种颜色进行着色的所有方法的总数。题目要求求出给定图的k色多项式。 12. 边赋权完全图的最优解: 对于边赋权完全图，求最优解通常涉及到寻找最小权重匹配或者最大权重匹配，具体取决于问题的上下文。 这份试卷展示了图论的多个核心概念，包括图的结构特性、图的性质、图的染色问题以及图的匹配理论等，这些都是图论研究的基础内容。通过解答这些问题，学生能够深入理解这些概念并锻炼解决实际问题的能力。