探讨3阶单图、连通性质与图论基础问题

在本次电子科技大学研究生图论及其应用的期末考试试卷中，涵盖了多个图论的基本概念和定理。以下是一些重要的知识点概述： 1. **单图的性质**： - 不同构的3阶单图的个数是题目5中要求的，尽管具体数值未给出，这涉及到图的结构分析，通常需要根据图的不同属性如顶点数、边数以及是否具有特定的同构性来确定。 2. **森林与边数**： - 题目6询问n阶图G如果是一个具有k个分支的森林，其边数mG可以通过公式计算，因为森林是由互不相交的树构成的，每个树都是一个分支，所以边数等于树的数量减去1，即mG = k - 1。 3. **树的连通性和度数**： - 题目7涉及树的连通性指标，n阶树的点连通度、边连通度和点色数分别是图论中的基本概念。点连通度指的是从任一节点出发都能到达其他所有节点的最少路径数，对于树来说通常是n-1；边连通度是指所有节点通过边连接形成连通图所需的最小边数，也是n-1；点色数是给定图最少需要多少种颜色使相邻的点颜色不同，对于树是2；边色数与最大度数有关，具体计算依赖于图的结构。 4. **连通性与内点不交路**： - 图G是k连通的，意味着任何两个顶点之间都有至少k条路径，且这些路径互不相交除了起点和终点。题目8指出任意两点间至少有k条内点不交路。 5. **图论的特殊结构**： - 提及了5阶度极大非哈密尔顿图族，这是一个关于是否存在简单图中不能包含所有顶点的哈密尔顿回路的问题，5阶图族可能包括特定的结构组合。 6. **平面图的性质**： - 面数、顶点位置和外平面图是图论中处理平面嵌入的概念。题目涉及面数计算，以及n阶极大平面图和外平面图的特点，这些都需要根据欧拉公式进行推算。 7. **图的分解和独立数**： - 完全图的分解和独立数问题，如题目10中提到的完全图的边不相交的一因子分解，以及题目12中完全偶图的点独立数和点覆盖数。 8. **树的度数和分支点**： - 完全m元根树是一种特殊的树形结构，题目13涉及其树叶数量、分支点数量与总度数的关系。 9. **定向图的生成**： - 最后，题目14讨论了单图定向后产生的不同定向图数量，这涉及到图的有向图表示和图的遍历方式。 这些知识点涵盖了图论的基础概念，如图的度数、连通性、平面性、图的分解和定向等，是期末考试中可能考察的重要内容。具体数值和解答需参考教材或进一步学习图论理论。