《离散数学图论习题.doc》由会员分享，可在线阅读，更多相关《离散数学图论习题.doc（4页珍藏版）》请在三一文库上搜索。
1、第4章 图论综合练习一、 单项选择题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)答案：C 6无向完全图K3的不同构的生成子图的个数为（ ）(A) 6 (B) 5 (C) 4 (D) 3答案：C 7n阶无向完全图Kn中的边数为（ ）(A) (B) (C) n (D)n(n+1)答案：B8以下命题正确的是( )(A)
3、 n(n1)阶完全图Kn都是欧拉图 (B) n(n1)阶完全图Kn都是哈密顿图(C) 连通且满足m=n1的图(V=n,E=m)是树 (D) n(n5)阶完全图Kn都是平面图答案：C10下列结论不正确是( )(A) 无向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B) 无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等于出度答案：D11无向完全图K4是（ ）（A）欧拉图 （B）哈密顿图 （C）树 答案：B12有4个结点的非同构的无向树有
4、 ( )个 (A) 2 (B) 3 (C) 4 (D) 5答案：A13设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树(A) (B) (C) (D) 答案：A14设G是有6个结点的完全图，从G中删去( )条边，则得到树(A) 6 (B) 9 (C) 10 (D) 15答案：C二、 填空题1数组1，2，3，4，4是一个能构成无向简单图的度数序列，此命题的真值是 .答案：02无向完全图K3的所有非同构生成子图有 个答案：43设图G=，其中|V|=n,|E|=m则图G是树当且仅当G是连通的，且m= 答案：n14连通图G是欧拉图的充分必要条件是 答案：图G无奇数度结点5
5、连通无向图G有6个顶点9条边，从G中删去 条边才有可能得到G的一棵生成树T答案：46无向图G为欧拉图，当且仅当G是连通的，且G中无 结点答案：奇数度 2 2 3 1 7 9 2 8 6 图17设图是简单图，若图中每对结点的度数之和 ，则G一定是哈密顿图答案：8如图1所示带权图中最小生成树的权是 答案：12 v1 v2 v6 v5 v3 v4图2三、化简解答题1设无向图G，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) 写出结点v2,
6、 v4，v6的度数；(3) 判断图G是简单图还是多重图 解：(1) 图G的图形如图5所示(2) (3) 图G是多重图作图如图2. ah bh hech hd图32设图G，其中 Va,b,c,d,e, E=(a,b),(b,c),(c,d), (a,e)试作出图G的图形，并指出图G是简单图还是多重图？是连通图吗？说明理由. 解：图G如图8所示. 图G中既无环，也无平行边，是简单图图G是连通图G中任意两点都连通. 所以，图G有9个结点作图如图3 四、计算题1设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3求G中有多少个结点试作一个满足该条件的简单无向图
7、图4解：设图G有x个结点，由握手定理 21+22+34+3（x-2-2-3）122 x9故图G有9个结点 b 23 1 15c 25 a 4 f 28 9 16 3 d 15 e 图5满足该条件的简单无向图如图4所示2设图G(如图5表示)是6个结点a,b,c, d,e,f的图，试求，图G的最小生成树，并计算它的权解：构造连通无圈的图，即最小生成树，用克鲁斯克尔算法： 第一步： 取ab1；第二步： 取af=4 第三步： 取fe3；第四步： 取ad=9 b 23 1 c a 4 f 9 3 d e 图6 第五步： 取bc=23如图6权为1+4+3+9+23=40 3一棵树T有两个2度顶点，1个3度顶点；3个4度顶点，问它有几片树叶？解：设T有n顶点，则有n1条边T中有2个2度顶点，1个3度顶点，3个4度顶点，其余n21-3个1度顶点 由握手定理： 22+13+34+ (n21-3)=2(n1)解得 n=15于是T有15-6=9片树叶 五、证明题1若无向图G中只有两个奇数度结点，则这两个结点一定是连通的证：用反证法设G中的两个奇数度结点分别为u和v假若u和v不连通 即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点这与握手定理的推论矛盾因而u和v一定是连通的