习题参考解答(图论部分)(共27页).doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《习题参考解答(图论部分)(共27页).doc》由会员分享,可在线阅读,更多相关《习题参考解答(图论部分)(共27页).doc(27页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上习题十1. 设G是一个(n,m)简单图。证明:,等号成立当且仅当G是完全图。证明:(1)先证结论: 因为G是简单图,所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理,G图边的上限为 max(m) n(n-1)/2,所以。(2) =G是完全图因为G具有上限边数,假设有结点的点度小于n-1,那么G的总度数就小于上限值,边数就小于上限值,与条件矛盾。所以,G的每个结点的点度都为n-1,G为完全图。G是完全图 =因为G是完全图,所以每个结点的点度为n-1, 总度数为n(n-1),根据握手定理
2、,图G的边数 。2. 设G是一个(n,n+1)的无向图,证明G中存在顶点u,d(u)3。证明:反证法,假设,则G的总点度上限为max(d(u) 2 n,根据握手定理,图边的上限为max(m) 2n/2=n。与题设m = n+1,矛盾。因此,G中存在顶点u,d(u)3。3确定下面的序列中哪些是图的序列,若是图的序列,画出一个对应的图来: (1)(3,2,0,1,5); (2)(6,3,3,2,2) (3)(4,4,2,2,4); (4)(7,6,8,3,9,5)解:除序列(1)不是图序列外,其余的都是图序列。因为在(1)中,总和为奇数,不满足图总度数为偶数的握手定理。可以按如下方法构造满足要求的
3、图:序列中每个数字ai对应一个点,如果序列数字是偶数,那么就在对应的点上画ai/2个环,如果序列是奇数,那么在对应的点上画(ai-1)/2个环。最后,将奇数序列对应的点两两一组,添加连线即可。下面以(2)为例说明: (6 , 3, 3, 2, 2 ) 对应图G的点集合V= v1,v2,v3,v4,v5v1v5v33v4v2每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)v1v5v33v4v2将奇数3,3 对应的结点v2,v3一组,画一条连线v1v5v33v4v2其他序列可以类式作图,当然大家也可以画图其它不同的图形。4证明:在(n,
4、m)图中。证明:图的点度数是一组非负整数d(v1),d(v2)d(vn),那么这组数的算术平均值一定大于等于其中的最小值,同时小于等于其中的最大值。对应到图的术语及为:最大值为,最小值为,平均值 = (d(v1)+d(v2)+d(vn)/n = 2m/n,所以。5证明定理10.2。【定理10.2】对于任何(n,m)有向图G =(V,E),证明:有向图中,每条有向边为图贡献一度出度,同时贡献一度出度,所以总出度和总入度相等,并和边数相等。因此,上述关系等式成立。6设G是(n,m)简单二部图,证明:。证明:本题目,我们是需要说明n阶的简单二部图的边数的最大值 = 即可。设n阶的简单二部图,其两部分
5、结点集合分别为V1,V2,那么|V1| + |V2| = n。此种情况下,当G为完全二部图时,有最多的边数,即max(m) = |V1|V2|,变形为,max(m) =( n-|V2|)|V2|.此函数的最大值及为n阶二部图的边的上限值,其上限值为当|V2|=n/2 时取得。及max(max(m) = ,所以n阶二部图(n,m), 7. 无向图G有21条边,12个3度数结点,其余结点的度数均为2,求G的阶数n。解:根据握手定理有: 21 =( 312 + 2(n-12)/2, 解此方程得n = 158证明:完全图的点诱导子图也是完全图。证明:方法1为证明此结论,我们先证两个引论:引论1:设G(
6、V,E)为母图,,则G的任意子图G(V,E)是G关于V的点诱导子图G(V,E)的子图。引论2:引论1中G(V,E)的任意点诱导子图,也是G图的点诱导子图。证明:略,请读者证明。设有完全图Kn( n1),现根据其p阶点诱导子图作归纳证明。Kn的1阶点诱导子图,显然是完全图,且都是K1图。当n2,Kn的2阶点诱导子图,显然是完全图,且都是K2图假设Kn的p(np2)阶点诱导子图,为Kp图,那么对任意的p+1阶点诱导子图G,根据引理2结论,G的任意p阶点诱导子图G为Kn的p阶点诱导子图,且为Kp图。因此,G必为Kp+1图。根据以上论证可得原命题成立方法2因为完全图的任意两个顶点均邻接,所以点导出子图
7、任意两个顶点也邻接,为完全图。9若,称G是自补图。确定一个图为自补图的最低条件;画出一个自补图来。解:设G为(n,m)图,为(n,m)图, 根据补图的定义有,至少应该满足m+m=n(n-1)/2 (1) 根据同构的定义有,至少应该满足m=m(2)(1),(2)联立求解得:m=n(n-1)/4, 及一个图为自补图,最低条件为结点数为4的倍数或为4的倍数加1。图示略10判断图10.29中的两个图是否同构,并说明理由。图10.29解:题中两个图不同构,因为左边图的唯一3度点有2个1度点为其邻接点,而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构11证明: 图10.30中的两个图是同
8、构的。图10.30解:略12. 求具有4个结点完全图K4的所有非同构的生成子图。解:我们可以把生成子图按总度数不同进行分类,不同总度数的子图类决不同构。总度数相同的子图类中,再去找出不同购的子图。因此求解如下:d(v) = 0: (0,0,0,0) =2: (1,1,0,0) =4: (2,1,1,0) (1,1,1,1) =6: (3,1,1,1) (2,2,1,1)(2,2,2,0) =8: (2,2,2,2) (3,2,2,1) =10: (3,3,2,2) =12: (3,3,3,3)总共10个不同构生成子图13. 设有向图D=如下图10.31所示。(1) 在图中找出所有长度分别为1,
9、2,3,4的圈 (至少用一种表示法写出它们,并以子图形式画出它们)。(2) 在图中找出所有长度分别为3,4,5,6的回路,并以子图形式画出它们。解:(1) C=AA C=ADA C=Ae4Be7Ce5A C=Ae4Be8Ce5A C=Ae4Be7Ce6De2A C=Ae4Be8Ce6De2A(2)子图略长度为三的回路:Ae1Ae1Ae1A,Ae1Ae3De2A,Ae4Be7Ce5A,Ae4Be8Ce5A长度为四的回路:AAAAA,AAADA,AABe7CA,AABe8CA,ABe7CDA,ABe8CDA长度为五的回路:AAAAAA,AAAADA,AAABe7CA,AAABe8CA,AABe7C
10、DA,AABe8CDA, AADADA,AAAe4Be7Ce5A,AAAe4Be8Ce5A, ADAe4Be7Ce5A,ADAe4Be8Ce5A14. 试证明在任意6个人的组里,存在3个人相互认识,或者存在3个人相互不认识。证明:设A为6人中的任一人,那么A要么至少与3人认识,要么至少与3人不认识,二者必居其一。假设A与B,C,D三人认识,如果B,C,D三人互不认识,结论成立如果B,C,D三人中,至少有两人相互认识,则它们和A一起,构成相互认识的3人,结论成立。同理,A至少与3人不认识,结论也成立。因此,题设结论成立15. 若u和v是图G中仅有的两个奇数度结点,证明u和v必是连通的。证明:反证
11、法,假设u和v不连通,那么他们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度结点。根据握手定理,一个图中奇度点的个数为偶数。而两个连通分支中,奇度点的个数为奇数。矛盾。矛盾的产生,是由于假设不连通导致的,因此,题设结论成立16. 证明:G是二部图当且仅当G的回路都是偶长回路。证明:设二部图G,顶点分为两个集合V1 ,V2 充分性:先证明在二部图中,奇长路的道路的两个端节点一定分别在两个顶点集合中,对道路长度使用归纳法,(1) 当道路长度为1是,根据二部图的定义,每条边的两个顶点分别在两个点集合中,结论成立(2) 假设道路长度为2n-1 ( n2)时结论成立(3) 当道
12、路长度为2n+1时,设P=v1v2v2n-1v2nv2n+1,在此路径上删除最后两个结点,那么道路P将变为长度为2n-1的奇长道路,根据假设,v1,v2n-1分别在两个顶点集合中,那么v2n和v1在同一顶点集合中,而v2n+1和v1在不同顶点集合,结论成立因为G中的任何回路,写成道路的形式,起点和终点时一个结点,当然在同一个顶点集合中,因此长度必为偶数;必要性:(仅对连通分支证明)在图中任意取一点着色为白色,将和此点最短距离为奇数的点着色为黑点,为偶数的着色为白点,那么将结点分为白色和黑色连个点集,任何同色点之间没有边相连。否则将形成奇数长度的回路,例如同色结点v1,v2 相邻,那么从初始着色
13、点v开始通过最短路径可以形成如下回路vv1v2v,因为vv1,v2v长度和为偶数,那么回路vv1v2v长度为奇数,与题设矛盾。所以是二部图17.设(n, m)简单图G满足,证明G必是连通图。构造一个的非连通简单图。证明:假设G不连通,分支G1,G2,那么他们的边数的最大值()()()()()()()(),所以,只有当k=1时,才能满足题设要求,G是连通图。如果将顶点集合分成两个点集,|V1|=1,|V2|=n-1,构成如下的有两个分支的非连通简单图,G1=(1,0),G2=Kn-1,满足题设条件18. 设G是阶数不小于3的连通图。证明下面四条命题相互等价:(1)G无割边;(2) G中任何两个结
14、点位于同一回路中;(3) G中任何一结点和任何一边都位于同一回路中;(4) G中任何两边都在同一回路中。证明:(1)=(2)因为G连通,且G无割边,所以任意两个结点u,v,都存在简单道路p=uwv.又因为G无割边,所以,删除边wv后,子图依然连通,即w,v存在简单道路p,以此类推,可以找到一条核p每条边都不相同的p=vu,这样p和p就构成了一条回路。(2)=(3)因为G中任意两个结点都位于同一回路中,所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1,C2中,如果C1=C2=uv1v2u,那么将回路中v1v2,用v1v2=e替换,就得到新的新的回路,并满足要求。如果C1C2,C
15、1=uv1u,C2=uv2u,那么构成新的道路P=uv1uv2u,在其中将重复边剔出掉,得到新的回路C3,其中包含v1,v2结点,可以将回路中v1v2用v1v2=e替换,就得到新的新的回路,并满足要求.(3)=(4)对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据(3)存在回路C1 = u1v1v2u1,C2=u2v1v2u2。那么可以形成新的闭道路P=u1v1v2u2v1v2u1,在其中将重复边剔出到,得到新的回路C3,其中包含e2和u1,u2结点,可以将回路中u1u2用u1u2=e1替换,就得到新的新的回路,包含e1,e2,满足要求.(4)=(1)因为任意两条边都在同一回路中
16、,所以不存在割边。假设边e是割边,那么删除此边,图不连通,分支中的任何一对不在同一分支中的边,不能构成回路,与条件矛盾。所以,G中无割边19. 设G=(V,E)是点度均为偶数的连通图。证明:对任何。证明:G-v最多产生d(v)个奇数度点,又因为每个连通分支中奇数度点的个数是偶数,即G-v的连通分支最少有两条边和v相连,所以总连通分支数小于等于d(v)/2hong(1).2.20. 证明:图中距离满足欧几里德距离的三条公理。证明:(1)d(u,v)0,即任何两个结点之间的最短路长度大于等于0显然,结点与自己之间的距离为,而和其他结点之间的最短距离不为。()(,)(,),两个结点之间的最短距离相等
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 习题 参考 解答 部分 27
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内