"该资源是一份电子科技大学研究生的期末考试试卷,涵盖了图论及其应用的相关知识,包括填空题和单项选择题,涉及了图的性质、度数序列、连通性、哈密尔顿图、欧拉图、平面图、特征值、独立数、覆盖数等多个概念。"
在图论领域,这张试卷考察了以下几个核心知识点:
1. **图的度数**:图中每个顶点的度数是与其相邻的边的数量。最小度和最大度分别代表图中所有顶点中度数最小和最大的值。例如,问题1指出,如果一个n阶单图的最小度是d,那么其补图的最大度就是n-1-d。
2. **图的乘积**:问题2提到了图的积图,两个图的积图的顶点数是原图顶点数的乘积,边数则是原图中对应顶点对之间是否存在边的乘积。
3. **邻接矩阵**:邻接矩阵是表示图中顶点之间关系的矩阵,问题3提到推广邻接矩阵,其非对角线元素表示路径的数目。
4. **完全图**:完全图K_n的所有顶点之间都有边相连。问题4指出,完全图K_n的邻接矩阵的最大特征值是n。
5. **单图的不等价类**:问题5提到了不同构的3阶单图共有4个,这是指3个顶点的不同连接方式。
6. **森林与树的性质**:森林是无环的图,问题6讨论了具有b个分支的阶图的边数。对于树,问题7指出k阶树的点连通度、边连通度以及点色数和边色数。
7. **连通性**:问题8提到在连通图中,任意两点间至少有一条不相交路径。
8. **度极大非哈密尔顿图**:5阶度极大非哈密尔顿图是指具有最大度数但不包含哈密尔顿循环的图,问题9要求填写这类图的例子。
9. **图的分解**:问题10讨论了如何将完全图分解为边不相交的一因子(完美匹配)的并。
10. **平面图与外平面图**:问题11涉及到平面图的面数,以及极大平面图和极大外平面图的性质。
11. **图的独立数和覆盖数**:问题12讨论了完全偶图的点独立数(不相邻的顶点数)和点覆盖数(最少的顶点数,使得每个边都与至少一个顶点相邻)。
12. **树的度数和结构**:问题13涉及完全元根树的度数,元根树是一种特殊的树,所有叶子的度数相同。
13. **图的定向**:问题14讨论了单图定向后可能产生的不同定向图的数量。
14. **图的度序列**:选择题部分考察了度序列的性质,例如不是某图的度序列的选项、树的定义、欧拉图的识别以及哈密尔顿图的条件。
这些题目覆盖了图论的基本概念和性质,对于理解和研究图论的学生来说是非常有价值的练习。