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

.PAGE.离散数学图论部分期末复习辅导一、单项选择题1．设图G＝<V,E>,vV,则下列结论成立的是<>．A．deg<v>=2EB．deg<v>=EC．D．解根据握手定理〔图中所有结点的度数之和等于边数的两倍知,答案C成立。答C2．设无向图G的邻接矩阵为,则G的边数为<>．A．6B．5C．4D．3解由邻接矩阵的定义知,无向图的邻接矩阵是对称的．即当结点vi与vj相邻时,结点vj与vi也相邻,所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1,题中给出的邻接矩阵中共有10个1,故有102=5条边。答B3．已知无向图G的邻接矩阵为,则G有〔．A．5点,8边B．6点,7边C．6点,8边D．5点,7边解由邻接矩阵的定义知,矩阵是5阶方阵,所以图G有5个结点,矩阵元素有14个1,14÷2=7,图G有7条边。答Dabcd图一eA．{<a,e>}是割边B．{<a,e>}是边割集C．{<a,e>,<b,c>}是边割集D．{<d,e>}是边割集定义设无向图G=<V,E>为连通图,若有边集E1E,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图仍是连通图,则称E1是G的一个边割集．若边割集为单元集{e},则称边e为割边〔或桥．解割边首先是一条边,因为答案A中的是边集,不可能是割边,因此答案A是错误的．删除答案B或C中的边后,得到的图是还是连通图,因此答案B、C也是错误的．在图一中,删去<d,e>边,图就不连通了,所以答案D正确．答D注：如果该题只给出图的结点和边,没有图示,大家也应该会做．如：若图G=<V,E>,其中V={a,b,c,d,e},E={<a,b>,<a,c>,<a,e>,<b,c>,<b,e>,<c,e>,<e,d>},则该图中的割边是什么？5．图G如图二所示,以下说法正确的是<>．aabcd图二B．{b,c}是点割集C．{b,d}是点割集D．{c}是点割集定义设无向图G=<V,E>为连通图,若有点集V1V,使图G删除了V1的所有结点后,所得的子图是不连通图,而删除了V1的任何真子集后,所得的子图仍是连通图,则称V1是G的一个点割集．若点割集为单元集{v},则称结点v为割点．解在图二中,删去结点a或删去结点c或删去结点b和d图还是连通的,所以答案A、C、D是错误的．在图二中删除结点b和c,得到的子图是不连通图,而只删除结点b或结点c,得到的子图仍然是连通的,由定义可以知道,{b,c}是点割集．所以答案B是正确的．答Baabcd图三A．{<a,d>}是割边B．{<a,d>}是边割集C．{<a,d>,<b,d>}是边割集D．{<b,d>}是边割集解割边首先是一条边,{<a,d>}是边集,不可能是割边．在图三中,删除答案B或D中的边后,得到的图是还是连通图．因此答案A、B、D是错误的．在图三中,删去<a,d>边和<b,d>边,图就不连通了,而只是删除<a,d>边或<b,d>边,图还是连通的,所以答案C正确．7．设有向图〔a、〔b、〔c与〔d如图四所示,则下列结论成立的是<>．图四A．〔a是强连通的B．〔b是强连通的C．〔c是强连通的D．〔d是强连通的复习：定义在简单有向图中,若在任何结点偶对中,至少从一个结点到另一个结点可达的,则称图G是单向〔侧连通的；若在任何结点偶对中,两结点对互相可达,则称图G是强连通的；若图G的底图,即在图G中略去边的方向,得到的无向图是连通的,则称图G是弱连通的．显然,强连通的一定是单向连通和弱连通的,单向连通的一定是弱连通,但其逆均不真．定理一个有向图是强连通的,当且仅当G中有一个回路,其至少包含每个结点一次．单侧连通图判别法：若有向图G中存在一条经过每个结点至少一次的路,则G是单侧连通的。答A〔有一条经过每个结点的回路问：上面的图中,哪个仅为弱连通的？答：图<d>是仅为弱连通的请大家要复习"弱连通"的概念．8．设完全图K有n个结点<n2>,m条边,当〔时,K中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数解完全图K每个结点都是n1度的,由定理的推论知K中存在欧拉回路的条件是n1是偶数,从而n为奇数。答C提示：前面提到n阶无向完全图Kn的每个结点的度数是n-1,现在要问：无向完全图Kn的边数是多少？答：n<n–1>/29．若G是一个汉密尔顿图,则G一定是<>．A．平面图B．对偶图C．欧拉图D．连通图定义给定图G,若存在一条路经过图G的每个结点一次且仅一次,则该路称为汉密尔顿路；若存在一条回路经过图G的每个结点一次且仅一次,则该回路称为汉密尔顿回路；具有汉密尔顿回路的图称为汉密尔顿图．由定义可知,汉密尔顿图是连通图．答D10．若G是一个欧拉图,则G一定是<>．A．平面图B．汉密尔顿图C．连通图D．对偶图定义4.1.1给定无孤立结点图G,若存在一条路经过图G的每条边一次且仅一次,则该路称为欧拉路．〔即,欧拉路中没有重复的边,并且包含了图中的每条边．若存在一条回路经过图G的每条边一次且仅一次,则该回路称为欧拉回路．具有欧拉回路的图就称为欧拉图．由定义可知,欧拉图是连通图．答C11．设G是连通平面图,有v个结点,e条边,r个面,则r=<>．A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋2答A〔定理：欧拉公式ver2问：如果连通平面图G有4个结点,7条边,那么图G有几个面？12．无向树T有8个结点,则T的边数为<>．A．6B．7C．8D．9答13．无向简单图G是棵树,当且仅当<>．A．G连通且边数比结点数少1B．G连通且结点数比边数少1C．G的边数比结点数少1D．G中没有回路．答A〔定理5.1.1〔树的等价定义14．已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个,T的树叶数为<>．A．8B．5C解这棵无向树T有7条边,所有结点的度数之和为14,而4度、3度、2度的分支点各一个共3个结点占用了9度,所以剩下的5个结点占用5度,即这5个结点每个都是1度结点,故有5片树叶．答B15．设G是有n个结点,m条边的连通图,必须删去G的<>条边,才能确定G的一棵生成树．A．B．C．D．答A〔n个结点的连通图的生成树有条边,必须删去条边16．设无向图G的邻接矩阵为,则G的边数为<>．A．1B．6C．7D．14答C17．如图二〔下图所示,以下说法正确的是<>．A．e是割点B．{a,e}是点割集C．{b,e}是点割集D．{d}是点割集图二答A18．设有向图〔a、〔b、〔c与〔d如图六〔下图所示,则下列结论成立的是<>．图六A．〔a只是弱连通的B．〔b只是弱连通的C．〔c只是弱连通的D．〔d只是弱连通的答D19．无向完全图K4是〔．A．欧拉图B．汉密尔顿图C．非平面图D．树答B20．以下结论正确的是<>．A．无向完全图都是欧拉图B．有n个结点n－1条边的无向图都是树C．无向完全图都是平面图D．树的每条边都是割边答D二、填空题1．已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是．解设G有x条边,则由握手定理,,答152．设给定图G<如右由图所示>,则图G的点割集是．解从图G中删除结点f,得到的子图是不连通图,即结点集{f}是点割集；从图G中删除结点c和e,得到的子图是不连通图,而只删除c或e,得到的子图仍然是连通的,所以结点集{c,e}也是点割集．而其他结点集都不满足点割集的定义的集合,所以应该填写：{f}、{c,e}答{f}、{c,e}提示：若f是图G的割点,则{f}是图G的点割集,删除f点后图G是连通吗？3．设G是一个图,结点集合为V,边集合为E,则G的结点等于边数的两倍．答的度数之和4．无向图G存在欧拉回路,当且仅当G连通且．答G的结点度数都是偶数〔定理4.1.15．设G=<V,E>是具有n个结点的简单图,若在G中每一对结点度数之和大于等于,则在G中存在一条汉密尔顿路．答n1〔定理6．若图G=<V,E>中具有一条汉密尔顿回路,则对于结点集V的每个非空子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数|S|与W满足的关系式为．答W|S|〔定理4.2.17．设完全图K有n个结点<n2>,m条边,当时,K中存在欧拉回路．答n为奇数〔同一、8题8．结点数v与边数e满足关系的无向连通图就是树．答ev1〔定理〔树的等价定义9．设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去条边后使之变成树．解由握手定理〔定理3.1.1知道图G有182=9条边,又由定理5.1.1中给出的图T为树的等价定义之一是"图T连通且e=v-1”答410．设正则5叉树的树叶数为17,则分支数为i=．答4〔定理：<m-1>i=t-1三、判断说明题〔判断下列各题,并说明理由．1．如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路．解错误．只有当G是连通图且其结点度数均为偶数时,图G才存在一条欧拉回路．2．如下图所示的图G存在一条欧拉回路．解错误．因为图G有两个奇数度〔3度结点,所以不存在欧拉回路．注：这是一个汉密尔顿图,但不是欧拉图。可见汉密尔顿图不一定是欧拉图．其实,欧拉图也不一定是汉密尔顿图．如下图所示,图〔1是欧拉图又是汉密尔顿图,图〔2是欧拉图但不是汉密尔顿图,图〔3不是欧拉图但它是汉密尔顿图,图〔4不是欧拉图也不是汉密尔顿图。3．如下图所示的图G不是欧拉图而是汉密尔顿图．图G解正确．图G有4个3度结点a,b,d,f,所以图G不是欧拉图．图G有汉密尔顿回路abefgdca,所以图G是汉密尔顿图．4．设G是一个有7个结点16条边的连通简单图,则G为平面图．解错误．由定理知,若G有v个结点e条边,且v3,则e≤3v6．但本题中,16≤3×76不成立．5．设G是一个连通平面图,且有6个结点11条边,则G有7个面．解正确．由欧拉定理,连通平面图G的结点数为v,边数为e,面数为r,则ve+r=2．于是有r=2v+e=26+11=7．问："完全图K6是平面图"是否正确？答不正确．因为完全图K6有6个结点15条边,且1536-6=12,即e3v-6对K6不成立,所以K6不是平面图．四、计算题1．设G=<V,E>,V={v1,v2,v3,v4,v5},E={<v1,v3>,<v2,v3>,<v2,v4>,<v3,v4>,<v3,v5>,<v4,v5>},试<1>给出G的图形表示；<2>写出其邻接矩阵；<3>求出每个结点的度数；<4>画出其补图的图形．解〔1G的图形为：〔2图G的邻接矩阵为：〔3图G的每个结点的度数为：,,,,．〔4由关于补图的定义3.1.9可知,先在图G补充边画出完全图〔见下面左图,然后去掉原图的边,可得图G补图〔见下面右注意：补图中,如果没有标出结点v3,则是错的．2．图G=<V,E>,其中V={a,b,c,d,e},E={<a,b>,<a,c>,<a,e>,<b,d>,<b,e>,<c,e>,<c,d>,<d,e>},对应边的权值依次为2、1、2、3、6、1、4及5,试〔1画出G的图形；〔2写出G的邻接矩阵；〔3求出G权最小的生成树及其权值．解〔1G的图形如左下图：〔2G的邻接矩阵为：〔3图G有5个结点,其生成树有4条边,用Kruskal算法求其权最小的生成树T：第1步,取具最小权1的边<a,c>；第2步,取剩余边中具最小权1的边<c,e>；第3步,取剩余边中不与前2条边构成回路的具最小权2的边<a,b>；第4步,取剩余边中不与前3条边构成回路的具最小权3的边<b,d>．所求最小生成树T如下图,其权为．注意：在用避圈法求最小的生成树的关键是："取图中权数最小的边,且与前面取到的边不构成圈",很多学生只注意到取权数最小的边了,而忽略了"不构成圈"的要求。如果题目给出如解<1>中所示赋权图,要求用Kruskal算法〔避圈法求出该赋权图的最小生成树,大家应该会吧．3．已知带权图G如右图所示．<1>求图G的最小生成树；<2>计算该生成树的权值．解〔1图G有6个结点,其生成树有5条边,用Kruskal算法求其权最小的生成树T：第1步,取具最小权1的边；第2步,取剩余边中具最小权2的边；第3步,取剩余边中不与前2条边构成回路的具最小权3的边；第4步,取剩余边中不与前3条边构成回路的具最小权5的边；第5步,取剩余边中不与前4条边构成回路的具最小权7的边．所求最小生成树T如右图．〔2该最小生成树的权为．4．设有一组权为2,3,5,7,17,31,试画出相应的最优二叉树,计算该最优二叉树的权．解〔Huffman算法：首先组合2+3,求带权5,5,7,17,31的最优二叉树；再组合5+5,求带权7,10,17,31的最优二叉树；然后组合7+10,求带权17,17,31的最优二叉树；继续组合17+17,求带权31,34的最优二叉树；最后组合31+34,得65,这是树根所带的权。可从树根开始往下画,即得所求最优二叉树T如下图：所求最优二叉树T的权为：讲评：作业中最优二叉树往往都能画对了,但计算总权值时可能会把有些权的层数计算错了,导致总权值计算错误,大家一定要细心。注意：这4个计算题的解题方法大家一定要