图论及其应用 第二章答案

<1.>给定一个由16条线段构成的图形（见下图）.证明：不能引一条折线与每一线段恰好相交一次（折线可以是不封闭的和自由相交的，但他的顶点不在给定的线段上）

证明：建立一个图G：顶点vi代表图形的区域Xi(i1,2,3,4,5,6)，顶点vi与vj之间连接的边数等于区域Xi与Xj公共线段的数目. 于是，将上图的区域和边可转化成下图：

由顶点度数知不存在欧拉路，从X1到X6只能相交于外面的两条线段. <2.>下列图形中哪些能一笔画成.

解：只需考虑该图是否有欧拉路（即有两个奇点或者无奇点），故第一个和第三个可以一笔画成，第二个不能一笔画成.

<4.>下图是某个展览馆的平面图，其中每个相邻的展览室有门相通.

证明：不存在一条从A进入，经过每个展览室恰好一次再从A处出来的参观路线.

证：用顶点代表展览室，两顶点相邻当且仅当这两点所对应的展览室有门相通，则可得一个连通简单图G（见下图）.因此，只要证明G中不存在H—回路即可.

具体理由如下：令Sy1,y2,,y16，则显然S是G的真子集，而(GS)18S16（x共18个，y共16个），故由讲义中定理2.3知不存在H—回路.

<5.>某次会议有20人参加，其中每个人都至少有10个朋友.这20人围一桌入座，要想使与每个人相邻的两位都是朋友是否可能？

解:用顶点代表人，两人是朋友时相应顶点间连一边，得到一个无向图G(V,E).只要证明

G中存在H—回路即可. G是10阶连通图，对于n20，且dG(u)10,dG(v)10，可

得：dG(u)dG(v)20n，故由讲义中定理2.4知G中存在H—回路.

<6.>已知a,b,c,d,e,f,g七个人中，a会讲英语，b会讲英语和汉语，c会讲英语、意大利语和俄语，d会讲汉语和日语，e会讲意大利语和德语，f会讲俄语、日语和法语，g会讲德语和法语.能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈. 解：用七个顶点表示这七个人.若两人能交谈（会讲同一种语言），就在这两顶点之间连一条边，得到图G.只要证明图G中存在H回路即可. 具体结果如下：c英语a 英语汉语日语法语德语意大利语bdfgec.

<7.>设G是分划为X,Y的二部图，且XY，则G一定不是H—图。

证明：设Xm,Yn，反证法：假设G为H—图，则存在回路C经过X,Y中点一次且仅一次，令SY，设mn，则(GY)mY。

<8.>设简单图G(V,E),Vn,En，若有mCn12，则G是H—图。 证明：反证法，若G不是H—图，则u,vG不相邻，且dG(u)dG(v)n1 令G1Gu,v，则(G1)2n21(n2)(n3)， 22E(G1)dG(u)dG(v)1(n2)(n3)n12矛盾。 12(n3n2)1212(n1)(n2)1Cn122<3.>如下图.图中各边数字所标注的数字，表示改变的长度（权）.邮递员从邮局A出发.求他的最优投递路线.

解：下图中的任一个欧拉环游就是邮递员的最优邮递路线.

补：

(1.)连通图G是欧拉图的充分必要条件是G中无奇点.

连通图G具有欧拉路充分必要条件是G恰好有两个奇点.

(2.)

H—图的必要条件：

若G是H—图，则对V(G)的每一个非空真子集S，均有(GS)S.其中，(G)表示G的连通分支个数. H—图的充分条件：

a.设n(n3)阶连通图G中任意两个不相邻的顶点u与v，均有dG(u)dG(v)n，则G是H—图.

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

2