(完整word版)离散数学图论练习题.pdf

上传人：H****o

文档编号：55056294

上传时间：2022-10-29

格式：PDF

页数：4

大小：70.25KB

( 4.5 )

《(完整word版)离散数学图论练习题.pdf》由会员分享，可在线阅读，更多相关《(完整word版)离散数学图论练习题.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 图论练习题一.选择题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

2、个结点的树，其结点度数之和是()。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 的生成树只有一

3、棵。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)16 18、设无向图 G 有 18 条边且每个顶点的度数都是3，则图 G 有()个顶点。(1)10(2)4(3)8(4)12 2 19、任一有向图中，度数为奇数的结点有()个。20、具有 6 个顶点，12 条边的连通简单平面图中，每个面都是由()条边围成？(1)2(2)4(3)3(

4、4)5 21、在有 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)9 23、若一棵完全二元（叉）树有2n-1 个顶点，则它（）片树叶。(1)n(2)2n(3)n-1(4)2 24、下列哪一种图不一定是树（）。(1)无简单回路的连通图(2)有 n 个顶点 n-1 条边的连通图(3)每对顶点间都有通路的图(4)连通但删去一条边便不连通的图25、连通图 G 是一棵树当且仅当G 中（）。(1)有些边

5、是割边(2)每条边都是割边(3)所有边都不是割边(4)图中存在一条欧拉路径26对于无向图，下列说法中（）是正确的.A不含平行边及环的图称为完全图B任何两个不同结点都有边相连且无平行边及环的图称为完全图C具有经过每条边一次且仅一次回路的图称为哈密尔顿图D具有经过每个结点一次且仅一次回路的图称为欧拉图27设图 G 的邻接矩阵为0101010010000011100000100则 G 的边数为()A 5 B6 C3 D 4 28设图 G，则下列结论成立的是()Adeg(V)=2EBdeg(V)=E文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B

6、6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G

7、9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O

8、7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K

9、2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y

10、8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K

11、10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码

12、:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K103 CEvVv2)deg(DEvVv)deg(29图 G 如右图所示，以下说法正确的是()A(a,d)是割边B(a,d)是边割集C(d,e)是边割集D(a,d),(a,c)是边割集30设 G 是连通平面图，有v个结点，e 条边，r 个面，则r=()Aev2 Bv e2 C

13、ev2 Dev2 31无向图G 存在欧拉通路，当且仅当()AG 中所有结点的度数全为偶数B G 中至多有两个奇数度结点C G 连通且所有结点的度数全为偶数DG 连通且至多有两个奇数度结点二、填空题1已知图G 中有 1 个 1 度结点，2 个 2 度结点，3 个 3 度结点，4 个 4 度结点，则G 的边数是2设给定图G(如右图所示)，则图 G 的点割集是3设无向图G是汉密尔顿图，则V 的任意非空子集V1，都有V14设有向图D 为欧拉图，则图D 中每个结点的入度5设完全图Kn有 n 个结点(n 2)，m 条边，当时，Kn中存在欧拉回路6给定一个序列集合1，01，10，11，001，000，若去掉

14、其中的元素，则该序列集合构成前缀码cabedfcabedf文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 H

15、Q8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3

16、C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 Z

17、O8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4

18、V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文

19、档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW

20、10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K104 三、计算题1设图 GV，E，其中 Va1,a2,a3,a4,a5,Ea1,a2，a2,a4，a3,a1，a

21、4,a5，a5,a2（1）试给出G 的图形表示；（2）求 G 的邻接矩阵；（3）判断图G 是强连通图、单侧连通图还是弱连通图？2图 G=，其中 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 的邻接矩阵；（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

22、，1，9，那么会求吗？3设有一组权为2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二叉树；（2）计算它们的权值解：（1）最优二叉树如右图所示：问：如果一组权为2,3,6,9,13,15,能否画出最优二叉树？cabedf1522619383 2 7 13 5 5 11 17 34 160 29 10 23 19 42 17 24 53 31 95 65 文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O

23、7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K

24、2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y

25、8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K

26、10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码

27、:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B

28、6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10文档编码:CW10B6F4B5G9 HQ8O7T3C5K2 ZO8Y8N4V1K10

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

4.3 金币

版权申诉 word格式文档无特别注明外均可编辑修改；预览文档经过压缩，下载后原文更清晰！ 立即下载

配套讲稿：: 如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
特殊限制：: 部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
关键词：: 完整 word 离散数学练习题

淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。

限制150内

关于本文

本文标题：(完整word版)离散数学图论练习题.pdf
链接地址：https://www.taowenge.com/p-55056294.html