资源描述：
《离散图论作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、D.以上三个都不是V1V2"30211A(G)=2201011011011_中存在三个顶点U.V和w,使1、设简单无向图G是一个有12条边的4—正则图，则G有(B)个顶点。A.3；B.6；C.9；D.122、设图G(p,q)的补图为则下面说法正确的是(D).A.q+=p(p_D)B.若G(p,q)连通，则Gp不连通C.若G'(p：q')连通，则G(p,q)不连通D.若G(p,q)不连通，则G'(p：q')连通3、无向图G有12条边，度为2,3,4,5,6的顶点各一个，其余顶点均为悬挂点(度为1的点),G屮悬挂点的个数为4・
2、4、设简单无向图G二〈仏，也〉是二分图，则G中(B)奇回路。A.一定包含；B.一定不包含；C.不一定包含；D.不能确定5、简单有向图的基础图(B)简单图.A.一定是B.不一定C.一定不是6、下列四组数种，可以充当4阶无向简单图度数列的为(D)A.(1,2,3,4)B.(0,2,2,3)C.(1,3,3,3)D.(1,1,2,2)7、、任何图中必定有偶数个(C)。A.度数为偶数的点；B.入度为奇数的点；C.度数为奇数的点；D.岀度为奇数的点8、简单图的最大度(B)顶点数。A.大丁-B.小于C.等于1、求下图的关联矩阵M(G)及
3、邻接矩阵A(G)o(4分)2、(7分)设G是简单连通的非完全图，求证:uv.vweE(G),但uw^E(G).证明：反证法。若不然，即对任意的w,v,weV(G),只要wv,vwg£(G),就有mwE(G),也即uveE(G)且vvvgE(G)=>uweE(G).(1)今任取V(G)ortlG连通知，存在(v.,vz)-通路:匕…炉厂(心)・于是由(1)可知：VyV.gE(G)且V.*2GE(G)n啊2GE(G)叫eE(G)且v/2V.GE(G)nvzv.gE(G)啊kwE(G)且vikVjgE(G)=>VfVjgE(G)从
4、而推得简单图G屮任何两个顶点均邻接，即G是一个完全图。此与题设矛盾。2、设G(p,q)是简单图(p是顶点数量，q是边数量)，且q>C；-求证：G是连通图。证明：考虑G的补图乙,因为G的边数q>C；_i,所以乙的边数P*(pT)(#一1)*(〃一2)~~2所以乙不连通，所以G连通。2.已知某有向图G的邻接矩阵如下:"210、00100101比<0010?问：(1)画出图G。(2)试用邻接矩阵求G中长度小于等于2的通路的条数，其中回路有几条？(3)该图是为强连通图还是弱连通图？2、证明：若图G是不连通的，则G的补图乙是连通的。9
5、、下列图屮，不是哈密顿图的为[]o3、无向图G存在欧拉回路，当且仅当G连通且该图14、设G为无向图，若G中恰有n个结点，n-1条边，则(D)。A.一定是连通图B.一定是树C.一定不连通D.以上答案都不对14、下列哪一种图不一定是树(A)A.每个结点间都有通路的图B.有n个结点门-1条边的连通图C.无回路的连通图D.连通但删去一条边则不连通的图4、无向图G有生成树当且仅当o4、设简单连通无向图G(p,q)(p>2)屮有m(l),其余顶点的度数均为k+1。己知删去图G中的k条边后恰构成G的一棵生成树，试
6、用p,k表示叽解：设生成树的边数为qi二p-l;G的边数为q=(mk+(k+1)(p-m))/2=(mk+pk-mk+p-m)/2=(pk+p-m)/2已知删去的边数为k=q-qt于是：k=(pk+p-m)/2-(p-l)=(pk+p-m-2p+2)/2=(pk-p-m+2)/2即:2k二pk-p-m+2故：m二pk-p+-2k+2二p(k-1)-2(k-1)二(k-1)(p-2)。2、一个有限平面图G的每个面的次数Z和S与G的边数qZ间的关系为S二2*q。12.设G是连通平面图，G中有6个顶点8条边，则G的面的数目为(B)
7、A.5B.4C.3D.22、一个有限平面图G的每个面的次数之和为&则G的边数°二4。1、设简单连通平面图G有9个顶点，英顶点的度分别是2,2,2,3,3,3,447,试求该图的面数(要求写出计算过程，否则得分为0)。解:已知图G的顶点数和各顶点度,利用2q=Ed(Vi)(i=l,-,p)求出边数。再利用欧拉公式p-q+r=2求面数ro这里p二9;q二(2+2+2+3+3+3+4+4+7)/2二30/2二15；代入欧拉公式：p-q+r二29T5+r二2/.r=85、设下图所示赋权图表示某7个城市V!v2....v7及预先测算出
8、的它们之间的一些直接通信线路的造价，试给出一个设计方案，使得各城市之间能够通信，而又使总造价最小。解：利用K算法：第一步，选el=(vl,v7),w(el)=l第二步，选e2=(v3,v4),w(e2)=3第三步，选e3=(v2,v7),w(e3)=4第四步，选e4=(v3,v7),w(e
