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

离散数学图论单元测验题一、单项选择题(本大题共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连通且结点度数都是偶数．( 对 )。

北京科技大学远程教育学院《离散数学》综合练习(一)参考答案数理逻辑一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。

1、今天天气真好！ 解：不是命题。

2、王华和张民是同学。

解：是命题。

真值视实际情况而定。

p ：王华和张民是同学。

3、我一边吃饭，一边看电视。

解：是命题。

真值视实际情况而定。

p ：我吃饭。

q ：我看电视。

p ∧q 4、没有不呼吸的人。

解：是命题。

真值为1。

M (x )：x 是人。

F (x )：x 呼吸。

∀x (M (x )→F (x )) 二、求命题公式的真值表和成真赋值、成假赋值。

)(])[(r p r q p →∧→∧三、用真值表、等值演算两种方法判别公式类型。

1、r q q p →∧→])[(rq q p r q q q p r q q p rq q p r q q p r q q p ∨⌝∧⌝∨⇔∨⌝∨⌝∧⌝∨⇔∨⌝∨⌝∧⇔∨⌝∨∨⌝⌝⇔∨∧∨⌝⌝⇔→∧→])[()]()[()()(])[(])[(可满足式2、))((p q p q ∧∨⌝⌝∨ 解：))((p q p q A ∧∨⌝⌝∨=1)()()())((⇔∨⌝∨∨⌝⌝⇔⌝∨∨⌝⌝∨⇔∧∨⌝⌝∨q p q p p q p q p q p q永真式四、求命题公式的主析取范式和成真赋值、成假赋值。

)(r q p →→ ∑=→→），，，，，，7543210()(r q p 成真赋值：000，001，010，011，100，101，111；成假赋值110五、解释I 如下：D 是实数集，特定元素a =0；特定函数f (x ，y )=x -y ；特定谓词F (x ，y )：x<y 。

在解释I 下判别公式真、假。

1、)])(([x y x f F y x ，，⌝∀∀ 解：)])[()])(([)]([)])(([x y x y x x y x y x x y x F y x x y x f F y x ≥-∀∀⇔<-⌝∀∀⇔-⌝∀∀⇔⌝∀∀，，，真值为假2、)]()([)({z y f z x f F y x F z y x ，，，，→∀∀∀ 解：)]()()[()]}()([)({z y z x y x z y x z y f z x f F y x F z y x -<-→<∀∀∀⇔→∀∀∀，，，，真值为真 六、1、求前束范式)()(y x yG x xF ，∀→⌝∃ 解：)]()([)()()()()()(y t G x F y x y t yG x xF y x yG x xF y x yG x xF ，，，，∨∀∃⇔∀∨∃⇔∀∨∃⇔∀→⌝∃2、证明：B x xA B x A x →∀⇔→∃)())(( 证明：Bx xA Bx xA B x A x B x A x B x A x →∀⇔∨⌝∀⇔∨⌝∃⇔∨⌝∃⇔→∃)()()())(())((七、写出下面推理的证明，要求写出前提、结论，并注明 推理规则。

离散数学综合练习二一、单项选择题（每题2分 ）16 %1. 设P ：4大于2，Q ：3大于2，命题“4大于2仅当3大于2”符号化为 ( )(A)(B)()(D)P Q Q P C P Q P Q →→↔⌝∨⌝2 设F (x )：x 是金属，G (y )：y 是液体，H (x ,y )：x 溶解在y 中，那么命题“任何金属都可以溶解在某种液体中”符号化为 ( ) (A) (()(()(,)))x F x y G y H x y ∀∧∃→ (B) (()(()(,)))x F x y G y H x y ∀→∃→(C) (()(()(,)))x F x y G y H x y ∀→∃∧ (D) ((()())(,))x y F x G y H x y ∀∃→∧3. 命题公式()p q p ∧→是 ( )(A) 重言式 (B) 矛盾式 (C) 可满足式 (D) 以上3种都不是 4. 下列各式命题为假的是 ( )(A) φφ⊆ (B) {}φφ⊆ (C) {}φφ∈ (D) φφ∈ 5. 设函数 :f R R →且3()215f x x x =--，则f 是 ( )(A) 满射,非单射 (B)单射，非满射 (C) 双射 (D)非单射，非满射 6. 与命题公式()p q r →→等值的公式是（ ）(A) ()p q r ∨→ (B) ()p q r ∧→ (C) ()p q r →→ (D) ()p q r →∨7. 设A ={a,b,c}，A 上的关系R ={<a,a>,<b,b>}，则R 是 ( )（A ）自反的 （B ）反自反的 （C ）反对称的 （D ）等价的 8. 设无向图,G V E =<>是哈密顿图, 则对于任意的1V V ⊂且1V ≠∅,均有11()P G V V -≤。

上述给出的是哈密顿图的（ ）（A ）充分条件 （B ）必要条件 （C ）充分必要条件 （D ）都不是 1. 设():F x x 是人，():G x x 犯错误，则命题“没有不犯错误的人”的符号化deb 图1是 ，其前束范式为 。

离散数学图论部分综合练习1．设图G ＝<V , E >，则下列结论成立的是 ( )． A ．deg(V )=2E B ．deg(V )=EC ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg( 2．图G 如图一所示，以下说法正确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集 D ．{(a, d ) ,(a, c )}是边割集3．如图二所示，以下说法正确的是 ( )． A ．e 是割点 B ．{a, e }是点割集 C ．{b , e }是点割集 D ．{d }是点割集4．如图三所示，以下说法正确的是 ( ) ．A ．{(a, e )}是割边B ．{(a, e)}是边割集 C ．{(a, e ) ,(b, c )}是边割集 D ．{(d , e )}是边割集图三5．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的6．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数 7．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )．A ．e －v ＋2B ．v ＋e －2C ．e －v －2D ．e ＋v ＋2οο ο ο οca b edο f图一图二8．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点9．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+ 10．无向简单图G 是棵树，当且仅当( )．A ．G 连通且边数比结点数少1B ．G 连通且结点数比边数少1C ．G 的边数比结点数少1D ．G 中没有回路．二、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．2．设给定图G (如图四所示)，则图G 的点割 集是 ．3．若图G=<V , E>中具有一条汉密尔顿回路， 则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 ．4．无向图G 存在欧拉回路，当且仅当G 连通 且 ．5．设有向图D 为欧拉图，则图D 中每个结点的入度 ．6．设完全图K n 有n 个结点(n 2)，m 条边，当 时，K n 中存在欧拉回路．7．设G 是连通平面图，v , e , r 分别表示G 的结点数，边数和面数，则v ，e 和r 满足的关系式 ．8．设连通平面图G 的结点数为5，边数为6，则面数为 ． 9．结点数v 与边数e 满足 关系的无向连通图就是树．10．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 条边后使之变成树．11．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为 ．12．设G ＝<V , E >是有6个结点，8条边的连通图，则从G 中删去 条边，可以确定图G 的一棵生成树．13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元ο ο οο ο c a be dο f 图四素 ，则该序列集合构成前缀码．三、判断说明题1．如图六所示的图G 存在一条欧拉回路．2．给定两个图G 1，G 2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．图七3．判别图G (如图八所示)是不是平面图， 并说明理由．4．设G 是一个有6个结点14条边的连 通图，则G 为平面图．四、计算题 1．设图GV ，E ，其中V a 1, a 2, a 3, a 4, a 5,Ea 1, a 2，a 2, a 4，a 3, a 1，a 4, a 5，a 5, a 2（1）试给出G 的图形表示；（2）判断图G 是强连通图、单侧连通图还是弱连通图？2．设图G =<V ，E >，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1, v 2)，(v 1, v 3)，(v 2, v 3)，(v 2, v 4)，(v 3, v 4)，(v 3, v 5)，(v 4, v 5) }，试（1）画出G 的图形表示； （2）求出每个结点的度数； （3）画出图G 的补图的图形．3．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4)，(v 3,v 5)，(v 4,v 5) }，试v 1v 2v 3v 4v 5v 6v 1v 2 v 3v 5 d bae fghn 图六οοο ο οv 5v 1 v 2 v 4v 6 ο v 3图八（1）给出G 的图形表示； （2）求出每个结点的度数； （3）画出其补图的图形．4．图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (c , d ), (d , e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G 的图形；（2）求出G 权最小的生成树及其权值．5．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二叉树； （2）计算它们的权值． 6．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它的权．五、证明题1．若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的． 2．设G 是一个n 阶无向简单图，n 是大于等于2的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．3．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．参考解答一、单项选择题1．C 2．C 3．A 4．D 5．D 6．C 7．A 8．D 9．A 10．A二、填空题1．15 2．{f }，{c ，e } 3．W|S|4．所有结点的度数全为偶数 5．等于出度 6．n 为奇数 7．v -e +r =2 8．3 9．e=v -1 10．4 11．512．3 13．0三、判断说明题1．解：正确．因为图G 为连通的，且其中每个顶点的度数为偶数． 2．解：（1）图G 1是欧拉图．因为图G 1中每个结点的度数都是偶数．图G 2是汉密尔顿图．因为图G 2存在一条汉密尔顿回路（不惟一）：a (a ,b )b (b , e ) e (e , f ) f (f , g ) g (g , d ) d (d ,c ) c (c , a )a 问题：请大家想一想，为什么图G 1不是汉密尔顿图，图G 2不是欧拉图。

离散数学图论部分综合练习辅导本次活动是本学期的第二次活动(2008.11.18)，主要是针对第二单元图论的重点学习内容进行辅导，方式是通过讲解一些典型的综合练习题目，帮助大家进一步理解和掌握图论的基本概念和方法。

图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法。

教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等。

本次综合练习主要是复习这一部分的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题。

这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习。

下面分别讲解。

一、单项选择题1．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******000011100000100 则G 的边数为( )．A ．5B ．6C ．3D ．4正确答案：D上学期的作业中，有的同学选择答案B 。

主要是对邻接矩阵的概念理解不到位。

我们复习定义：定义3.3.1 设G =<V ，E >是一个简单图，其中V ={v 1，v 2，…， v n }，则 n 阶方阵A （G ）=（a ij ）称为G 的邻接矩阵．其中各元素⎪⎩⎪⎨⎧==ji v v v v a j i j i ij 不相邻或与相邻与01 而当给定的简单图是无向图时，邻接矩阵为对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i 与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各有一个1，题中给出的邻接矩阵中共有8个1，故有8÷2=4条边。

2．设图G ＝<V , E >，则下列结论成立的是 ( )．A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v V v 2)deg(=∑∈D ．E v Vv =∑∈)deg(正确答案：C该题主要是检查大家对握手定理掌握的情况。

1、一个7阶无向简单图，其结点的最大度数为（）A、5B、6C、7D、82、设G为7阶无向简单图，下列命题成立的是（）A、G的每个结点度数均为3B、G的每个结点度数均为5C、G的每个结点度数均为6D、G的每个结点度数均为73、由4个点3条边构成的无向简单图中，结点的最大度数为（）A、1B、2C、3D、44、(多选题)下列度数列，可以简单图化的是（）A、5,5,4,4,2,1B、5,5,4,1,1C、5,4,4,2,1D、5,4,3,2,2E、4,4,3,3,2,2F、4,3,2,1G、3,3,2,2,1,1H、3,3,3,1I、3,3,1,15、下列可作为4阶无向简单图的结点度数序列是（）A、1,2,3,4B、0,2,2,3C、1,1,2,2D、1,3,3,38、下列关于图的命题正确的是（）A、欧拉图都是哈密顿图B、哈密顿图都是欧拉图C、4阶以上的完全图都是欧拉图D、4阶以上的完全图都是哈密顿图9、下列关于欧拉图的描述正确的是（）A、K4是欧拉图B、K5是欧拉图C、完全图都是欧拉图D、K6是欧拉图13、一棵无向树有5片树叶，3个2度结点，其余都是3度结点，这棵树的结点数是（）A、10B、11C、12D、1314、G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的多少条边（）A、m-n+1B、m-nC、m+n+1D、n-m+115、一个n阶图不一定是树的是（）A、无回路的连通图B、无回路且有n-1条边C、n阶连通图D、有n-1条边的连通图16、下列6阶无向树的度数序列，对应不止一棵同构树的是（）A、1,1,1,1,2,4B、1,1,1,2,2,3C、1,1,2,2,2,2D、1,1,1,1,3,31、设5阶简单连通图G所有结点的度数之和为18，则G的结点的最大度数为_____，最小度数为______2、4阶完全图K4是平面图，其面数r为_____，记结点数为n，边数为m，则n-m+r=_______3、一个简单无向连通图，有n个结点，m条边，则边数m的最大值为_________，最小值为_______4、7阶无向简单图G，最多有________条边5、连通平面图G的每个面至少由5条边围成，则G的边数m与顶点数n满足的不等式关系为______________6、连通平面图G共有8个顶点，其平面表示中共有6个面，则边数为______7、如题的9阶无向图，需要添加边使其称为欧拉图，至少需要添加_____________和______________8、一棵n(n>2)阶无向树T，其最大度数⊿(T)的最小值为_____，最大值为________9、一棵7阶树T，其分支点最多有____个，最多有____片树叶10、无向完全图K8，需要删掉______条边才能得到生成树；无向完全图K9，需要删掉______条边才能得到生成树11、无向树有4个3度分支点，2个2度分支点，其余为树叶，则树叶数为______12、设无向树有8片树叶，1个4度分支点，其余都是3度分支点，则该树共有______个结点1、研究4阶完全图K4，判断其是否存在欧拉回路？是否存在哈密顿回路？如果存在，共有多少个非同构的回路？2、9阶无向图G中，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。

《离散数学》图论部分习题《离散数学》图论部分习题1.已知⽆向图G有12条边，6个3度顶点，其余顶点的度数均⼩于3，问G⾄少有⼏个顶点？并画出满⾜条件的⼀个图形. （24-3*6）/2 +6=92.是否存在7阶⽆向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶⽆向简单图G中最⼤度≤63.设d1、d2、…、d n为n个互不相同的正整数. 证明：不存在以d1、d2、…、d n为度序列的⽆向简单图.Max{d1，d2，…，dn}≥n，n阶⽆向简单图G中最⼤度≤n-14.求下图的补图.5.1)试画⼀个具有5个顶点的⾃补图2)是否存在具有6个顶点的⾃补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整数，n=4k或n=4k+1，不存在6阶⾃补图。

