资源描述：
《离散数学练习第6-7章图论（无答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一.选择/填空1、ro1°设图G的邻接矩阵为II01001001111ooool,第6-7章则G的边数为（)・0ILoB.A.52、100111010IJ6(c)C.3D.4与（d）如下图所示，则下列结论成立的是（）.3、A.（6F）是强连通的C・（c）是强连通的给定无向图G如下图所示,B.（Z?）是强连通的D.（d）是强连通的下面给出的结点集子集中，不是点割集的为（）・{b9d}A.以下说法正确的是（）・B.{d}D.{b.e}A.@,c)}是割边B.{(67,C)}是边割集C.{(b,c)}是边割集D.{(ec),(b,c)}是边
2、割集5、无向图G存在欧拉通路，当且仅当（）.A.G中所有结点的度数全为偶数B・G屮至多有两个奇数度结点C・G连通且所有结点的度数全为偶数D・G连通且至多有两个奇数度结点6、设G是有n个结点，加条边的连通图，必须删去G的（）条边，才能确定G的一棵生成树.A.m—n+1B.m-nC.m+n+/D.n-m+7、已知一棵无向树T屮有8个结点，4度，3度，2度的分支点各一个，T的树叶数为()・A.8B.5C・4D.38、己知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是・9、连通无向图G有6个顶点9条边，从G中删
3、去条边才有可能得到G的一棵生成树T.10、如右图相对于完全图K5的补图为()。11、[B][C][D]G=如下图所示，下面哪个边集不是其边割集(A、｛,｝；B、｛,｝;C、｛｝；D、｛,/o12、设D是有n个结点的有向完全图，则图D的边数为()(A)n(n-7)(B)/?(«+1)(C)n(n+7)/2(D)n(n-1)/213、无向图G是欧拉图，当且仅当()(A)G的所有结点的度数都是偶数(B)G的所有结点的度数都
4、是奇数(C)G连通且所有结点的度数都是偶数(D)G连通且G的所有结点度数都是奇数。14、n阶完全图Kn的边数为15、右图的邻接矩阵A二V116、任何gm)图G二(VJE),边数与顶点度数的关系则T中有18、已知一棵无向树T有三个3顶点，一个2度顶点，其余的都是1度顶点,个1度顶点。19、下面四组数能构成无向图的度数列的有（）。A、2)4567；B、12234；C、2,1,1,1,2；20、的邻接矩阵为（)°A、11011000000](11I100；B、111111111111、111卩；(0
5、021、下列图中是欧拉图的有（10C>
6、1111001010000°
7、1I1OP0)[D]22、下面给出的集合中，哪一个是前缀码？（(1){0,10,110,101111)(2){01,001,000,1}(3){b,c,aa,ab,aba}⑷{1,11,101,001,0011}23、一棵树有2个2度顶点,1个3度顶点，3个4度顶点，则其1度顶点为（(1)5(2)724＞下图中既不是Eular图，也不是Hamilton图的图是（）25、26、27、(0)一棵无向树的顶点数n与边数m关系是(有n个结点的树，其结点度数Z和是(下面给出的集合中，哪一个不是前缀码()。)°1}(
8、1){a,ab,110,albll}(2){01,001,000,(3){1,2,00,01,0210}(4){12,11,101,002,0011}28、n个结点的有向完全图边数是()，每个结点的度数是()。29、设G是一棵树，分别表示顶点数和边数，则()(1)n=m(2)m=n+l(3)n=m+l(4)不能确定。30、任何连通无向图G至少有()棵生成树。31、设无向图G有16条边且每个顶点的度数都是2,则图G有()个顶点。(1)10(2)4(3)8(4)1632、任一有向图中，度数为奇数的结点有()个。33、在有n个顶点的连通图中
9、，其边数(),(3)最多有n条(4)至少有n条34、在如下各图屮()欧拉图。ID)二.综合题1、设G=,V={VI,V2,V3,V4,V5),E={(V1,V3),(V2,V3),(V2,V4),(V3,V4),(V3,V5),(V4,V5)},试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画岀其补图的图形.2、图G=,其中V={ayb,c,d,e,f},E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(〃,/),(e,fi},对应边的权值
10、依次为5,2,1,2,6,1,9,3及8.(1)画出G的图形；(2)写出G的邻接矩阵；(3)求出G权最小的生成树及其权值.3、己知带权图G如右图所示.(1)求图G的最小生成树；(2)计算该生成树的权值.4、设有一组权为2
