图论及其应用 第二章答案

)3( 题属中国邮路问题除第欧拉图与哈密尔顿图 给定一个由16条线段构成的图形（见下图）.证明：不能引一条折线与每一线段恰好相 交一次（折线可以是不封闭的和自由相交的，但他的顶点不在给定的线段上） 证明：建立一个图G：顶点 i v代表图形的区域(1,2,3,4,5,6) i X i ，顶点 i v与 j v之间连接 的边数等于区域 i X与 j X公共线段的数目. 于是，将上图的区域和边可转化成下图： 由顶点度数知不存在欧拉路，从 1 X到 6 X只能相交于外面的两条线段. 下列图形中哪些能一笔画成. 解：只需考虑该图是否有欧拉路（即有两个奇点或者无奇点） ，故第一个和第三个可以一笔 画成，第二个不能一笔画成. 下图是某个展览馆的平面图，其中每个相邻的展览室有门相通. 证明：不存在一条从A进入，经过每个展览室恰好一次再从A处出来的参观路线. 证：用顶点代表展览室，两顶点相邻当且仅当这两点所对应的展览室有门相通，则可得一个 连通简单图G（见下图）.因此，只要证明G中不存在H回路即可. 具体理由如下： 令 1216 ,Sy yy， 则显然S是G的真子集， 而()1816GSS （x共18个，y共16个） ，故由讲义中定理2.3知不存在H回路. 某次会议有20人参加，其中每个人都至少有10个朋友.这20人围一桌入座，要想使与 每个人相邻的两位都是朋友是否可能？ 解:用顶点代表人，两人是朋友时相应顶点间连一边，得到一个无向图( ,)GV E.只要证明 G中存在H回路即可. G是10阶连通图，对于20n，且( )10,( )10 GG dudv，可 得：( )( )20 GG dudvn，故由讲义中定理2.4知G中存在H回路. 已知, , , , , ,a b c d e f g七个人中，a会讲英语，b会讲英语和汉语，c会讲英语、意大利 语和俄语，d会讲汉语和日语，e会讲意大利语和德语，f会讲俄语、日语和法语，g会 讲德语和法语.能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈. 解：用七个顶点表示这七个人.若两人能交谈（会讲同一种语言） ，就在这两顶点之间连一条 边，得到图G.只要证明图G中存在H 回路即可. 具体结果如下：cegfdbac 意大利语德语法语日语汉语英语英语 . 设G是分划为,X Y的二部图，且XY，则G一定不是H图。 证明：设,Xm Yn，反证法：假设G为H图，则存在回路C经过,X Y中点一次 且仅一次，令SY，设mn，则()G YmY。 设简单图( , ),GV E Vn En，若有 2 1 2 n mC ，则G是H图。 证明：反证法，若G不是H图，则, u vG不相邻，且( )( )1 GG dudvn 令 1 ,GGu v，则 1 2 1 ()(2)(3) 22 n Gnn ， 1 2 2 1 ()( )( ) 1 (2)(3)1 2 1 (32) 1 2 1 (1)(2) 12 2 GG n EGdudv nnn nn nnC 矛盾。 如下图.图中各边数字所标注的数字，表示改变的长度（权）.邮递员从邮局A出发.求他 的最优投递路线. 解：下图中的任一个欧拉环游就是邮递员的最优邮递路线. 补：补： (1.)连通图G是欧拉图的充分必要条件是G中无奇点. 连通图G具有欧拉路充分必要条件是G恰好有两个奇点. (2.) H图的必要条件：图的必要条件： 若G是H图，则对( )V G的每一个非空真子集S，均有()GSS.其中，( )G表 示G的连通分支个数. H图的充分条件：图的充分条件： a.设(3)n n阶连通图G中任意两个