图论作业3

图论作业3

一、填空题

1. 完全图K2n共有 个不同的完美匹配。 2. 图K60,62的最小覆盖包含的点数为 。

3. 完全图K60能分解为 个边不重的一因子之并。 4. 完全图K2n+1能分解为 个边不重的二因子之并。

5. 图G是由3个连通分支K1, K2, K4组成的平面图，则其共有 个面。

6. 设图G与K5同胚，则至少从G中删掉 条边才可能使其成为可平面图。 7. 设连通平面图G具有5个顶点，9条边，则其面数为 。 8. 若图G是10阶极大平面图，则其面数等于 。 9. 若图G是10阶极大外平面图，其内部面共有 个。 二、不定项选择题

1. 关于非平凡树T，下面说法错误的是( ) (A) T至少包含一个完美匹配； (B) T的荫度大于1；

(C) T是只有一个面的平面图； (D) T的对偶图是简单图。 2. 下列说法正确的是( )

(A) 三正则的偶图存在完美匹配；

(B) 无割边的三正则图一定存在完美匹配； (C) 有完美匹配的三正则图一定没有割边； (D) 三正则哈密尔顿图存在完美匹配。 3. 下列说法错误的是( )

(A) 在偶图中，最大匹配包含的边数等于最小覆盖包含的点数； (B) 任一非平凡正则偶图可以1-因子分解； (C) 奇数阶的哈密尔顿图可能是偶图； (D) 非平凡偶图的最大匹配是唯一的。 4. 下列说法中正确的是( ) (A) 完全图K101包含1-因子； (B) 完全图K102包含2-因子；

(C) 图G的一个完美匹配实际上就是它的一个1因子； (D) 图G的一个2-因子实际上就是它的一个哈密尔顿圈。 5. 下列说法正确的是( ) (A) n方体可以1-因子分解； (B) 非平凡树可以1-因子分解；

(C) 无割边的3正则图可以1-因子分解；

(D) 有割边的3正则图一定不可以1-因子分解； (E) 可1-因子分解的3正则图一定是哈密尔顿图。 6. 下列说法正确的是( )

(A) 完全图K2n是2n-1个完美匹配的并； (B) 完全图K2n是n个哈密尔顿圈的并；

(C) 完全图K2n是1个完美匹配与n-1个哈密尔顿圈的并；

1 / 3

图论 班 姓名 学号

(D) 若图G是2k正则连通图，则G可以分解为k个二因子的并； (E) 具有m条边的n阶无环图可以分解为m个生成森林的并。 7. 下列说法错误的是( )

(A) 任何平面图都只有一个外部面；

(B) 简单平面图中一定有度数不超过5的顶点； (C) 平面图的各个面的次数之和可能为奇数；

(D) 存在一种方法，总可以把平面图的任意一个内部面转化为外部面。 8. 下列说法正确的是( )

(A) 若无环图G是2连通的平面图，则其一定不包含割点； (B) 若无环图G是2连通的平面图，则其一定不包含割边；

(C) 若无环图G是2连通的平面图，则其一定不包含只属于一个面的边； (D) 若无环图G是2连通的平面图，则其每个面的边界均为圈。 9. 下列说法错误的是( )

(A) 若(n, m)图G是极大平面图且n≥3，则m=3n-6； (B) 阶数至少为3的极大平面图的每个面均是三角形； (C) 阶数至少为3的极大外平面图的每个面均是三角形； (D) 阶数至少为3的极大外平面图一定是哈密尔顿图。

10. 关于平面图G和其对偶图G*的关系，下列说法中错误的是( ) (A) G*是连通平面图；

(B) G的面数等于G*的顶点数； (C) G的边数等于G*的边数； (D) G的点数等于G*的面数； (E) G≌(G*)*。 三、解答题

1. 共有n位男士和n位女士参加一次舞会，已知每位男士至少认识两位女士，而每位女士至多认识两位男士。能否将男士和女士分配为n对，使得每对中的男士和女士彼此相识？

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。 每名学生是否都可以得到他喜欢的书？为什么？(用图论方法求解)

2 / 3

图论 班 姓名 学号

3. 设图G是n(n≥4)阶简单图，n为偶数，且最小度δ≥n/2+3，则G中存在5因子。

4. 设图G是具有n个点、m条边、ω个连通分支的平面图。若G的每个面均至少由k (k≥3)条边围成，则

m≤k(n−ω−1).

k−2

5. 设简单图G有10个4度顶点和8个5度顶点，其余顶点度数均为7。求7度顶点的最大数目，使得G保持其可平面性。

3 / 3