6.设图G为n(n>2且为奇数)阶⽆向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现7.⽆向图G中只有2个奇度顶点u和v，u与v是否⼀定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分⽀上，每个分⽀上仅有⼀个奇度顶点，与握⼿引理相⽭盾。

8.图G如下图所⽰：1)写出上图的⼀个⽣成⼦图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v) | v V } ；κ(G)=min{ |V’| |V’是图G的点割集} ；λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下⽆向完全图K n为欧拉图？n为奇数时10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数；桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分⽀上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分⽀上只有⼀个奇度顶点，与握⼿引理⽭盾。

离散数学作业5离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第15周末前完成并上交任课教师（不收电子稿）。

并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是15． 2．设给定图G (如右由图所示)，则图G 的点割集是{f}．3．设G 是一个图，结点集合为V ，边集合为E ，则G 的结点度数之和等于边数的两倍．4．无向图G 存在欧拉回路，当且仅当G 连通且等于出度．5．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于n-1，则在G 中存在一条汉密尔顿路．6．若图G=<V ,E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为W ?|S|．7．设完全图K n 有n 个结点(n ?2)，m 条边，当n 为奇数时，K n 中存在欧拉回路．8．结点数v 与边数e 满足e=v -1关系的无向连通图就是树．9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i =5．二、判断说明题（判断下列各题，并说明理由．）1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．． 错。

. 离散数学图论部分综合练习1．设图G ＝<V , E >，则下列结论成立的是 ( )．A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v V v 2)deg(=∑∈D ．E v V v =∑∈)deg(2．图G 如图一所示，以下说确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集D ．{(a, d ) ,(a, c )}是边割集3．如图二所示，以下说确的是 ( )．A ．e 是割点B ．{a, e }是点割集C ．{b , e }是点割集D ．{d }是点割集4．如图三所示，以下说确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d , e )}是边割集图三5．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的6．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数 ο ο ο ο ο ca b e dο f 图一图二. 7．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )．A ．e －v ＋2B ．v ＋e －2C ．e －v －2D ．e ＋v ＋28．无向图G 存在欧拉通路，当且仅当( )．A ．G 中所有结点的度数全为偶数B ．G 中至多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数D ．G 连通且至多有两个奇数度结点9．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+10．无向简单图G 是棵树，当且仅当( )．A ．G 连通且边数比结点数少1B ．G 连通且结点数比边数少1C ．G 的边数比结点数少1D ．G 中没有回路．二、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．2．设给定图G (如图四所示)，则图G 的点割 集是 ．3．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 ． 4．无向图G 存在欧拉回路，当且仅当G 连通 且 ．5．设有向图D 为欧拉图，则图D 中每个结点的入度 ．6．设完全图K n 有n 个结点(n ≥2)，m 条边，当 时，K n 中存在欧拉回路．7．设G 是连通平面图，v , e , r 分别表示G 的结点数，边数和面数，则v ，e 和r 满足的关系式 ．8．设连通平面图G 的结点数为5，边数为6，则面数为 ．9．结点数v 与边数e 满足 关系的无向连通图就是树．10．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 条边后使之变成树．11．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T ο ο ο ο ο c a b e dο f 图四. 的树叶数为 ．12．设G ＝<V , E >是有6个结点，8条边的连通图，则从G 中删去 条边，可以确定图G 的一棵生成树．13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码．三、判断说明题1．如图六所示的图G 存在一条欧拉回路．2．给定两个图G 1，G 2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．（2）若是欧拉图，请写出一条欧拉回路．图七 3．判别图G (如图八所示)是不是平面图， 并说明理由． 4．设G 是一个有6个结点14条边的连 通图，则G 为平面图． 四、计算题1．设图G =<V ，E >，其中V ={a 1, a 2, a 3, a 4, a 5},E ={<a 1, a 2>，<a 2, a 4>，<a 3, a 1>，<a 4, a 5>，<a 5, a 2>}（1）试给出G 的图形表示；（2）判断图G 是强连通图、单侧连通图还是弱连通图？2．设图G =<V ，E >，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1, v 2)，(v 1, v 3)，(v 2, v 3)，v 1v 2v 3v 4 v 5v 6v 1v 2 v 3 v 5 d bae f g h n 图六 οοο ο ο v 5v 1 v 2 v 4 v 6 ο v 3 图八. (v 2, v 4)，(v 3, v 4)，(v 3, v 5)，(v 4, v 5) }，试（1）画出G 的图形表示；（2）求出每个结点的度数；（3）画出图G 的补图的图形．3．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4)，(v 3,v 5)，(v 4,v 5) }，试（1）给出G 的图形表示；（2）求出每个结点的度数；（3）画出其补图的图形．4．图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (c , d ), (d , e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G 的图形；（2）求出G 权最小的生成树及其权值．5．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二叉树； （2）计算它们的权值．6．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它的权．五、证明题1．若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的．2．设G 是一个n 阶无向简单图，n 是大于等于2的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．3．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k 条边才能使其成为欧拉图．参考解答一、单项选择题1．C 2．C 3．A 4．D 5．D 6．C7．A 8．D 9．A 10．A二、填空题1．15 2．{f }，{c ，e } 3．W |S|4．所有结点的度数全为偶数 5．等于出度6．n 为奇数 7．v -e +r =2 8．3. 9．e=v -1 10．4 11．512．3 13．0三、判断说明题1．解：正确．因为图G 为连通的，且其中每个顶点的度数为偶数．2．解：（1）图G 1是欧拉图．因为图G 1中每个结点的度数都是偶数．图G 2是汉密尔顿图．因为图G 2存在一条汉密尔顿回路（不惟一）：a (a ,b )b (b , e ) e (e , f ) f (f , g ) g (g , d ) d (d ,c ) c (c , a )a问题：请大家想一想，为什么图G 1不是汉密尔顿图，图G 2不是欧拉图。

离散数学图论部分综合练习1．设图G =〈Ｖ， E 〉,则下列结论成立的是 ( ）．A ．deg(V )=２∣E ∣B ．ｄeg(V )=∣E ∣ C.E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(2．图Ｇ如图一所示,以下说法正确的是 ( ） . A ．｛(a ， ｄ）｝是割边 B.｛（ａ, ｄ)}是边割集 Ｃ.｛（d , e )}是边割集D.｛（a, d ) ，（ａ, c )}是边割集 3.如图二所示，以下说法正确的是 ( ). Ａ．ｅ是割点 B ．{a,e }是点割集 C.{ｂ, e }是点割集 Ｄ.｛d ｝是点割集4.如图三所示,以下说法正确的是 （ ).A.｛（a ， e )}是割边 B ．{(a ， e ）}是边割集Ｃ．｛(a, ｅ) ,(b, ｃ）}是边割集 D.｛(d ， e ）}是边割集图三5．设有向图(ａ）、（b ）、(c )与(d ）如图四所示,则下列结论成立的是 （ )．图四A ．(a )是强连通的 B.（b ）是强连通的 Ｃ．(c ）是强连通的D ．(d )是强连通的6．设完全图K n 有n 个结点(ｎ≥2),m 条边，当（ ）时,K n 中存在欧拉回路.A.m 为奇数 B ．n 为偶数 C ．n 为奇数 D.m 为偶数7．设Ｇ是连通平面图,有v 个结点，e 条边,r 个面，则r ＝ ( )．A.e －ｖ+２ B ．v +ｅ－2 C ．e －ｖ-2 Ｄ．e +v ＋２ ８．无向图G 存在欧拉通路，当且仅当（ ）.οο ο ο ο ca b edο f图一图二A.G 中所有结点的度数全为偶数 Ｂ.Ｇ中至多有两个奇数度结点 C.Ｇ连通且所有结点的度数全为偶数 Ｄ．G 连通且至多有两个奇数度结点9．设G 是有n 个结点，m 条边的连通图,必须删去G 的（ )条边，才能确定Ｇ的一棵生成树.Ａ．1m n -+ B.m n - C.1m n ++ D.1n m -+１0．无向简单图G 是棵树,当且仅当( ）.A.G 连通且边数比结点数少1 Ｂ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 Ｄ．G 中没有回路.二、填空题1.已知图G 中有１个１度结点，2个2度结点,3个3度结点，4个4度结点，则G 的边数是．2．设给定图G (如图四所示)，则图G 的点割集是.3.若图G=〈V ，E ＞中具有一条汉密尔顿回路,则对于结点集Ｖ的每个非空子集S ,在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点 数｜S ｜与W 满足的关系式为．４．无向图Ｇ存在欧拉回路，当且仅当G 连通 且．5.设有向图D 为欧拉图,则图D 中每个结点的入度.6．设完全图K n 有n 个结点（n ≥2),ｍ条边,当时,K n 中存在欧拉回路. 7.设G 是连通平面图,v ， e , r 分别表示Ｇ的结点数，边数和面数，则ｖ,e 和ｒ满足的关系式.８.设连通平面图Ｇ的结点数为5,边数为6,则面数为． 9.结点数v 与边数e 满足关系的无向连通图就是树.10．设图G 是有６个结点的连通图,结点的总度数为１8,则可从G 中删去 条边后使之变成树.１1.已知一棵无向树T 中有８个结点，4度,3度，2度的分支点各一个，T 的树叶数为 .１２.设G =〈V ， Ｅ〉是有6个结点,8条边的连通图,则从G 中删去条边,可以确定图G 的一棵生成树．13．给定一个序列集合{000,０01，01,10，0}，若去掉其中的元素,则该序列集合构成前缀码．三、判断说明题ο ο οο ο c a b e dο f 图四1.如图六所示的图G 存在一条欧拉回路.2．给定两个图G 1,Ｇ2(如图七所示）:(1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由. (2)若是欧拉图,请写出一条欧拉回路．图七３．判别图Ｇ（如图八所示）是不是平面图， 并说明理由．4.设G 是一个有6个结点14条边的连 通图，则G 为平面图.四、计算题1．设图G =<Ｖ,E >，其中V ={ａ1,a 2，a 3，a 4,a 5},E ={<ａ1,a 2>,<a 2，a ４>,<a 3，ａ1>,<ａ4,ａ５>，<ａ5,ａ２>}（１)试给出G 的图形表示;(2）判断图G 是强连通图、单侧连通图还是弱连通图?2．设图G =〈Ｖ,E ＞,V ＝{ v １,v 2,v 3，ｖ４，ｖ５}，E ={ （v 1,ｖ2),(ｖ1，v 3)，(v 2,v 3),(v 2,v 4），(ｖ３，v 4)，（ｖ3,v 5),(ｖ4，v ５） },试(1)画出G 的图形表示； (2)求出每个结点的度数;（3）画出图Ｇ的补图的图形． 3.设G ＝〈V ，E 〉,V ={ ｖ1，ｖ2,ｖ3,v 4，v ５｝，Ｅ=｛ (v 1,ｖ３),(v 2,v 3),（v ２,v 4），(v 3，v 4）,（v ３,ｖ5),(v 4,v 5） },试（1）给出G 的图形表示; (2）求出每个结点的度数； （3)画出其补图的图形．v 1v 2v 3v 4v 5v 6v 1v 2 v 3v 5 d bae fghn 图六οοο ο οv 5v 1 v 2 v 4v 6 ο v 3图八4.图Ｇ=<V , E 〉，其中V ={ a , ｂ, c ，ｄ，e }，E ＝{ （a , b ）, (a ， ｃ), (ａ, e ), （b ， ｄ)，（ｂ, e ), （c ， e ）, (ｃ， d ）， （d ， e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试(1)画出G 的图形；(2)求出Ｇ权最小的生成树及其权值.5.设有一组权为2，3,５，7,１1，１3，１7，19，2３,29，３1,试(１）画出相应的最优二叉树；(2）计算它们的权值. 6.画一棵带权为１，2,2，3,4的最优二叉树,计算它的权.五、证明题1.若无向图Ｇ中只有两个奇数度结点,则这两个结点一定是连通的.2．设Ｇ是一个n 阶无向简单图,ｎ是大于等于2的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等.3.设连通图Ｇ有ｋ个奇数度的结点,证明在图G 中至少要添加2k条边才能使其成为欧拉图．参考解答一、单项选择题１.C ２.C ３．Ａ 4．Ｄ ５.D 6．C 7.A8.Ｄ９.A10.A二、填空题1．１52.{f ｝，{c ，ｅ｝3.W ｜S| ４.所有结点的度数全为偶数５．等于出度 6．n 为奇数7．v -e +r ＝2８．３ 9．e ＝ｖ—11０．411．512．３1３.0三、判断说明题1．解：正确.因为图G 为连通的,且其中每个顶点的度数为偶数. 2.解:(1)图G 1是欧拉图． 因为图G 1中每个结点的度数都是偶数．图Ｇ２是汉密尔顿图．因为图Ｇ２存在一条汉密尔顿回路（不惟一）：a （a ,b )b （b , ｅ) e (ｅ, f ） f （f , g ) g （ｇ， d ） d (ｄ，c ) c （ｃ， ａ）a 问题:请大家想一想,为什么图Ｇ１不是汉密尔顿图，图G 2不是欧拉图。