图论及其应用 第二章答案.pdf

《图论及其应用 第二章答案.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—回路即可.具体理由如下：令Syy,,,y，则显然S是G的真子集，而(GS)18S161216（x共18个，y共16个），故由讲义中定理2.3知不存在H—回路.<5.>某次会议有20人参加，其中每个人都至少有10个朋友.这20人围一桌入座，要想使与每个人相邻的两位都是朋友是否可能？解:用顶点代表人，两人是朋友时相应顶点间连一

3、边，得到一个无向图G(,)VE.只要证明G中存在H—回路即可.G是10阶连通图，对于n20，且duGG()10,dv()10，可得：du()dv()20n，故由讲义中定理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—图。证明：设XmY,n，反证法：假设G为H—图，则存在回路C经过XY,中点一次且仅一次，令SY，设mn，则()GYmY。2<8.>设简单图G(,),VEVnE,n，若有mC2，则G是H—图。n1证明：反证法，若G不是H—图，则uvG,不相邻，且du()dv()n1GGn21令GGuv,，则()G(n2)(n3)，1122E(G)du()dv()1GG1(n2)(n3)n121矛盾

5、。2(nn32)1212(n1)(n2)1C2n12<3.>如下图.图中各边数字所标注的数字，表示改变的长度（权）.邮递员从邮局A出发.求他的最优投递路线.解：下图中的任一个欧拉环游就是邮递员的最优邮递路线.补：(1.)连通图G是欧拉图的充分必要条件是G中无奇点.连通图G具有欧拉路充分必要条件是G恰好有两个奇点.(2.)H—图的必要条件：若G是H—图，则对VG()的每一个非空真子集S，均有()GSS.其中，()G表示G的连通分支个数.H—图的充分条件：a.设nn(3)阶连通图G中任意两个不相邻的顶点u与v，均有du()dv()n，则GGG是H—图.nb

6、.若G是具有nn(3)个顶点的简单图，每个顶点的度至少是，则G是H—图.2