当前位置:文档之家› 离散数学图论答案

离散数学图论答案

离散数学图论答案【篇一:离散数学图论习题】综合练习一、单项选择题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一定是()。

(1) 欧拉图 (2) 树 (3)平面图(4) 连通图 2、下面给出的集合中,哪一个是前缀码?( ) (1) {0,10,110,101111}(2) {01,001,000,1} (3) {b,c,aa,ab,aba} (4) {1,11,101,001,0011} 3、一个图的哈密尔顿路是一条通过图中( )的路。

4、设g是一棵树,则g 的生成树有( )棵。

(1) 0 (2) 1 (3) 2 (4) 不能确定5、n阶无向完全图kn 的边数是( ),每个结点的度数是( )。

6、一棵无向树的顶点数n与边数m关系是( )。

7、一个图的欧拉回路是一条通过图中( )的回路。

8、有n个结点的树,其结点度数之和是()。

9、下面给出的集合中,哪一个不是前缀码( )。

(1) {a,ab,110,a1b11}(2) {01,001,000,1} (3) {1,2,00,01,0210} (4) {12,11,101,002,0011}10、n个结点的有向完全图边数是( ),每个结点的度数是( )。

11、一个无向图有生成树的充分必要条件是( )。

12、设g是一棵树,n,m分别表示顶点数和边数,则 (1) n=m (2) m=n+1 (3) n=m+1 (4)不能确定。

13、设t=〈v,e〉是一棵树,若|v|1,则t中至少存在( )片树叶。

14、任何连通无向图g至少有( )棵生成树,当且仅当g 是(),g的生成树只有一棵。

15、设g是有n个结点m条边的连通平面图,且有k个面,则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。

16、设t是一棵树,则t是一个连通且( )图。

17、设无向图g有16条边且每个顶点的度数都是2,则图g有()个顶点。

(1) 10(2) 4(3) 8 (4) 1618、设无向图g有18条边且每个顶点的度数都是3,则图g有()个顶点。

(1) 10(2) 4(3) 8 (4) 1219、任一有向图中,度数为奇数的结点有()个。

20、具有6 个顶点,12条边的连通简单平面图中,每个面都是由( )条边围成? (1) 2 (2) 4 (3) 3 (4) 521、在有n个顶点的连通图中,其边数()。

(1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条22、一棵树有2个2度顶点,1 个3度顶点,3个4度顶点,则其1度顶点为((1) 5 (2) 7 (3) 8(4) 923、若一棵完全二元(叉)树有2n-1个顶点,则它()片树叶。

(1) n (2) 2n (3) n-1(4) 2 24、下列哪一种图不一定是树()。

(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 25、连通图g是一棵树当且仅当g中()。

(1) 有些边是割边 (2) 每条边都是割边(3) 所有边都不是割边(4) 图中存在一条欧拉路径26.对于无向图,下列说法中()是正确的. a.不含平行边及环的图称为完全图b.任何两个不同结点都有边相连且无平行边及环的图称为完全图c.具有经过每条边一次且仅一次回路的图称为哈密尔顿图 d.具有经过每个结点一次且仅一次回路的图称为欧拉图27.设图g的邻接矩阵为0100?00011100000100101010??则g的边数为( ).a.5b.6c.3d.4 28.设图g=v, e,则下列结论成立的是 ( ).a.deg(v)=2?e?b.deg(v)=?e?)。

c.deg(v)2e d.?deg(v)?ev?vv?v29.图g如右图所示,以下说法正确的是 ( ) .a.{(a, d)}是割边 b.{(a, d)}是边割集 c.{(d, e)}是边割集d.{(a, d) ,(a, c)}是边割集30.设g是连通平面图,有v个结点,e条边,r个面,则r= ( ).a.e-v+2b.v+e-2c.e-v-2d.e+v+2 31.无向图g存在欧拉通路,当且仅当( ).a.g中所有结点的度数全为偶数 b.g中至多有两个奇数度结点c.g连通且所有结点的度数全为偶数 d.g连通且至多有两个奇数度结点二、填空题1.已知图g中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则g的边数是.2.设给定图g(如右图所示),则图g的点割集是.3.设无向图g=v, e是汉密尔顿图,则v的任意非空子集v1,都有 ??v1?.4.设有向图d为欧拉图,则图d中每个结点的入度.5.设完全图kn有n个结点(n?2),m条边,当时,kn中存在欧拉回路.6.给定一个序列集合{1,01,10,11,001,000},若去掉其中的元素合构成前缀码.e da ?d bfea?bf c三、计算题1.设图g??v,e?,其中v??a1, a2, a3, a4, a5?,ea1, a2?,?a2, a4?,?a3, a1?,?a4, a5?,?a5, a2??(1)试给出g的图形表示;(2)求g的邻接矩阵;(3)判断图g是强连通图、单侧连通图还是弱连通图?2.图g=v, e,其中v={a, b, c, d, e, f },e={(a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f)},对应边的权值依次为5,2,1,2,6,1,9,3及8.(1)画出g的图形;(2)写出g的邻接矩阵;a 2 c15 69b2 d(3)求出g权最小的生成树及其权值.问:如果结点集是v={a, b, c, d, e },边集e={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e) },对应边的权值依次为5,2,1,2,6,1,9,那么会求吗?3.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试(1)画出相应的最优二叉树;(2)计算它们的权值.160 ?65 95解:(1)最优二叉树如右图所示:42 3453 1724 191055问:如果一组权为2,3,6,9,13,15,能否画出最优二叉树?【篇三:离散数学习题解答第6部分(图论)】1.从日常生活中列举出三个例子,并由这些例子自然地导出两个无向图及一个向图。

相关主题