图论 班 姓名 学号 图论作业 3 一、填空题 1. 完全图 K2n共有 个不同的完美匹配。 2. 超方体 Q6的最小覆盖包含的点数为 。 3. 图 Km,n (m≤n)的最小覆盖包含的点数为 。 4. 完全图 K60能分解为 个边不重的一因子之并。 5. 完全图 K61能分解为 个边不重的二因子之并。 6. 假设 G 是具有 n 个点、m 条边、k 个连通分支的无圈图，则 G 的荫度为 。 7. 图 G 是由 3 个连通分支 K1, K2, K4组成的平面图，则其共有 个面。 8. 设图 G 与 K5同胚，则至少从 G 中删掉 条边才可能使其成为可平面图。 9. 设连通平面图 G 具有 5 个顶点，9 条边，则其面数为 。 10. 若图 G 是 10 阶极大平面图，则其面数等于 。 11. 若图 G 是 10 阶极大外平面图，其内部面共有 个。 二、不定项选择题 1. 关于非平凡树 T，下面说法错误的是( ) (A) T 至少包含一个完美匹配； (B) T 至多包含一个完美匹配； (C) T 的荫度大于 1； (D) T 是只有一个面的平面图； (E) T 的对偶图是简单图。 2. 下列说法正确的是( ) (A) 三正则的偶图存在完美匹配； (B) 无割边的三正则图一定存在完美匹配； (C) 有割边的三正则图一定没有完美匹配； (D) 有完美匹配的三正则图一定没有割边； (E) 三正则哈密尔顿图存在完美匹配。 3. 下列说法正确的是( ) (A) 在偶图中，最大匹配包含的边数等于最小覆盖包含的点数； (B) 任一非平凡正则偶图包含完美匹配； (C) 任一非平凡正则偶图可以 1-因子分解； (D) 偶度正则偶图可以 2-因子分解； (E) 非平凡偶图的最大匹配是唯一的。 4. 下列说法中错误的是( ) (A) 完全图 K101包含 1-因子； (B) 完全图 K101包含 2-因子； (C) 完全图 K102包含 1-因子； (D) 完全图 K102包含 2-因子； (E) 图 G 的一个完美匹配实际上就是它的一个 1 因子； (F) 图 G 的一个 2-因子实际上就是它的一个哈密尔顿圈。 5. 下列说法正确的是( ) (A) 方体 Qn可以 1-因子分解； (B) 非平凡树可以 1-因子分解； 1 / 4 

图论 班 姓名 学号 (C) 无割边的 3 正则图可以 1-因子分解； (D) 有割边的 3 正则图一定不可以 1-因子分解； (E) 可 1-因子分解的 3 正则图一定是哈密尔顿图。 6. 下列说法正确的是( ) (A) 完全图 K2n是 2n-1 个完美匹配的并； (B) 完全图 K2n是 n 个哈密尔顿圈的并； (C) 完全图 K2n是 1 个完美匹配与 n-1 个哈密尔顿圈的并； (D) 若图 G 是 2k 正则连通图，则 G 可以分解为 k 个二因子的并； (E) 无割边的 3 正则图可以分解为是一个 1-因子与一个 2-因子的并。 7. 下列说法正确的是( ) (A) 完全图 Kn的荫度为[n/2]； (B) 完全二部图 Ka,b的荫度为[ab/(a+b-1)]； (C) 非平凡树的荫度为 1； (D) 具有 m 条边的 n 阶无环图可以分解为 m 个生成森林的并； (E) 假设 H 是图 G 的子图，则 σ(H)≤σ(G)。 8. 下列说法错误的是( ) (A) 任何平面图都只有一个外部面； (B) 简单平面图中一定有度数不超过 5 的顶点； (C) 平面图的各个面的次数之和可能为奇数； (D) 只有一个面的连通平面图一定是树； (E) 存在一种方法，总可以把平面图的任意一个内部面转化为外部面。 9. 下列说法正确的是( ) (A) 若无环图 G 是 2 连通的平面图，则其一定不包含割点； (B) 若无环图 G 是 2 连通的平面图，则其一定不包含割边； (C) 若无环图 G 是 2 连通的平面图，则其一定不包含只属于一个面的边； (D) 若无环图 G 是 2 连通的平面图，则其每个面的边界均为圈。 10. 下列说法错误的是( ) (A) 若(n, m)图 G 是极大平面图且 n≥3，则 m=3n-6； (B) 若(n, m)图 G 是极大外平面图且 n≥3，则 m=2n-3； (C) 阶数至少为 3 的极大平面图的每个面均是三角形； (D) 阶数至少为 3 的极大外平面图的每个面均是三角形； (E) 阶数至少为 3 的极大外平面图一定是哈密尔顿图。 11. 关于平面图 G 和其对偶图 G*的关系，下列说法中错误的是( ) (A) G*是连通平面图； (B) G 的面数等于 G*的顶点数； (C) G 的边数等于 G*的边数； (D) G 的点数等于 G*的面数； (E) G≌(G*)*； (F) 若 G1≌G2，则 G1*≌G2*。 三、解答题 1. 共有 n 位男士和 n 位女士参加一次舞会，已知每位男士至少认识两位女士，而每位女士 至多认识两位男士。能否将男士和女士分配为 n 对，使得每对中的男士和女士彼此相识？ 2 / 4 

图论 班 姓名 学号 2. 由于在考试中获得好成绩，6 名学生将获得下列书籍的奖励，分别是：代数学(a)、微积分 (c)、微分方程(d)、几何学(g)、数学史(h)、规划学(p)、拓扑学(t)。每门科目只有 1 本书，而 每名学生对书的喜好是： A：d, h, t；B：h, t；C：c, d, g, p；D：d, h；E：d, t；F：a, c, d。 每名学生是否都可以得到他喜欢的书？为什么？(用图论方法求解) 3. 设图 G 是 n(n≥4)阶简单图，n 为偶数，且最小度 δ≥n/2+3，则 G 中存在 5 因子。 4. 证明：完全图 K6n-2可以 3-因子分解。 3 / 4 

图论 班 姓名 学号 5. 证明：完全图 K4n+1可以 4-因子分解。 6. 设简单图 G 有 10 个 4 度顶点和 8 个 5 度顶点，其余顶点度数均为 7。求 7 度顶点的最大 数目，使得 G 保持其可平面性。 7. 设 G*是具有 k (k≥2)个连通分支的平面图 G 的对偶图，已知 G 的边数为 10，面数为 3， 求 G*的面数。 4 / 4