电子科技大学2018级图论课程测试：图论作业与连通性

"电子科技大学2018级研究生图论课程的四次测试题之一，图论作业2，包括填空题和不定项选择题，涉及图的连通性、欧拉路径、割点与割边等相关概念。" 这篇资料详细介绍了图论中的多个关键概念，适用于电子科技大学2018级研究生的图论及应用课程。以下是这些知识点的详细解释： 1. **连通性**： - **点连通度** (κ(G))：图G中最小的顶点集大小，该集的移除会导致图不连通。 - **边连通度** (λ(G))：图G中最小的边集大小，移除后导致图不连通。 - **完全图** (Kn)：所有顶点之间都有边相连的图，κ(G)=λ(G)=n-1。 2. **割点与割边**： - 割点：移除后导致图不连通的顶点。 - 割边：移除后导致图不连通的边。 - 有割边的图不一定有割点，反之亦然，但割点至少属于图的两个连通分量。 3. **欧拉路径与欧拉回路**： - **欧拉回路**：从一个顶点出发并回到同一顶点，经过每条边恰好一次的路径。 - **欧拉路径**：从一个顶点出发但不一定回到同一顶点，经过每条边恰好一次的路径。 - 完全偶图Km,n(m,n均为偶数)有欧拉回路，最优欧拉环游包含所有边。 4. **树的性质**： - 非平凡树至少有一个割点，因为树是一棵树形结构，移除一个节点可能使图不连通。 - 树的点连通度和边连通度都为1，因为树本身就是连通的且只需移除一个边即可分离成两部分。 5. **图的宽度与直径**： - **宽度**：通常指树剖的宽度或图的2宽等，这里提到的"2宽"可能指的是树剖的宽度。 - **直径**：图中任意两点间最长路径的长度。 - 长度为n(n≥3)的圈的2宽直径为n，完全图Kn的3宽直径为n-1。 6. **图的优化问题**： - 最优欧拉环游涉及最小化路径的权重总和。 - Dantzig算法用于求解最短路问题。 - Fleury算法用于找到图的欧拉回路，但最优欧拉环游不一定是唯一的。 7. **连通性的性质**： - k连通图意味着图中存在k个独立的顶点集，移除其中任何k-1个集合都不会导致图不连通。 - k边连通图的性质与k连通图类似，但涉及边而不是顶点。 - 若图G是2连通的，那么它连通且无割点，n>=3。 这些题目和解答涵盖了图论的基础知识，包括图的结构、连通性、欧拉路径以及图的优化问题，对于理解和应用图论概念具有很高的价值。