?)??(C) 故 ?(C?)??(C0又G?的最佳H圈C?展开又是G中的一个权相同的推销员回路，所以 ?(C)??(C?) 综上，?(C)??(C?)，证毕。 定理 6·16 对Christofides法，有??32。
证 设C*是算法得到的H圈，C是算法中C*的欧拉巡回，T和M分别是G的最小生成树和树中奇次顶点导出子图的最小权匹配，则：
W(C*)?W(C)?W(T)?W(M） 设H是最佳H图，则W（T）?W（H）下证W（M）?12W（H)
设在H：u1u2?unu1上去掉T中的偶次顶点得一个只含T的奇次顶点的圈C?，显然 W(C?)?W(H)且W(C?)?2W(M) W(M)?*12W(C?)?W(H) 12W(H)?32W(H)
W(C)?W(H)?故??32。证毕。
定理 6·17 设D?是图G的距离矩阵D的简化矩阵，则H圈也是原图G的最佳（有向）D?对应图G?的最佳（有向）
H图。G?只是边权与G不同，去掉权之后完全一样。
因此当简化矩阵中的零元素构成H圈时，即是原问题的最佳H圈。
定义6·8 一个H圈的一些不相交路径称为可行路分路。
第七章 平面图
定义7·1 一个图若能再曲面S上画出，使任两边在非顶点处不相交，则称此图可以再
曲面S上嵌入。可嵌入平面的图称为可嵌平面图，否则称为非平面图。可嵌平面图G嵌入平面形成的图，称为G的平面嵌入。
定理7·1 任何图皆可嵌入E3。
证 取E3中曲线l:x?t,y?t2,z?t3,t?0,从l上任取四个点(ti,ti2,ti3),i?1,2,3,4,
ti?0,则由于范德蒙行列式
11t2t2231t3t3231t4t423
t1t123??(t1?j?i?4i?tj)?0
t1t2t3t4知这四点不共面，我们把G的顶点画在l上，把边画成直线段，这时不会有任何两条边在非顶点相交不然相交的两条线段共面。于是其四个端点共面，在l上四点不共面矛盾。因此可如此把任何画G画在E3中而边不再非顶点处相交。证毕。
定理7·2 G是可嵌平面图的充要条件是G可在球面上嵌入。
证 考虑球极投影（如图（7—3）），球面S与平面P相切，过切点的直径的另一端点为N（北极），定义映射?：S?P当且仅当N，s,p共线时，?（s)?p，其中
。 s?S,p?P,?是一一映射（P上的?与N对应）
若图G有平面嵌入G?，则由?，G?在S上的嵌入，不妨设N不再G??的边上或顶点上，则由?，G??之象即为G的平面嵌入。证毕。
定义 7·2 可嵌平面图G的平面嵌入把平面分成若干个连通的闭区域，每个这种闭区域叫做G的一个面。用F（G）与?（G）分别表示G的面集与面的数目，并用b(f)表示面f的周界。
定理 7·3 设G是连通的平面图，则
u?????2 证 对?进行归纳法证明
?=1时，G中无圈，又G是连通图，因此G是树，??u?1,于是u???1?2，公
式成立。
假设??n时，公式成立
当??n?1?2时，G有圈，记e是某圈上的边，则G?e仍连通，而被e分隔的G中的两个面在G?e中成为一个面，且G?e仍为平面图，由归纳假设
u(G?e)??(G?e)??(G?e)?2 u(G)???(G)?1????(G)?1??2 u(G)??(G)??(G)?2 证毕。
推论 7·3 一个连通可嵌平面图的所有平面嵌入，其面的数目均相等。
定义7·2 设G?是平面图G的平面嵌入，则如下画出的图G*是G的一个对偶图： （1）G?的每个面f内画且仅画G*的一个顶点f*；
（2）当且仅当面fi与面fj有公共边ek时，画G*的一条边ek?fifj； （3）e为G?的割边时，画G*的一环，此环与e所在的面内的顶点f*相关联。 定义 7·3 设G是平面图，面f的周界边上的数目（割边要算两次），称为面f的次数，记为dG(f)。
定理 7·4 设G为平面图，则有： 证 证毕。
推论7·4·1 设G是u?3的简单平面图，则 ??3u?6
证据 只需对简单连通平面图来证明，因u?3，且G是简单图，因而d(f)?3，其中 f?F(G)
2??由欧拉公式
u?????2 ? 3u?3??3??6
3u?6?3??3??3??2??? ??3u?6 证毕。
推论7·4·2 若G是简单平面图，则?（G）?5
***?d(f)?2?(G)
f?F(G)?d(f)??d(ff?F(G)f?V(G)***)?2?(G)?2?(G)
*?d(f)?3?.
f?F(G)证 u?1或2时，命题显然 当u?3时，由推论7·4·1有 ?u??d(u)?2?u?V(G)?2(3u?6)
? ??6?故u?3，证毕。
12u
定义 7·5 K5和K3,3都是非平面图
证 u(K5)?5 ?(K5)?10 3u?6?9?? 因此K5不满足平面图的必要条件，故K5是非平面图。
K3,3是二部图，无奇圈，不含长度为3的圈，若K3,3是平面图，则?f?F(K3,3) d(f)?4 4???d(f)?2?f?F(G)?2?9?18
? ??4.5 即??4
由欧拉公式 2?u?????6?9?4?1，这不可能，故K3,3是非平面图，证毕。
定义 7·4 将图G的某些边换成路径得到图G?，称G?为G的细分。
定理 7·5 证明了K5和K3,3均是非平面图，很显然，它们的细分也是非平面图，因而任何含有K5或K3,3的细分的图也都不是平面图，即任何可嵌平面图都不含K5和K3,3的细分。库拉托斯基证明了可嵌平面图的这个必要条件也是充分的。
定理 7·6 G是可嵌平面图的充要条件是它不含K5或K3,3的任何细分。
定理 7·7 （瓦格纳Wagner,1937），G是平面图的充要条件是G中无可收缩到K5或K3,3的子图。
定义 7·5 设H是G的子图，称满足下列条件的G?E(H)的连通子图B为G加在H上的桥，
（1）B中任意两边之间都存在路径，其中间点均不属于H；
（2）B是满足条件（1）的G?E(H)的极大连通子图，即任何以B为真子图的。 G?E(H)的连通子图，都不满足（1）
定义 7·6 设G是可嵌平面图，H是在平面上嵌入的G的子图，若能在H的基础上
~~把G全部在平面上嵌入，则称H是G?可接受的一个平面嵌入。
定义 7·7 设H是G的一个可嵌平面子图，H是H在平面上的嵌入，B是G中H上的一个桥，f是H的一个面。如果B的附着点全部在f的边界上，则称B在H的面f上是可展的，并把H中B是可展的那些面的集合记为F(B,H)。
定理7·8 若G是一个可嵌平面图，H是G的一个可嵌平面子图，且H是G?可接受的平面嵌入，则对H上每一个桥B，恒有
F(B,H)??
~~~证 设H是G?可接受的，则G可在H的基础上继续嵌入而成为平面图G，使得~~~~~ H?G。因此G中H上的每一个桥必定限制在H的一个面上，故F(B,H)??。证毕。
~~~~~~~定理 7·9 设G是可嵌平面图，则由可平面化算法产生的序列G1,G2,?均是G?可接受的平面嵌入。
d~~定义 7·8 若G??Gi?1i，其中Gi皆平面图，i?1,2?,d,E(Gi)?E(Gj)??,i?j；
（G1,G2,?Gd)是G的平面分解，而 则称
是G的平面分解? ?(G)?min?d(G1,G2,?,Gd）称为G的厚度或层数。
定理 7·9 （1）非平面图G的厚度
?(G)??（2） 若G不含三角形，则 Q(G)??证 （1）对于平面图有
0???3u?6,从而(u?2) 0???? (u?2)
?2u?4???? (u?2)
?3u?6????3u?6??1
故有 ?(G)????
?3u?6??