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

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，00113、一个图的哈密尔顿路是一条通过图中 ()的路。4、设 G 是一棵树，则 G 的生成树有 ()棵。(1) 0 (2) 1 (3) 2 (4) 不能确定5、n 阶无向完全图 Kn 的边数是 ()，每个结点的度数是 ()。6、一棵无向树的顶点数 n 与边数 m 关系是 ( )。7

2、、一个图的欧拉回路是一条通过图中 ()的回路。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 个结点的有向完全图边数是 ( )，每个结点的度数是 ()。11、一个无向图有生成树的充分必要条件是 ()。12、设 G 是一棵树， n,m 分别表示顶点数和边数，则(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。13、 设 T=V,E是一棵树，若|V|1，则 T

3、 中至少存在()片树叶。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) 16218、 设无向图 G 有 18 条边且每个顶点的度数都是 3，则图 G 有()个顶点。(1) 10(2) 4(3) 8 (4

4、) 1219、任一有向图中，度数为奇数的结点有 () 个。20、具有 6 个顶点， 12 条边的连通简单平面图中，每个面都是由 ()条边围成？(1) 2 (2) 4 (3) 3 (4) 521、在有 n 个顶点的连通图中，其边数( )。最多有 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) 224、

5、下列哪一种图不一定是树()。(1) 无简单回路的连通图 (2) 有 n 个顶点 n-1 条边的连通图(3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图25、连通图 G 是一棵树当且仅当 G 中( )。(1) 有些边是割边 (2) 每条边都是割边(3) 所有边都不是割边 (4) 图中存在一条欧拉路径 26对于无向图，下列说法中( )是正确的 .A 不含平行边及环的图称为完全图B 任何两个不同结点都有边相连且无平行边及环的图称为完全图C.具有经过每条边一次且仅一次回路的图称为哈密尔顿图D .具有经过每个结点一次且仅一次回路的图称为欧拉图27.设图 G 的邻接矩阵为0010 000

6、01 11000 00100 101010则 G 的边数为 () .A . 5B.6C.3D. 4328.设图 G= ,则下列结论成立的是().A . deg(V)=2 EB.deg(V)= E4C.deg(v) 2 Ev V29 图 G 如右图所示，以下说法正确的是A . (a, d)是割边B.(a, d)是边割集C.(d, e)是边割集D . (a, d) ,(a, c)是边割集B . G 中至多有两个奇数度结点C . G 连通且所有结点的度数全为偶数D.G 连通且至多有两个奇数度结点、填空题1 .已知图 G 中有 1 个 1 度结点，2 个 2 度结点，3 个 3 度结点，4 个 4 度

7、结点，则 G 的边数是_.2.设给定图 G(如右图所示)，则图 G 的点割集是3. 设无向图 G= 是汉密尔顿图，则 V 的任意非空子集 V1，都有_ V1.4._ 设有向图 D 为欧拉图，则图 D 中每个结点的入度 _.5 .设完全图 Kn有 n 个结点(n 2), m 条边，当 _时，Kn中存在欧拉回路.合构成前缀码.D.deg(v) Ev V( ).30 .设 G 是连通平面图，有 v 个结点，A . e- v + 2B . v+ e- 231.无向图 G 存在欧拉通路，当且仅当A . G 中所有结点的度数全为偶数e 条边，r 个面，则 r=().C . ev2D . e+ v+26.给

8、定一个序列集合1 , 01, 10, 11, 001, 000，若去掉其中的元素_，则该序列集cd5二、计算题1 .设图 G V, E，其中 V ai, a2, a3, a4, a5,E ai, a2, a2, a4, a3, ai, a4, a5, a5, a2(1) 试给出 G 的图形表示；(2) 求 G 的邻接矩阵；(3) 判断图 G 是强连通图、单侧连通图还是弱连通图？(d, e), (d, f), (e, f)，对应边的权值依次为(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.图 G=，其中