2023年电大离散数学图论部分期末复习辅导

离散数学图论部分期末复习辅导一、单项选择题１．设图G=＜V,Ｅ>,vV,则下列结论成立的是().A．ｄｅg(v)=2ＥB．ｄeg(ｖ)=EC．Ｄ.解根据握手定理(图中所有结点的度数之和等于边数的两倍）知，答案C成立。答Ｃ2．设无向图Ｇ的邻接矩阵为，则G的边数为(）．A．６Ｂ．5C.4D.3解由邻接矩阵的定义知，无向图的邻接矩阵是对称的.即当结点vｉ与vj相邻时,结点vj与ｖi也相邻，所以连接结点ｖi与vj的一条边在邻接矩阵的第ｉ行第j列处和第j行第i列处各有一个１，题中给出的邻接矩阵中共有1０个1，故有102=5条边。答Ｂ3．已知无向图G的邻接矩阵为，则G有().A．5点,8边B．６点，7边C．６点，8边Ｄ.５点，7边解由邻接矩阵的定义知，矩阵是5阶方阵，所以图G有５个结点，矩阵元素有14个1,１４÷2=7,图G有7条边。答Dabcd图一eA．{(a,e)}是割边B.{(a，ｅ）}是边割集C．{(a,e),(b,ｃ）}是边割集Ｄ．{(d,e)}是边割集定义3.2.9设无向图G=<V,E>为连通图,若有边集E1ÌE,使图G删除了E１的所有边后，所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图仍是连通图，则称E１是Ｇ的一个边割集．若边割集为单元集｛e},则称边e为割边(或桥）．解割边一方面是一条边,由于答案A中的是边集，不也许是割边，因此答案Ａ是错误的.删除答案B或Ｃ中的边后，得到的图是还是连通图,因此答案Ｂ、C也是错误的.在图一中,删去(ｄ，ｅ)边,图就不连通了，所以答案Ｄ对的．答D注：假如该题只给出图的结点和边,没有图示,大家也应当会做．如：若图G＝<Ｖ,E>,其中V=｛a,b,c，d,e}，E＝{(a,ｂ),(a,c),(a,ｅ),(b,c),(b,ｅ),(c,ｅ),（e，ｄ)}，则该图中的割边是什么?5.图Ｇ如图二所示,以下说法对的的是（)．aabcd图二Ｂ．｛b，ｃ｝是点割集Ｃ．{b,d｝是点割集D.{c}是点割集定义3.２.7设无向图G=<V,E>为连通图，若有点集V1ÌV,使图Ｇ删除了V1的所有结点后,所得的子图是不连通图，而删除了V1的任何真子集后，所得的子图仍是连通图,则称V1是G的一个点割集.若点割集为单元集{v},则称结点v为割点．解在图二中，删去结点a或删去结点c或删去结点b和d图还是连通的,所以答案A、Ｃ、D是错误的.在图二中删除结点b和ｃ,得到的子图是不连通图,而只删除结点ｂ或结点c,得到的子图仍然是连通的,由定义可以知道,｛b,c}是点割集.所以答案B是对的的.答Baabcd图三A.{（a,d)}是割边B.{（ａ,d)｝是边割集C.{(a,d),(ｂ,d)}是边割集Ｄ.{(b,d)}是边割集解割边一方面是一条边，{(a,ｄ）}是边集，不也许是割边．在图三中,删除答案B或D中的边后,得到的图是还是连通图.因此答案A、B、D是错误的．在图三中，删去(a，d）边和（b,d)边,图就不连通了，而只是删除(ａ,d)边或(b,d)边，图还是连通的,所以答案Ｃ对的.7．设有向图（a)、（b）、(c）与（d)如图四所示，则下列结论成立的是().图四A.（ａ）是强连通的Ｂ.(b)是强连通的C.（ｃ)是强连通的Ｄ.（d）是强连通的复习：定义3.２．5在简朴有向图中,若在任何结点偶对中,至少从一个结点到另一个结点可达的，则称图G是单向（侧）连通的；若在任何结点偶对中，两结点对互相可达，则称图G是强连通的；若图G的底图，即在图G中略去边的方向，得到的无向图是连通的，则称图G是弱连通的.显然,强连通的一定是单向连通和弱连通的，单向连通的一定是弱连通，但其逆均不真．定理3.2．1一个有向图是强连通的,当且仅当Ｇ中有一个回路，其至少包含每个结点一次.单侧连通图判别法:若有向图G中存在一条通过每个结点至少一次的路，则G是单侧连通的。答Ａ(有一条通过每个结点的回路)问：上面的图中，哪个仅为弱连通的?答：图(ｄ)是仅为弱连通的请大家要复习“弱连通”的概念.８．设完全图K有n个结点(n2)，m条边,当()时，Ｋ中存在欧拉回路.A．ｍ为奇数B．n为偶数Ｃ．n为奇数D.m为偶数解完全图Ｋ每个结点都是n１度的，由定理4.１.1的推论知Ｋ中存在欧拉回路的条件是n1是偶数,从而n为奇数。答C提醒:前面提到n阶无向完全图Ｋn的每个结点的度数是n-1,现在要问:无向完全图Kn的边数是多少？答：n（n–1)/29.若G是一个汉密尔顿图，则G一定是（).Ａ．平面图Ｂ.对偶图Ｃ．欧拉图D．连通图定义４．2．1给定图Ｇ，若存在一条路通过图G的每个结点一次且仅一次,则该路称为汉密尔顿路；若存在一条回路通过图G的每个结点一次且仅一次，则该回路称为汉密尔顿回路；具有汉密尔顿回路的图称为汉密尔顿图.由定义可知,汉密尔顿图是连通图.答D10.若Ｇ是一个欧拉图,则Ｇ一定是().Ａ．平面图Ｂ．汉密尔顿图C.连通图D.对偶图定义4.1.1给定无孤立结点图G，若存在一条路通过图G的每条边一次且仅一次，则该路称为欧拉路.（即，若存在一条回路通过图G的每条边一次且仅一次，则该回路称为欧拉回路．具有欧拉回路的图就称为欧拉图.由定义可知，欧拉图是连通图．答C１１．设G是连通平面图,有v个结点，e条边，r个面，则r=(）．A．ｅ-ｖ＋2B.v+e－２C.e-v-２Ｄ．e+v+2答A(定理4.３．2:欧拉公式v-e+ｒ2）问：假如连通平面图Ｇ有4个结点,7条边，那么图G有几个面？12．无向树Ｔ有８个结点,则Ｔ的边数为()．A.6B．７C.８D.９ 13.无向简朴图G是棵树,当且仅当(）.Ａ.G连通且边数比结点数少1Ｂ.G连通且结点数比边数少1Ｃ．Ｇ的边数比结点数少１D.G中没有回路.答A（定理5.1.1（树的等价定义)）14.已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个，T的树叶数为(）．Ａ．8B．５C解这棵无向树Ｔ有7条边，所有结点的度数之和为1４，而4度、3度、2度的分支点各一个共3个结点占用了9度，所以剩下的５个结点占用5度,即这5个结点每个都是１度结点，故有5片树叶．答B15．设G是有ｎ个结点，ｍ条边的连通图,必须删去G的()条边，才干拟定G的一棵生成树.A.B.C．D．答A（n个结点的连通图的生成树有条边,必须删去条边）１６.设无向图G的邻接矩阵为,则G的边数为()．Ａ．1B.6C.7D.1４ ﻩ答C１7.如图二(下图)所示，以下说法对的的是().Ａ．e是割点B．{a,e}是点割集C.{b,ｅ}是点割集Ｄ．｛d}是点割集图二答A18.设有向图（a）、（b）、(c）与（d）如图六（下图)所示,则下列结论成立的是()．图六A.(a）只是弱连通的Ｂ.（b)只是弱连通的Ｃ．(c）只是弱连通的D.（d）只是弱连通的ﻩ 答Ｄ19.无向完全图K4是（).A.欧拉图B．汉密尔顿图C．非平面图Ｄ．树ﻩﻩﻩ答B20．以下结论对的的是().Ａ.无向完全图都是欧拉图B.有n个结点n－1条边的无向图都是树Ｃ．无向完全图都是平面图Ｄ．树的每条边都是割边 答Ｄ二、填空题1．已知图Ｇ中有１个1度结点，２个2度结点，3个3度结点，4个4度结点,则G的边数是.解设Ｇ有x条边,则由握手定理,，答15２.设给定图G(如右由图所示),则图G的点割集是．解从图G中删除结点f,得到的子图是不连通图,即结点集{f}是点割集;从图Ｇ中删除结点ｃ和e，得到的子图是不连通图，而只删除ｃ或e，得到的子图仍然是连通的,所以结点集{c,ｅ}也是点割集.而其他结点集都不满足点割集的定义的集合，所以应当填写：{ｆ}、｛c，e}答{f｝、｛c,e}提醒:若ｆ是图G的割点，则{ｆ}是图Ｇ的点割集，删除f点后图Ｇ是连通吗？3.设G是一个图，结点集合为Ｖ，边集合为E,则Ｇ的结点等于边数的两倍．答的度数之和4.无向图G存在欧拉回路，当且仅当G连通且．答G的结点度数都是偶数（定理4.１.１的５．设G＝<V,E>是具有n个结点的简朴图，若在G中每一对结点度数之和大于等于,则在G中存在一条汉密尔顿路.答ｎ1(定理4．2.2)6.若图G＝<V,E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除Ｓ中的所有结点得到的连通分支数为Ｗ,则S中结点数|S|与W满足的关系式为．答W|S|(定理4.2.17．设完全图K有n个结点(ｎ2)，m条边,当时,K中存在欧拉回路．答n为奇数（同一、８题）８．结点数v与边数e满足关系的无向连通图就是树．答ev1（定理5．1．1(树的等价定义)）９．设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去条边后使之变成树.解由握手定理（定理３.1．１)知道图Ｇ有18２=9条边,又由定理５.1.１中给出的图T为树的等价定义之一是“图Ｔ连通且ｅ=v-1”，可以知道答410.设正则5叉树的树叶数为17，则分支数为i=．答４（定理5.2．1:(m-1)i=t-1）三、判断说明题（判断下列各题，并说明理由．）1．假如图G是无向图，且其结点度数均为偶数,则图Ｇ存在一条欧拉回路．解错误．只有当Ｇ是连通图且其结点度数均为偶数时，图G才存在一条欧拉回路．2.如下图所示的图G存在一条欧拉回路．解错误.由于图Ｇ有两个奇数度(3度)结点，所以不存在欧拉回路.注：这是一个汉密尔顿图,但不是欧拉图。可见汉密尔顿图不一定是欧拉图．其实,欧拉图也不一定是汉密尔顿图.如下图所示,图（1）是欧拉图又是汉密尔顿图，图（２)是欧拉图但不是汉密尔顿图，图(3)不是欧拉图但它是汉密尔顿图,图（４)不是欧拉图也不是汉密尔顿图。3．如下图所示的图G不是欧拉图而是汉密尔顿图.图G解对的．图G有4个3度结点ａ，b，d，f,所以图Ｇ不是欧拉图．图Ｇ有汉密尔顿回路ａbefgｄca，所以图G是汉密尔顿图．4．设G是一个有7个结点16条边的连通简朴图，则Ｇ为平面图．解错误．由定理4.3．3知,若Ｇ有v个结点e条边,且v3，则e≤3v６．但本题中，16≤3×７６不成立．5．设G是一个连通平面图,且有6个结点11条边,则G有7个面．解对的.由欧拉定理，连通平面图G的结点数为v，边数为ｅ，面数为r,则ｖｅ+r=2．于是有ｒ=2v＋ｅ=2６+11=７．问：“完全图Ｋ6是平面图”是否对的?答不对的.由于完全图Ｋ６有6个结点15条边，且1536－6=1２，即e3ｖ-6对Ｋ6不成立，所以Ｋ６不是平面图.四、计算题１.设Ｇ=＜V，E>,Ｖ＝{v１，v2，ｖ3,ｖ4,v5}，E={（ｖ1,v３),(v2，ｖ3),（ｖ2,v4),(v3,v４)，（v3,ｖ5)，(v4,v5)},试(1）给出G的图形表达;(２)写出其邻接矩阵；(3)求出每个结点的度数;(4)画出其补图的图形.解（1）Ｇ的图形为:(2)图G的邻接矩阵为:（3）图Ｇ的每个结点的度数为：，，,,．(4)由关于补图的定义3.1．9可知,先在图G补充边画出完全图(见下面左图)，然后去掉原图的边,可得图G补图（见下面右注意:补图中，假如没有标出结点v3,则是错的.2.图G=<V,E＞，其中V＝{ａ,ｂ,c,d,e}，Ｅ＝｛(a,b),（a,c),(a,e),(b,ｄ）,(ｂ，ｅ),(c,e),(c，d）,（d，ｅ)}，相应边的权值依次为2、１、2、3、６、1、4及5，试（1)画出Ｇ的图形；(2）写出G的邻接矩阵；（3）求出Ｇ权最小的生成树及其权值．解(1）G的图形如左下图：(2）G的邻接矩阵为:（３)图G有5个结点，其生成树有4条边，用Ｋruｓｋａｌ算法求其权最小的生成树T：第１步，取具最小权1的边（a,c）；第２步,取剩余边中具最小权1的边(c，e)；第3步,取剩余边中不与前２条边构成回路的具最小权２的边（ａ,ｂ)；第4步,取剩余边中不与前3条边构成回路的具最小权３的边(b,d).所求最小生成树T如下图，其权为．注意：在用避圈法求最小的生成树的关键是:“取图中权数最小的边,且与前面取到的边不构成圈”，很多学生只注意到取权数最小的边了，而忽略了“不构成圈”的规定。假如题目给出如解（1)中所示赋权图，规定用Kruskal算法（避圈法）求出该赋权图的最小生成树,大家应当会吧．３．已知带权图Ｇ如右图所示.(１)求图G的最小生成树;（２)计算该生成树的权值.解（1)图Ｇ有6个结点，其生成树有５条边，用Kruskａl算法求其权最小的生成树T：第1步,取具最小权1的边；第2步,取剩余边中具最小权2的边；第3步，取剩余边中不与前2条边构成回路的具最小权3的边;第４步,取剩余边中不与前３条边构成回路的具最小权5的边;第5步，取剩余边中不与前４条边构成回路的具最小权7的边.所求最小生成树Ｔ如右图．（２)该最小生成树的权为.4.设有一组权为2,3,5,7,17,３1,试画出相应的最优二叉树,计算该最优二叉树的权.解（Ｈuffman算法）:一方面组合２+3,求带权5,5,7,１７，31的最优二叉树;再组合5+5,求带权７,10,1７,31的最优二叉树；然后组合7+10，求带权17,17,31的最优二叉树;继续组合１７+17，求带权31，3４的最优二叉树；最后组合31+3４,得65,这是树根所带的权。可从树根开始往下画，即得所求最优二叉树T如下图:所求最优二叉树T的权为:讲评：作业中最优二叉树往往都能画对了,但计算总权值时也许会把有些权的层数计算错了，导致总权值计算错误，大家一定要细心。注意：这4