2022年2022年离散数学图论练习题 .pdf

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 个结点的树，其结点度数之和是()。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) 16 18、设无向图 G 有 18 条边且每个顶点的度数都是3，则图 G 有( )个顶点。(1) 10 (2) 4 (3) 8 (4) 12 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 2 19、任一有向图中，度数为奇数的结点有()个。20、具有 6 个顶点， 12 条边的连通简单平面图中，每个面都是由()条边围成？(1) 2(2) 4(3) 3(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) 有些边是割边(2) 每条边都是割边(3) 所有边都不是割边(4) 图中存在一条欧拉路径26对于无向图，下列说法中（）是正确的 . A不含平行边及环的图称为完全图B任何两个不同结点都有边相连且无平行边及环的图称为完全图C具有经过每条边一次且仅一次回路的图称为哈密尔顿图D具有经过每个结点一次且仅一次回路的图称为欧拉图27设图 G 的邻接矩阵为0101010010000011100000100则 G 的边数为 ( )A 5 B6 C3 D4 28设图 G，则下列结论成立的是( )Adeg(V)=2EBdeg(V)=E名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 3 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 Cev2 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，若去掉其中的元素，则该序列集合构成前缀码cabedfcabedf名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 4 三、计算题1设图 GV，E ，其中 Va1, a2, a3, a4, a5, Ea1, a2， a2, a4， a3, a1， a4, 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，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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -