离散数学图论练习题.doc

(完整word版)离散数学图论练习题图论练习题一.选择题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、一个图的欧拉回路是一条通过图中( )的回路。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中至少存在( )片树叶。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) 224、下列哪一种图不一定是树（ ）。(1) 无简单回路的连通图(2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图25、连通图G是一棵树当且仅当G中（ ）。(1) 有些边是割边(2) 每条边都是割边(3) 所有边都不是割边 (4) 图中存在一条欧拉路径26对于无向图，下列说法中（ ）是正确的.A不含平行边及环的图称为完全图B任何两个不同结点都有边相连且无平行边及环的图称为完全图C具有经过每条边一次且仅一次回路的图称为哈密尔顿图D具有经过每个结点一次且仅一次回路的图称为欧拉图27设图G的邻接矩阵为则G的边数为( )A5 B6 C3 D428设图G，则下列结论成立的是 ( )Adeg(V)=2E Bdeg(V)=EC D29图G如右图所示，以下说法正确的是 ( ) A(a, d)是割边B(a, d)是边割集ooooocabedofC(d, e)是边割集D(a, d) ,(a, c)是边割集 30设G是连通平面图，有v个结点，e条边，r个面，则r= ( )Aev2 Bve2 Cev2 Dev231无向图G存在欧拉通路，当且仅当( )AG中所有结点的度数全为偶数 BG中至多有两个奇数度结点CG连通且所有结点的度数全为偶数DG连通且至多有两个奇数度结点二、填空题ooooocabedof1已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 2设给定图G(如右图所示)，则图G的点割集是 3设无向图G是汉密尔顿图，则V的任意非空子集V1，都有 V14设有向图D为欧拉图，则图D中每个结点的入度 5设完全图K有n个结点(n2)，m条边，当 时，K中存在欧拉回路6给定一个序列集合1，01，10，11，001，000，若去掉其中的元素 ，则该序列集合构成前缀码三、计算题1设图G=，其中V=a1, a2, a3, a4, a5,E=，（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的图形；ooooocabedof152261938（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）画出相应的最优二叉树；ooooooooo3271355111734oo1602910ooo231942oo17o24o5331ooo9565（2）计算它们的权值解：（1）最优二叉树如右图所示：问：如果一组权为2,3,6,9,13,15,能否画出最优二叉树？6