图论及其应用 第二章答案

南开大学数学科学学院 图论及其应用

欧拉图与哈密尔顿图 (除第3题属中国邮路问题)

<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 2

E (G1) dG(u) dG(v)

1 (n 2)(n 3) n 12

矛盾。 12 (n 3n 2) 12

12 (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