考试题目参考_upload

图论期末考试题目参考

《图论》

《图论》期末考试模拟题（答案）

注意：这仅仅是题型的参考而已，真正的题目不会从这里出。

一、选择题

1、给定无向图如图所示，下面给出的顶点集子集中，是点割集的为（A,B,C,D）。

A. {b, d}

B. {d}

C. {a, c}

D. {g, e} bf

2、设V＝{a,b,c,d},与V能构成强连通图的边集E＝（ A ）。

A. {<a,b>,<a,c>,<d,a>,<b,d>,<c,d>}

B. {<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}

C. {<a,c>,<b,a>,<b,c>,<d,a>,<d,c>}

{<a,d>,<b,a>,<b,d>,<c,d>,<d,c>}

3、一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条（ B ）。

A. 哈密尔顿回路

B. 欧拉回路

C. 哈密尔顿通路

D. 欧拉通路

4、如图所示各图，其中存在哈密顿回路的图是（ A, C ）。

第 1 页 共 5 页

图论期末考试题目参考

《图论》

5. 下图中既是欧拉图，又是哈密尔顿图的有（D）。

A．

B．

C．

D．

5、设G是有5个顶点的完全图，则G（ B ）。

D. 无哈密尔顿路

E. 可以一笔画出

F. 不能一笔画出

G. 是平面图

6、设G是连通简单平面图，G中有11个顶点5个面，则G中的边是（ D ）。

A. 10

B. 12

C. 16

D. 14

二、填空题

1、完全图K8具有（ 28 ）条边。

2、图G如图所示， ab

fc 那么图G的割点是（ a, f ）。

e d

3、无向图G为欧拉图，当且仅当G是连通的，且G中无（ 奇数度 ）结点。

第 2 页 共 5 页

图论期末考试题目参考

《图论》

4、连通有向图D含有欧拉回路的充分必要条件是（ D中每个结点的入度＝出度 ）。

5、 n个结点、m条边的无向连通图是树当且仅当m=__（3）___。

(1) n+1 (2) n (3) n-1 (4)2n-1

三、

1、设图G=(P,E) 中有12条边，6个度数为3的顶点，其余顶点的度数均小于3，求G至少有多少个顶点。

解答：设G有n个顶点，由定理1，

∑d

i=1nG(vi)=2m=24 (|E|=m)

由题设 24<3×6+3(n?6)

∴ 3n>24

即 n>8

因此，G中至少有9个顶点。

2、一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么? 解答：可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。 根据：构造无向简单图G=<V,E>,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。 ?Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知?vi,vj∈V有d(vi)+d(vj)≥20,于是G中存在哈密尔顿回路。

设C=Vi1Vi2…Vi20Vi1是G中一条哈密尔顿回路，按这条回路的顺序按其排座位即符合要求。

3、已知带权图G，如图所示。试求图G的最小生成树，并计算该生成树的权。

第 3 页 共 5 页

图论期末考试题目参考

《图论》

解答：做法如下：

①选边1； ②选边2；

③选边3； ④选边5； ⑤选边7 最小生成树为{1,2,3,5,7}。如图中粗线所示。

权数为18。

四、证明题

1、设G为9个结点的无向图，每个结点的度数不是5就是6，试证明G中至少有5个度数为6的结点，或者至少有6个度数为5的结点。

证明：由握手定理的推论，G中度数为5的结点个数只能是0,2,4,6,8五种情况； 此时，相应的结点度数为6的结点个数分别为9，7，5，3，1个，以上五种对应情况(0,9),(2,7),(4,5),(6,3),(8,1)，每对情况，两数之和为9，且满足第2个数大于或等于5，或者第1个数大于或等于6，意即满足至少有度数为6的结点5个，或者至少有度数为5的结点6个。

2、彼得森图G如图8.23所示。

(1)求：α(G),β(G),γ(G).

(2)证明：(2.1)χ(G)=3,

(2.2)它不是二分图，也不是欧拉图，更不是平面图。

解 因为彼得森图中有长度为奇数的圈，根据定理8.1可知它不是二部图。图中每个顶点的度数均为3，由定理8.4可知它不是欧拉图。又因为它可以收缩成由库拉图斯基定理可知它也不是平面图。 第 4 页 共 5 页 ，

图论期末考试题目参考

《图论》

3．证明或推翻下列命题：“设连通简单平面图G 的最小度δ(G)≥4，则G 的点色数χ(G)≥3.”

解答与评分标准：

假设χ(G)<3.（反证法分情况讨论2 分）

χ(G)=1 当且仅当G 为n 阶零图，与已知矛盾。（4 分）

χ(G)=2 当且仅当G 为二分图，因为G 为平面图，只能为K2,s 或Kr,2（有问题）. 此时

必有δ(G)=2, 与已知矛盾。（4 分）

第 5 页 共 5 页