离散数学图论部分综合练习

离散数学图论单元测验题一、单项选择题(本大题共10小题，每小题2分，共20分)1、在图G ＝<V ,E >中，结点总度数与边数的关系是( )(A) deg(v i )=2∣E ∣ (B) deg(v i )=∣E ∣ (C)∑∈=V v E v 2)deg( (D) ∑∈=Vv E v )deg(2、设D 是n 个结点的无向简单完全图，则图D 的边数为( )(A) n (n －1) (B) n (n +1) (C) n (n －1)/2 (D) n (n +1)/23、 设G ＝<V ,E >为无向简单图，∣V ∣=n ，∆(G )为G 的最大度数，则有(A) ∆(G )<n (B)∆(G )≤n (C) ∆(G )>n (D) ∆(G )≥n4、图G 与G '的结点和边分别存在一一对应关系，是G ≌G '(同构)的( )(A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件5、设},,,{d c b a V =，则与V 能构成强连通图的边集合是( )(A) },,,,,,,,,{><><><><><=c d b c d b a b d a E(B) },,,,,,,,,{><><><><><=c d d b c b a b d a E(C) },,,,,,,,,{><><><><><=c d a d c b a b c a E6、有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的() (A)度数 (B) 出度 (C)最大度数 (D) 入度7、设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100则G 的边数为( )．A ．5B ．6C ．3D ．48、设m E n V E V G ==>=<,,,为连通平面图且有r 个面，则r ＝( )(A) m －n +2 (B) n －m －2 (C) n +m -2 (D) m +n +29、在5个结点的二元完全树中，若有4条边，则有 ( )片树叶。

离散数学图论答案离散数学图论答案【篇⼀：离散数学图论习题】综合练习⼀、单项选择题1．设l是n阶⽆向图g上的⼀条通路，则下⾯命题为假的是( )． (a) l可以不是简单路径，⽽是基本路径 (b) l可以既是简单路径,⼜是基本路径 (c) l可以既不是简单路径，⼜不是基本路径 (d) l可以是简单路径，⽽不是基本路径答案：a2．下列定义正确的是( )．(a) 含平⾏边或环的图称为多重图(b) 不含平⾏边或环的图称为简单图 (c) 含平⾏边和环的图称为多重图(d) 不含平⾏边和环的图称为简单图答案：d3．以下结论正确是 ( )．(a) 仅有⼀个孤⽴结点构成的图是零图 (b) ⽆向完全图kn每个结点的度数是n (c) 有n(n1)个孤⽴结点构成的图是平凡图(d) 图中的基本回路都是简单回路答案：d4．下列数组中，不能构成⽆向图的度数列的数组是( )． (a)(1,1,1,2,3) (b) (1,2,3,4,5) (c) (2,2,2,2,2) (d) (1,3,3,3) 答案：b5．下列数组能构成简单图的是( )． (a) (0,1,2,3)(b) (2,3,3,3)(c) (3,3,3,3)(d) (4,2,3,3) 答案：c6．⽆向完全图k3的不同构的⽣成⼦图的个数为（）． (a) 6 (b)5(c) 4 (d) 3 答案：c7．n阶⽆向完全图kn中的边数为（）．(a)n(n?1)n(n?1)(b) (c) n (d)n(n+1) 22答案：b8．以下命题正确的是( )．(a) n(n?1)阶完全图kn都是欧拉图(b) n(n?1)阶完全图kn都是哈密顿图(c) 连通且满⾜m=n－1的图v,e(?v?=n,?e?=m)是树 (d) n(n?5)阶完全图kn都是平⾯图答案：c10．下列结论不正确是( )．(a) ⽆向连通图g是欧拉图的充分必要条件是g不含奇数度结点(b) ⽆向连通图g有欧拉路的充分必要条件是g最多有两个奇数度结点 (c) 有向连通图d是欧拉图的充分必要条件是d的每个结点的⼊度等于出度(d) 有向连通图d有有向欧拉路的充分必要条件是除两个结点外，每个结点的⼊度等1于出度答案：d11．⽆向完全图k4是（）．（a）欧拉图（b）哈密顿图（c）树答案：b12．有4个结点的⾮同构的⽆向树有 ( )个．(a) 2 (b) 3(c) 4(d) 5 答案：a13．设g是有n个结点，m条边的连通图，必须删去g的( )条边，才能确定g的⼀棵⽣成树．(a) m?n?1 (b) n?m (c) m?n?1 (d) n?m?1 答案：a14．设g是有6个结点的完全图，从g中删去( )条边，则得到树． (a) 6 (b) 9 (c) 10 (d) 15 答案：c⼆、填空题1．数组{1，2，3，4，4}是⼀个能构成⽆向简单图的度数序列，此命题的真值是 . 答案：02．⽆向完全图k3的所有⾮同构⽣成⼦图有个．答案：43．设图g??v,e?，其中?v??n,?e??m．则图g是树当且仅当g是连通的，且m?．答案：n－14．连通图g是欧拉图的充分必要条件是答案：图g⽆奇数度结点 5．连通⽆向图g有6个顶点9条边，从g中删去g的⼀棵⽣成树t．答案：46．⽆向图g为欧拉图，当且仅当g是连通的，且g中⽆答案：奇数度7．设图g??v,e?是简单图，若图中每对结点的度数之和，则g⼀定是哈密顿图．答案：?8．如图1所⽰带权图中最⼩⽣成树的权是．答案：12三、化简解答题1．设⽆向图g＝v,e，v={v1，v2，v3，v4，v5，v6}， e={( v1，v2), ( v2，v2), ( v4，v5), ( v3，v4), ( v1，v3),( v3，v1), ( v2，v4)}． (1) 画出图g的图形；2图15图22(2) 写出结点v2, v4，v6的度数； (3) 判断图g是简单图还是多重图．解：(1) 图g的图形如图5所⽰．(2) deg(v2)?4,deg(v4)?3,deg(v6)?0．(3) 图g是多重图．作图如图2. 2．设图g＝v，e，其中v＝{a,b,c,d,e}, e={(a,b),(b,c),(c,d), (a,e)}试作出图g的图形，并指出图g是简单图还是多重图？是连通图吗？说明理由.b e解：图g如图8所⽰．. 图g中既⽆环，也⽆平⾏边，是简单图． cd 图g是连通图．g中任意两点都连通.图3所以，图g有9个结点．作图如图3．四、计算题1．设简单连通⽆向图g有12条边，g中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求g中有多少个结点．试作⼀个满⾜该条件的简单⽆向图．解：设图g有x个结点，由握⼿定理2?1+2?2+3?4+3?（x?2?2?3）＝12?23x?24?21?18?27x＝9 故图g有9个结点．图4满⾜该条件的简单⽆向图如图4所⽰2．设图g(如图5表⽰)是6个结点a,b,c, d,e,f的图，试求，图g的最⼩⽣成树，并计算它的权．c 解：构造连通⽆圈的图，即最⼩⽣成树，⽤克鲁斯克尔算法：第⼀步：取ab＝1；第⼆步：取af=4第三步：取fe＝3；第四步：取ad=9图5 第五步：取bc=23如图6．权为1+4+3+9+23=403．⼀棵树t有两个2度顶点，1个3度顶点；3个4问它有⼏⽚树叶？解：设t有n顶点，则有n－1条边．t中有2个 2度顶点，1个3度顶点，3个4度顶点，其余n－2－1-3个1度顶点．五、证明题1．若⽆向图g中只有两个奇数度结点，则这两个结点⼀定是连通的．证：⽤反证法．设g中的两个奇数度结点分别为u和v．假若u和v不连通．即它们之间⽆任何通路，则g⾄少有两个连通分⽀g1，g2，且u和v分别属于g1和g2，于是g1和g2各含有⼀个奇数度结点．这与握⼿定理的推论⽭盾．因⽽u和v⼀定是连通的．3【篇⼆：离散数学图论练习题】题1、设g是⼀个哈密尔顿图，则g⼀定是()。

作业答案：图论部分P165:习题九1、 给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表示。

（1）111,G V E =<>，112345{,,,,}V v v v v v =，11223343345{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （2）222,G V E =<>，21V V =，11223344551{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （3）13331,,,D V E V V =<>=31223324551{,,,,,,,,,}E v v v v v v v v v v =<><><><><> （4）24441,,,D V E V V =<>=31225523443{,,,,,,,,,}E v v v v v v v v v v =<><><><><> 解答： （1）（2）10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。

（1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个奇度顶点。

14、设G 是(2)n n ≥阶无向简单图，G 是它的补图，已知12(),()G k G k δ∆==，求()G ∆，()G δ。

解答：2()1G n k ∆=--；1()1G n k δ=--。

15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。

解答：（c ）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1（d ）同构，同构函数为12()345x a x bf x x c x d x e=⎧⎪=⎪⎪==⎨⎪=⎪=⎪⎩ 16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。

离散数学特殊图练习题一、基本概念与性质1. 判断下列说法是否正确：（1）完全图是连通图。

（2）树是一个无环的连通图。

（3）平面图一定可以画在一个平面上，使得任意两边都不相交。

2. 填空题：（1）一个有n个顶点的完全图的边数为______。

（2）一个有n个顶点的连通图至少有______条边。

（3）一个有n个顶点的树有______条边。

二、特殊图的判定1. 判断下列图是否为特殊图，并说明理由：（1）一个有5个顶点的图，其中每个顶点的度数分别为4, 4, 3, 3, 2。

（2）一个有6个顶点的图，其中每个顶点的度数都为3。

2. 下列图是否为平面图？请给出证明或反例：（1）K5（完全图K5）。

（2）K3,3（完全二部图K3,3）。

三、特殊图的性质与应用1. 计算下列图的色数：（1）一个有5个顶点的完全图。

（2）一个有6个顶点的环形图。

2. 下列图是否存在哈密顿回路？请给出证明或反例：（1）一个有5个顶点的环形图。

（2）一个有6个顶点的完全二部图。

四、综合题（1）若G为连通图，则G至少有n1条边。

（2）若G为平面图，则G的边数e ≤ 3n 6。

（1）完全图K6。

（2）完全二部图K3,3。

（3）一个有5个顶点的树。

3. 设G是一个有8个顶点的连通图，其中每个顶点的度数都为3。

证明：G至少有一个哈密顿回路。

五、图的同构与子图（1）图G1：顶点集{A, B, C, D}，边集{AB, AC, BC, BD, CD}；图G2：顶点集{P, Q, R, S}，边集{PQ, PR, QR, QS, RS}。

（1）一个有4个顶点的完全图。

（2）一个有5个顶点的星形图。

六、路径与距离（1）一个有6个顶点的环形图。

（2）一个有5个顶点的完全图。

（1）一个有6个顶点的路径图，顶点A和顶点B分别位于路径的两端。

（2）一个有7个顶点的图，顶点A和B不相邻，但通过其他顶点可以到达。

七、欧拉图与哈密顿图（1）一个有5个顶点的环形图。

第二部分图论选择题判断题注意：A B C D顺序会出现变动！根据选项确定答案！1. 已知无向图G的邻接矩阵为，则G有（5点，7边）．A. 5点，8边B. 6点，7边C. 6点， 8边D. 5点，7边2. 设无向图G的邻接矩阵为，则G的边数为( 5 )．A. 6B. 5C.4 C.33．设无向图G的邻接矩阵为则G的边数为（ 7 ）。

A．1 B. 6 C. 7 D. 144．设图G＝<V, E>，v V，则下列结论成立的是 (()deg2v Vv E∈=∑) ．A. deg(v)=2|E|B. deg(v)=|E|C.()deg2v Vv E∈=∑D.()degv Vv E∈=∑5.图G如图二所示，以下说法正确的是 ( {b,c}是点割集 )A. a是割点B. {b,c}是点割集C. {b, d}是点割集D. {c}是点割集6.如图所示，以下说法正确的是 ( e是割点)．A. e是割点B. {a,e}是点割集C. {b , e}是点割集D. {d}是点割集7. 如图所示，以下说法正确的是（e是割点）A. e是割点B. {a,e}是点割集C. {b, e}是点割集D. {d}是点割集8. 如图一所示，以下说法正确的是 ( {(d, e)}是边割集 ) ．A. {(a, e)}是割边B. {(a, e)}是边割集C. {(a, e) ,(b, c)}是边割集D. {(d, e)}是边割集9.图G如图四所示，以下说法正确的是( {(a, d) ,(b, d)}是边割集) ．A. {(a, d)}是割边B. {(a, d)}是边割集C. {(a, d) ,(b, d)}是边割集D. {(b, d)}是边割集图四10.设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是 (（a）是强连通的 )．图五A.（a）是强连通的B. （b）是强连通的C. （c）是强连通的D. （d）是强连通的11. 设有向图（a）、（b）、（c）与（d）如图六所示，则下列结论成立的是( （d）只是弱连通的 )．图六A. （a）只是弱连通的B. （b）只是弱连通的C. （c）只是弱连通的D. （d）只是弱连通的12.设G是连通平面图，有v个结点，e条边，r个面，则r = ( e－v＋2 )．A. e－v＋2B. v＋e－2C. e－v－2D. e＋v＋213.设完全图K n有n个结点(n 2)，m条边，当（n为奇数）时，K n中存在欧拉回路．A. m为奇数B. n为偶数C. n为奇数D. m为偶数14.若G是一个欧拉图，则G一定是( 连通图)．A. 平面图B. 汉密尔顿图C. 连通图D. 对偶图15.若G是一个汉密尔顿图，则G一定是( 连通图 )．A. 平面图B. 对偶图C. 欧拉图D. 连通图16.无向完全图K4是（汉密尔顿图）．A. 欧拉图B. 汉密尔顿图C. 非平面图D. 树17.无向树T有8个结点，则T的边数为( 7 )．A. 6B. 7C.8D.918. 无向简单图G是棵树，当且仅当( G连通且边数比结点数少1 )．A. G连通且边数比结点数少1B. G连通且结点数比边数少1C. G的边数比结点数少1D. G中没有回路19. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( 5 )．A．8 B.5 C.4 D.320.设G是有n个结点，m条边的连通图，必须删去G的( m-n+1 )条边，才能确定G的一棵生成树A. m-n+1B. m-nC. m+n+1D. n-m+121. 以下结论正确的是（树的每条边都是割边）A. 无向完全图都是欧拉图B. 有n个结点n－1条边的无向图都是树C. 无向完全图都是平面图D. 树的每条边都是割边22.无向图G存在欧拉回路，当且仅当（G连通且至多有两个奇数度结点）.A. G中所有结点的度数全为偶数B. G中至多有两个奇数度结点C. G连通且所有结点的度数全为偶数D. G连通且至多有两个奇数度结点二、判断题1.设G 是一个有7个结点16条边的连通图，则G 为平面图． ( 错 )2. 如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路． ( 错 )3. 如图九所示的图G 不是欧拉图而是汉密尔顿图． ( 对 )4. 设图G 如图七所示，则图G 的点割集是{f}． ( 错 )5. 两个图同构的必要条件是结点数相等；边数相等；度数相同的结点数相等．( 对 )6. 设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去4条边后使之变成树． ( 对 )7. 若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为W ≤|S|． ( 对 )8. 汉密尔顿图一定是欧拉图． ( 错 )9. 设G=<V ，E>是具有n 个结点的简单图，若在G 中每一对结点度数之和小于n-1，则在G 中存在一条汉密尔顿路． ( 错 )(应该大于等于n-1)10. 设G 是一个连通平面图，且有6个结点11条边，则G 有7个面．( 对 )11. 已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是15． ( 对 )12. 设图G 是有5个结点的连通图，结点度数总和为10，则可从G 中删去6条边后使之变成树． ( 错 )（应该删除5-4=1条边）13. 设完全图Kn 有n 个结点（n ≥2），m 条边，当n 为奇数时，Kn 中存在欧拉回路 ( 对 )14. 设G 是一个图，结点集合为V ，边集合为E ，则()v Vdeg 2v E ∈=∑ ( 对 )15. 若图G=<V, E>，其中V={ a, b, c, d }，E={ (a, b), (a, d),(b, c), (b,d)}，则该图中的割边为(b, c)( 对 )16. 结点数v与边数e满足e=v的无向连通图就是树． ( 错)17. 无向图G的结点数比边数多1，则G是树． ( 错)18. 设连通平面图G的结点数为5，边数为6，则面数为4． ( 错)19. 如图八所示的图G存在一条欧拉回路． ( 错)20. 无向图G存在欧拉回路，当且仅当G连通且结点度数都是偶数．( 对 )。