欢迎来到天天文库
浏览记录
ID:53911136
大小:278.62 KB
页数:4页
时间:2020-04-27
《图论及其应用 第二章答案.pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、欧拉图与哈密尔顿图(除第3题属中国邮路问题)<1.>给定一个由16条线段构成的图形(见下图).证明:不能引一条折线与每一线段恰好相交一次(折线可以是不封闭的和自由相交的,但他的顶点不在给定的线段上)证明:建立一个图G:顶点v代表图形的区域Xi(1,2,3,4,5,6),顶点v与v之间连接iiij的边数等于区域X与X公共线段的数目.ij于是,将上图的区域和边可转化成下图:由顶点度数知不存在欧拉路,从X到X只能相交于外面的两条线段.16<2.>下列图形中哪些能一笔画成.解:只需考虑该图是否有欧拉路(即有两个奇点或者无奇点),故第一个和第三个可以一笔画成,第二个不能一笔画成.<4.>下图是某
2、个展览馆的平面图,其中每个相邻的展览室有门相通.证明:不存在一条从A进入,经过每个展览室恰好一次再从A处出来的参观路线.证:用顶点代表展览室,两顶点相邻当且仅当这两点所对应的展览室有门相通,则可得一个连通简单图G(见下图).因此,只要证明G中不存在H—回路即可.具体理由如下:令Syy,,,y,则显然S是G的真子集,而(GS)18S161216(x共18个,y共16个),故由讲义中定理2.3知不存在H—回路.<5.>某次会议有20人参加,其中每个人都至少有10个朋友.这20人围一桌入座,要想使与每个人相邻的两位都是朋友是否可能?解:用顶点代表人,两人是朋友时相应顶点间连一
3、边,得到一个无向图G(,)VE.只要证明G中存在H—回路即可.G是10阶连通图,对于n20,且duGG()10,dv()10,可得:du()dv()20n,故由讲义中定理2.4知G中存在H—回路.GG<6.>已知abcdefg,,,,,,七个人中,a会讲英语,b会讲英语和汉语,c会讲英语、意大利语和俄语,d会讲汉语和日语,e会讲意大利语和德语,f会讲俄语、日语和法语,g会讲德语和法语.能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人交谈.解:用七个顶点表示这七个人.若两人能交谈(会讲同一种语言),就在这两顶点之间连一条边,得到图G.只要证明图G中存在H回路即可.英
4、语英语汉语日语法语德语意大利语具体结果如下:cabdfgec.<7.>设G是分划为XY,的二部图,且XY,则G一定不是H—图。证明:设XmY,n,反证法:假设G为H—图,则存在回路C经过XY,中点一次且仅一次,令SY,设mn,则()GYmY。2<8.>设简单图G(,),VEVnE,n,若有mC2,则G是H—图。n1证明:反证法,若G不是H—图,则uvG,不相邻,且du()dv()n1GGn21令GGuv,,则()G(n2)(n3),1122E(G)du()dv()1GG1(n2)(n3)n121矛盾
5、。2(nn32)1212(n1)(n2)1C2n12<3.>如下图.图中各边数字所标注的数字,表示改变的长度(权).邮递员从邮局A出发.求他的最优投递路线.解:下图中的任一个欧拉环游就是邮递员的最优邮递路线.补:(1.)连通图G是欧拉图的充分必要条件是G中无奇点.连通图G具有欧拉路充分必要条件是G恰好有两个奇点.(2.)H—图的必要条件:若G是H—图,则对VG()的每一个非空真子集S,均有()GSS.其中,()G表示G的连通分支个数.H—图的充分条件:a.设nn(3)阶连通图G中任意两个不相邻的顶点u与v,均有du()dv()n,则GGG是H—图.nb
6、.若G是具有nn(3)个顶点的简单图,每个顶点的度至少是,则G是H—图.2
此文档下载收益归作者所有