离散数学图论答案

1、离散数学图论答案【篇一：离散数学图论习题】综合练习一、单项选择题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)个孤立结点构成的图是平凡

2、图(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

3、(n?1)阶完全图kn都是欧拉图(b)n(n?1)阶完全图kn都是哈密顿图(c) 连通且满足m=n1的图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个结点的非同构

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中删去()条边，贝U得到树.(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?.答案：n14 .连通图g是欧拉图的充分

5、必要条件是答案：图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写出结点v2,v4,v6的度数；(3)判断图g是简单图还是多重

6、图.解：(1)图g的图形如图5所示.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中有多少个结点.试作一个满足该条件的简单无向图.解：

7、设图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度顶点，

8、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是一个哈密尔顿图，贝Ug一定是()。(1)欧拉图(2)树(3)平面图(4)连通图2、下面给出的集合中，哪一个是前缀码？()(1)(0,10,110,101111(2)01,001,000,1(3)(b,c,

9、aa,ab,aba(4)(1,11,101,001,00113、一个图的哈密尔顿路是一条通过图中()的路。4、设g是一棵树，贝Ug的生成树有()棵。(1)01(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，001110、n个结点的有向完全图边数是()，

10、每个结点的度数是()。11、一个无向图有生成树的充分必要条件是()。12、设g是一棵树，n,m分另U表示顶点数和边数，贝U(1)n=mm=n+1n=m+1(4)不能确定。13、设t=<v,e是一棵树，若|v|1，则t中至少存在()片树叶。14、任何连通无向图g至少有()棵生成树，当且仅当g是()，g的生成树只有一棵。15、设g是有n个结点m条边的连通平面图，且有k个面，则k等于:m-n+2n-m-2n+m-2m+n+2。16、设t是一棵树，则t是一个连通且()图。17、设无向图g有16条边且每个顶点的度数都是2,则图g有()个顶点。(1) 10(2)4(3)8(4)1618、设无向图g有

11、18条边且每个顶点的度数都是3,则图g有()个顶点。(1)10(2)4(3)8(4)1219、任一有向图中，度数为奇数的结点有()个。20、具有6个顶点，12条边的连通简单平面图中，每个面都是由()条边围成？(1)24(3)3521、在有n个顶点的连通图中，其边数()。(1)最多有n-1条至少有n-1条(3)最多有n条(4)至少有n条22、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为(1)5(2)78(4)923、若一棵完全二元(叉)树有2n-1个顶点，则它()片树叶。n2nn-1(4)224、下列哪一种图不一定是树()。(1)无简单回路的连通图(2)有n个顶点n-1条边的

12、连通图(3)每对顶点间都有通路的图(4)连通但删去一条边便不连通的图25、连通图g是一棵树当且仅当g中()。(1)有些边是割边(2)每条边都是割边(3)所有边都不是割边(4)图中存在一条欧拉路径26.对于无向图，下列说法中()是正确的.a.不含平行边及环的图称为完全图b.任何两个不同结点都有边相连且无平行边及环的图称为完全图c.具有经过每条边一次且仅一次回路的图称为哈密尔顿图d.具有经过每个结点一次且仅一次回路的图称为欧拉图27.设图g的邻接矩阵为?00100?00011?10000?01001?01010?则g的边数为().a.5b.6c.3d.428.设图g=v,e，则下列结论成立的是()

13、.a.deg(v)=2?e?b.deg(v)=?e?)。c.?deg(v)?2ed?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.ev+2b.v+e2c.ev2d.e+v+231.无向图g存在欧拉通路，当且仅当().g中所有结点的度数全为偶数b.g中至多有两个奇数度结点c.g连通且所有结点的度数全为偶数d.g连通且至多有两个奇数度结点二、填空题1. 已知图g中有1个1度结点，2个2度结点，3个3度结点，4

14、个4度结点，贝Ug的边数是.2. 设给定图g(如右图所示)，则图g的点割集是.3.设无向图g=v,e是汉密尔顿图，则v的任意非空子集v1,都有？?v1?.4. 设有向图d为欧拉图，则图d中每个结点的入度.5. 设完全图kn有n个结点(n?2),m条边，当时，kn中存在欧拉回路.给定一个序列集合(1,01,10,11,001,000,若去掉其中的兀索合构成前缀码.eda?dbfea?b?fc三、计算题1 .设图g?v,e?,其中v?a1,a2,a3,a4,a5?,e?a1,a2?,?a2,a4?,?a3,a1?,?a4,a5?,?a5,a2?(1)试给出g的图形表示；(2)求g的邻接矩阵；(3)

15、判断图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的邻接矩阵；a2c1569b2d(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

16、,13,17,19,23,29,31,试(1)画出相应的最优二叉树；(2)计算它们的权值.160?6595解：(1)最优二叉树如右图所示：4234531724191055问：如果一组权为2,3,6,9,13,15,能否画出最优二叉树？【篇三：离散数学习题解答第6部分(图论)】1.从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。解用v代表全国城市的集合，e代表各城市间的铁路线的集合,则所成之图g=(v,e)是全国铁路交通图。是一个无向图。 v用代表中国象棋盘中的格子点集，e代表任两个相邻小方格的对角线的集合，则所成之图g=(v,e)是中国象棋中马”所能走的路线图。是一个无

17、向图。 用v代表fortran程序的块集台，e代表任两个程序块之间的调用关系，则所成之图g+(v,e)是fortran程序的调用关系图。是一个有向图。2.画出下左图的补图。解左图的补图如右图所示。3. 证明下面两图同构。v2a图gv3图gv4证存在双射函数？:vtv及双射函数？：ete?(v1)=v1'?(v2)=v2'?(v3)=v3'?(v4)=v4'?(v5)=v5(v6)=v6'?(v1,v2)=(v1；v2')?(v2v3)=(v2；v3')?(v3v4)=(v3；v4')?(v4v5)=(v4；v5)?(v5,v6)=

18、(v5；v6')?(v6v1)=(v6；v1')?(v1,v4)=(v1；v4')?(v2v5)=(v2；v5')?(v3v6)=(v3；v6')显然使下式成立：4. 证明(a),(b)中的两个图都是不同构的。图g中有一个长度为4的圈v1v2v6v5v1，其各顶点的度均为3点,而在图g中却没有这样的圈，因为它中的四个度为3的顶点v1?,v5?,v7?,v3?不成长度的4的圈。图g中有四个二度结点，v6?,v8?,v4?,它们每个都和两个三度结点相邻，而g中一个区样的结点都没有。在(b)中，图g?中有一2度结点v3?，它相邻的两个项点v2?,v4?的度均为

19、4,而在图g中却没有这样的点。ggggv3?v4?5. 一个图若同构于它的外图，则称此图为自补图。在满足下列条件的无向简单图中：1)给出一个五个结点的自补图；2) 有三个或一结点的自补图吗？为什么？3) 证明：若一个图为自补图，则它对应的完全图的边数不清必然为偶数。解1)五个结点的自补图如左图g所示同构函数？：vTv及？：eTe如下：?(a)=a?(b)=c?(c)=e?(d)=b?(e)=d?(a,b)=(a,c)?(b,c)=(c,e)?(c,d)=(e,d)?(d,e)=(b,d)(e,a)=(d,a)ggebae2)(a)没有三个结点的自补图。因为三个结点的完备图的边数为3(3?1)=

20、32为奇数，所以由下面3)的结论，不可能有自补图。(b)有五个结点的自补图。1)中的例子即是一个五个结点的自补图。3)证：一个图是一个自补图，则它对应的完全图的边数必为偶数。实际上，n个项点(n>3)的自补图g,由于其对应的完全图的边数|e*|=n(n?1)n(n?1)，因此有=2|e|，为偶数。这里n>4o对于所有大于或等22于4的正整数，都可表达成n=4k,4k+1,4k+2,4k+3的形式，这里k=1,2,?。其中只有n=4k,4k+1，才能使4k或4k+1形式，(kn)n(n?1)为偶数，所以自补图的项点数只能是26. 证明在任何两个或两个以上人的组内，总存在两个人在组内有

21、相同个数的朋友。证令上述组内的人的集合为图g的项点集v,若两人互相是朋友，则其间联以一边。所得之图g是组内人员的朋友关系图。显然图g是简单图，图中项点的度恰表示该人在组内朋友的个数，利用图g,上述问题就抽象成如下的图认论问题：在简单图g中，若|v|a，则在g中恒存在着两个项点，v1,v2Cv,使得它们的度相等，即deg(v1)=deg(v2)。其证明如下：若存在着一个项点vCv,使得deg(v)=0，则图g中各项点的度最大不超过n-2。因此n个项点的度在集合0,1,2,?,n-2里取值,而这个集合只有n-1个元素，因此，根据鸽笼原理，必有两个项点的度相同。若不存在一个度为零的项点，则图g中各项点的度最大不超过n-1因此n个项点的度在集合1,2,?,n-1中取值，这个集合只有n-1个元素，因此，根据鸽笼原理，必有两具项点的度相同。7.设图g的图示如右所示：1)找出从a到f的所有初级路；2)找出从a到f的所有简单路；3)求由a到f的距离。解1)从a到f的初级路有7条pl:(