课后作业31

【知识点详解】 1. **完美匹配**：在图论中，一个完美匹配是图中的一组边，使得每个顶点恰好被一条边所连接，没有未配对的顶点。对于完全图 K2n，其拥有 n 个大小为 2 的独立集，因此有 n 个不同的完美匹配。 2. **最小覆盖**：在图论中，最小覆盖是指最少数量的顶点集合，使得这些顶点覆盖了图中的所有边。超方体 Q6 是四维超立方体的扩展，是一个6维的立方体结构。对于 Q6 的最小覆盖，需要找到最少的点数，确保每条边都至少有一个端点在覆盖集中。具体的数值需要计算得出，但最小覆盖通常小于或等于图的顶点数。 3. **Km,n 的最小覆盖**：图 Km,n 是一个完全二部图，其中一部分有 m 个顶点，另一部分有 n 个顶点（m≤n）。最小覆盖是指覆盖所有边所需的最少顶点数。在这种情况下，最小覆盖通常包括较大的部分的所有顶点，即 n 个顶点。 4. **边不重的一因子分解**：一个一因子是一条边不重的匹配，即图中的一组边，没有两个边共享同一个顶点。完全图 K60 可以被分解为若干个边不重的一因子之并，具体数目可以通过计算 K60 的边数（即组合数学中的组合公式）并除以每个性质的一因子的边数（n/2，n 为完全图的顶点数）来获得。 5. **二因子分解**：二因子是图的一种特殊分解，由一系列环路组成，每条环路的长度都是偶数。类似地，完全图 K61 可以被分解为若干个边不重的二因子之并。 6. **荫度**：图的荫度指的是最少需要删除的顶点数，使得剩下的图变得连通。一个无圈图（树）的荫度总是 1，因为只需删除一个顶点即可使树变成若干棵不相交的树。 7. **平面图的面数**：平面图的面数是由欧拉公式 V - E + F = 2 决定的，其中 V 是顶点数，E 是边数，F 是面数。由题目中的信息，需要根据具体图形计算出面数。 8. **平面图与 K5 同胚**：若图 G 与 K5 同胚，意味着 G 可以通过连续变形变为 K5。K5 是非平面图，因为它不能在平面上画出而不产生交叉边。为了使 G 成为可平面图，需要删除至少一条边。 9. **连通平面图的面数**：根据欧拉公式，对于一个连通平面图，如果有 5 个顶点和 9 条边，面数可以通过 V - E + F = 2 计算得出。 10. **极大平面图的面数**：极大平面图是指在保持平面性的同时，无法再添加边的图。对于 10 阶极大平面图，面数可通过欧拉公式求解。 11. **极大外平面图的内部面数**：极大外平面图是可以在二维平面上展开为平面图，而所有顶点都在边界上的图。同样，内部面的数量可以通过欧拉公式计算得出。 12. **非平凡树的性质**：非平凡树至少有一个完美匹配，荫度为 1，且其对偶图是简单图。 13. **正则图与完美匹配**：正则图是指所有顶点度数都相同的图。偶图（所有顶点度数都是偶数的图）中的最大匹配等于最小覆盖的点数。三正则图如果存在完美匹配，则没有割边；反之，有割边的三正则图可能存在完美匹配。 14. **1-因子与 2-因子**：1-因子是匹配，2-因子是每个顶点度数为 2 的循环结构。完全图 K101 及 K102 是否包含 1-因子或 2-因子取决于它们的边数是否为偶数。1-因子是完美匹配，2-因子对应于哈密尔顿圈。 15. **方体与树的分解**：方体 Qn 可以分解为 1-因子，非平凡树和无割边的 3 正则图也都可以。有割边的 3 正则图不一定不可分解为 1-因子，但可 1-因子分解的 3 正则图不一定是哈密尔顿图。 16. **完全图与哈密尔顿圈**：完全图 K2n 可以看作是 n 个哈密尔顿圈的并。完全二部图 Ka,b 的荫度与边数有关，非平凡树的荫度为 1，而有 m 条边的 n 阶无环图可以分解为 m 个生成森林的并。 17. **平面图的性质**：平面图有一个外部面，且每个面的次数（边数）之和为偶数。只有一个面的连通平面图是树，平面图的面可以转换，但不是任意面都能转化为外部面。 18. **2 连通平面图**：2 连通平面图没有割点和割边，其每个面的边界都是一个圈。 19. **极大平面图与极大外平面图**：极大平面图与极大外平面图的边数与顶点数的关系，可以通过平面图和外平面图的定义及欧拉公式来推导。 这些知识点涵盖了图论的基本概念，如完美匹配、最小覆盖、平面图、二部图、正则图、树、哈密尔顿圈、荫度以及平面图的面数等。