资源描述：
《离散数学测验题--图论部分》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、离散数学图论单元测验题一、单项选择题(本大题共10小题，每小题2分，共20分)1、在图G=中，结点总度数与边数的关系是()(A)deg(v,)=2
2、£
3、(B)deg(v,-)=
4、E
5、(C)^deg(v)=2
6、E
7、(D)^deg(v)=
8、EveVveV2、设D是刀个结点的无向简单完全图，则图D的边数为()(A)(B)/?(/?+1)(C)n(n—)/2(D)血汁1)/23、设G=为无向简单图，4(G)为G的最大度数，则有(A)A(G)<77(B)A(G)n(D)A(G)>/z4、图G与G的结点和边分别存在一一对应关系，是G9G(同构)
9、的()(A)充分条件(B)必要条件(C)充分必要条件(D)既非充分也非必要条件5、设V={a,b,c9d}f则与V能构成强连通图的边集合是()(A)E={..,,](B)E={,,,,](C)E={,,,,}6、有向图的邻接矩阵屮，行元素Z和是对应结点的(),列元素之和是对应结点的()(A)度数(B)出度(C)最大度数(D)入度7、设图G的邻接矩阵为00100-00011100000100101010则G的边数为().A.5B.
10、6C.3D-48、设G=,
11、V
12、=n,
13、£
14、=m为连通平面图且有厂个面，则厂=()(A)m~n+2(B)n—m—2(C)n+m-2(D)〃?+t?+2二、填空题(本大题共10小题，每题2分，共20分)9、在5个结点的二元完全树中，若有4条边，则有()片树叶。(A)2(B)3(C)510、图2是()(A)完全图(B)欧拉图(D)4(C)平面图图21、设图G=,若,则&是G的真子图，若，则G是G的生成子图.2、设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有条边，G的总度数是,G的分支点数是,G中度数为3的结点数是・3、一棵树有两个结点度
15、数为2,—个结点度数为3,三个结点度数为4,问它有儿个度数为1的结点。4、画出满足下列条件的图：(1)画一个有一条欧拉冋路和一条哈密顿冋路的图；(2)画一个有一条欧拉回路，但没有哈密顿回路的图；(3)画一条没有欧拉路，但有一条哈密顿冋路的图.5、设G是〃个结点的简单图，若G中每对结点的度数之和,则G—定是哈密顿图.6、一个有向树T称为根树，若,其中称为树根，称为树叶■7、设G是平面图,G有8个面，每个面的度数都是3,则G有条边,G有个顶点。8、设G是有个结点，加条边的连通图，要确定G的一棵生成树，必须删去G的条边.9、在下图屮，哪些是欧拉图？哪些是哈密顿图？哪些是平面图？⑷(
16、2)10、设G是n阶无向带权边连通图，各边的权均为a(a>0),设T是G的一棵最小生成树,则T的权W(T)=(n-1)*a。三、计算题(本大题共4小题，每小题10分，共40分)1、设G=是一个无向图，V={vpv2,...,v8},^={(vpv2),(v2,V3X(V3,V)X(V),v5x(v5,v4X(V3,V4X(V7,V8)}(1)G=的IS，丨创各是多少？(2)画出G的图示；(3)指岀与内邻接的结点，以及与卩关联的边；(4)指出与©关联的结点；(5)该图是否有孤立结点和孤立边？(6)求出各结点的度数；2、设图G是具有3个顶点的无向完全图，试问(
17、1)G有多少个子图？(2)G有多少个生成子图？(3)如果没有任何两个子图是同构的，则G的子图个数是多少？将它们构造出来.3・图G=,其中V={a,b,c,d,e,f}9E={(a,b),(a,c),(a,e)9(b,d),(b,e)9(c,e)f(d,e),(d,对应边的权值依次为5,2,1,2,6,1,9,3及&(1)画出G的图形;(2)写出G的邻接矩阵；(3)求出G权最小的生成树及其权值.4.设有一组权为2,3,5,7,11,13,17,19,23,29,31，试(1)画出相应的最优二叉树；(2)计算它们的权值.四、证明题(本大题共3小题，任选2题，每小题10分
18、，共20分)1.若无向图G中只有两个奇数度结点，则这两个结点一定是连通的.2.设G是一个n阶无向简单图，斤是大于等于2的奇数.证明图G与它的补图乙屮的奇数度顶点个数相等.k3.设连通图G有R个奇数度的结点，证明在图G中至少要添加一条边才能使其成为2欧拉图.补充1、若图G是不连通的，则G的补图G是连通的。2、当且仅当G的一条边e不包含在G的回路中吋，e才是G的割边。3、设G是简单平面图，则它一定有一个度数W5的结点。解答：一、单项选择题(本大题共10小题，每小题2分，共20分)1、在图G=中，结
