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

　　一、选择题

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

　　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. {,,,,}

　　B. {,,,,}

　　C. {,,,,}

　　{,,,,}

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

　　A. 哈密尔顿回路

　　B. 欧拉回路

　　C. 哈密尔顿通路

　　D. 欧拉通路

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

　　内容需要下载文档才能查看

　　第 1 页共 5 页

　　图论期末考试题目参考

　　《图论》

　　5. 下图中既是欧拉图，又是哈密尔顿图的有（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={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 分）