资源描述：
《离散数学图论习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章图论综合练习一、单项选择题1．设L是n阶无向图G上的一条通路，则下面命题为假的是()．(A)L可以不是简单路径，而是基本路径(B)L可以既是简单路径,又是基本路径(C)L可以既不是简单路径，又不是基本路径(D)L可以是简单路径，而不是基本路径答案：A2．下列定义正确的是()．(A)含平行边或环的图称为多重图(B)不含平行边或环的图称为简单图(C)含平行边和环的图称为多重图(D)不含平行边和环的图称为简单图答案：D3．以下结论正确是()．(A)仅有一个孤立结点构成的图是零图(B)无向完全图Kn每个结点的度数是n(
2、C)有n(n>1)个孤立结点构成的图是平凡图(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)答案：C6．无向完全图K3的不同构的生成子图的个数为（）．(A)6(B)5(C)4(D)3答案：C7．n阶无向完全图Kn中的边数为（）．(A
3、)(B)(C)n(D)n(n+1)答案：B8．以下命题正确的是()．(A)n(n³1)阶完全图Kn都是欧拉图(B)n(n³1)阶完全图Kn都是哈密顿图(C)连通且满足m=n－1的图(½V½=n,½E½=m)是树(D)n(n³5)阶完全图Kn都是平面图答案：C10．下列结论不正确是()．(A)无向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B)无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C)有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度(D)有向连通图D有有向欧拉路的充分
4、必要条件是除两个结点外，每个结点的入度等于出度答案：D11．无向完全图K4是（）．（A）欧拉图（B）哈密顿图（C）树答案：B12．有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}是一个能构成无向简单图的度数序列，此命题的真值是.答
5、案：02．无向完全图K3的所有非同构生成子图有个．答案：43．设图G=，其中
6、V
7、=n,
8、E
9、=m．则图G是树当且仅当G是连通的，且m=．答案：n－14．连通图G是欧拉图的充分必要条件是．答案：图G无奇数度结点5．连通无向图G有6个顶点9条边，从G中删去条边才有可能得到G的一棵生成树T．答案：46．无向图G为欧拉图，当且仅当G是连通的，且G中无结点．答案：奇数度·223·1·792·8·6图17．设图是简单图，若图中每对结点的度数之和，则G一定是哈密顿图．答案：8．如图1所示带权图中最小生成树的权是．答案：
10、12v1 v2v6v5v3v4图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,v4，v6的度数；(3)判断图G是简单图还是多重图．解：(1)图G的图形如图5所示．(2)．(3)图G是多重图．作图如图2.ahbhhechhd图32．设图G＝，其中V＝{a,b,c,d,e},E={(a,b),(b,c),(c,
11、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中有多少个结点．试作一个满足该条件的简单无向图．图4解：设图G有x个结点，由握手定理2´1+2´2+3´4+3´（x-2-2-3）＝12´2x＝9故图G有9个结点．b·23115c·25·a4·
12、f289163d·15·e图5满足该条件的简单无向图如图4所示2．设图G(如图5表示)是6个结点a,b,c,d,e,f的图，试求，图G的最小生成树，并计算它的权．解：构造连通无圈的图，即最小生成树，用克鲁斯克尔算法：第一步：取ab＝1；第二步：取af=4第三步：取fe＝3；第四步：取ad=9b·231c··a4·f93d··e图6第五步：取bc
