离散数学图论答案离散数学图论答案【篇⼀：离散数学图论习题】综合练习⼀、单项选择题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是简单图还是多重图？是连通图吗？说明理由.be解：图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问它有⼏⽚树叶？...
