电子科技大学图论作业3：填空与选择题详解

本资源是一份电子科技大学图论课程的作业题目，由王老师分发，旨在帮助学生巩固图论基础知识。作业包括填空题和不定项选择题，涵盖了多个图论的核心概念。 1. 填空题部分涉及到的知识点： - 完全图K2n中的完美匹配数量：题目询问的是K2n（2n个顶点的完全图）的完美匹配数目，这需要理解完全图的性质和完美匹配的概念，即每一对不相邻的顶点之间恰好有一条边的匹配总共有C(n,2)种，对于K2n来说，由于每个顶点都有n-1个不相邻的顶点，所以完美匹配的数量为(n-1)×n/2。 - 超方体Q6的最小覆盖：涉及图的覆盖理论，超方体Q6的最小覆盖是指用最少的点数覆盖所有边，对于超立方体，这个问题通常与顶点的独立集相关。 - 图Km,n的最小覆盖：这是一个关于图的最小覆盖问题，通常需要考虑图的结构和边的连接性。 - 完全图K60和K61的一因子分解：一因子是指图中的边可以分为若干组，每组恰好包含图的所有顶点，K60和K61的分解数目取决于它们的连通性和是否有哈密尔顿圈的存在。 - 图的荫度和面数：荫度指的是图中任意顶点的度数，平面图的面数与顶点数、边数和连通分支有关，可以通过欧拉公式来计算。 - 平面图的平面化：如果一个图是可平面化的，意味着它可以被嵌入到平面上，删去边的数量与图的特征有关。 - 面数的计算：根据给定条件，如连通平面图的顶点和边数，可以应用欧拉公式或平面图的性质来确定面数。 - 大平面图和极大外平面图：极大平面图和极大外平面图的面数关系是固定的，极大平面图的面数等于顶点数减1，而极大外平面图的内部面数等于外部面数。 2. 不定项选择题涉及的知识点： - 非平凡树的性质：树的特征包括至少一个叶子节点（对应于完美匹配）、无环（即无圈）、荫度至少为1（非平凡），以及对偶图的定义。 - 完美匹配和三正则图的关系：三正则图意味着所有顶点的度数都相同，这与是否存在完美匹配及割边相关联。 - 1-因子和2-因子：1-因子是图中的边可以分为若干组，每个组恰好包含所有顶点，而2-因子则是包含所有顶点的环，哈密尔顿圈是特殊的一种2-因子。 - 完全图的1-因子和2-因子：判断特定大小的完全图是否包含1-因子和2-因子，需要考虑图的结构和正则性。 - 可1-因子分解的性质：这涉及图的连通性、是否有割边以及分解的可能性。 这些题目旨在测试学生对图论基本概念的理解，包括图的结构、连通性、覆盖、匹配、正则图、平面图的性质以及1-因子和2-因子等，同时考察了学生对定理和公式运用的能力。通过解答这些问题，学生能够深化对图论理论的理解，并提升解决实际问题的能力。