143页：定理516前一句话“这是至今。。之一”删除，添加： 60年代，科恩(P.J.Cohen)证明了连续统假设在ZFC公理系统中是不可能判定真假的。这 里ZFC公理系统是由ZF(Zermelo-Fraenkel)公理系统加上选择公理构成。有关ZF公理系统 和选择公理可参见书后参考书[1]。 11.4欧拉图与哈密顿图 以下加在279页11.4.2节前面 从欧拉图G=(V,E)中寻找欧拉回路的算法主要有弗罗莱(Fleury)算法。算法如下： 弗罗莱算法 (I)任取vo∈V,令T=vo。 (2)设T=eyye2…e,y,按如下规则从E-{e,e2,…,e,}中选取边一条边e1, (a)e与y,相关联： (b)如果与y,相关联的边中，存在非G-{e1,e2,…,e,}的割边的边，则优先选它。 (3)将e1=(心，)和1添加到T末尾。 (4)重复(2)(3)直到不能再进行，算法停止，T即为欧拉回路。 【例11.*】找出图1的欧拉回路。 6 e2 e13 e4 e12 d 9 e10 6 es 图1 图2
143 页：定理 5.16 前一句话“这是至今。。。之一”删除，添加： 60 年代，科恩（P. J. Cohen）证明了连续统假设在 ZFC 公理系统中是不可能判定真假的。这 里 ZFC 公理系统是由 ZF（Zermelo-Fraenkel）公理系统加上选择公理构成。有关 ZF 公理系统 和选择公理可参见书后参考书[1]。 11.4 欧拉图与哈密顿图 以下加在 279 页 11.4.2 节前面 从欧拉图G = (V,E) 中寻找欧拉回路的算法主要有弗罗莱（Fleury）算法。算法如下： 弗罗莱算法 (1) 任取 0 v V ，令T = 0 v 。 (2) 设T = 0 1 1 2 i i v e v e e v ，按如下规则从 E e1 ,e2 ,,ei 中选取边一条边 i 1 e ， （a） i 1 e 与 i v 相关联； （b）如果与 i v 相关联的边中，存在非G e1 ,e2 ,,ei 的割边的边，则优先选它。 (3) 将 1 1 ( , ) i i i e v v 和 i 1 v 添加到T 末尾。 (4) 重复（2）（3）直到不能再进行，算法停止，T 即为欧拉回路。 【例 11.**】 找出图 1 的欧拉回路。 a b c e d g h f i a b c e d g h f i e1 e2 e3 e4 e6 e5 e7 e8 e9 e10 e11 e12 e13 e14 图 1 图 2
【解】根据弗罗莱算法，不妨先取初始顶点a,则T=a。接着操作如下： (1)选取e,=(a,b),此时T=ae,b。 (2)选取e2=(b,c),此时T=aebe,c。 (3)选取e=(c,f),此时T=aebe,cef。 (4)选取e4=(f,i),此时T=aebe2cee,i。 (5)选取e,=(i,h),此时T=ae,be2ce,fe,ie,h。 (6)选取es=(h,g）,此时T=ae,be2cee,ieshe8。 (7)选取e,=(g,d),此时T=aebe,cefe,ie,he ge,.d。 (8)选取eg=(d,e),此时T=aebe,ce fe ie,he ge,dese。 (9)注意此时边(b,e)是图G-{e,…,e}的割边，不能选取此边，可以选取e,=(e,f), 此时T=ae,be2cefe,ie,he ge,de ee,f。 (10)选取eo=(f,h),此时T=ae,be,ce,fe,ie,he ge,desee,feh。 (1l)选取eu=(h,e),此时T=ae,be2cee,ie,he.ge,deee,fechee。 (12)选取e2=(e,b),此时T=aebe2cefe,ie he ge,deee,fe che ee2b。 (13)选取es=(b,d),此时T=aebe,cefe,ie,he ge,.desees fehe eebed。 (14)选取e4=(d,a),此时T=aebe2cefe,ie,he ge,desee,fe cheeebe1sde4a。 最终得到的T即为欧拉回路，可参看图2。 习题11.4补如下习题： 13.判定给定的图是否具有欧拉闭迹，当存在欧拉闭迹时构造出这样的闭迹。如果不存在欧 拉闭迹，判定是否具有欧拉迹。若存在欧拉迹则构造出这样的迹
【解】根据弗罗莱算法，不妨先取初始顶点 a，则T a 。接着操作如下： (1) 选取 1e (a,b) ，此时T 1 ae b 。 (2) 选取 2 e (b,c) ，此时T 1 2 ae be c 。 (3) 选取 3 e (c, f ) ，此时T 1 2 3 ae be ce f 。 (4) 选取 4 e ( f ,i) ，此时T 1 2 3 4 ae be ce fe i 。 (5) 选取 5 e (i,h) ，此时T 1 2 3 4 5 ae be ce fe ie h 。 (6) 选取 6 e (h, g) ，此时T 1 2 3 4 5 6 ae be ce fe ie he g 。 (7) 选取 7 e (g,d ) ，此时T 1 2 3 4 5 6 7 ae be ce fe ie he ge d 。 (8) 选取 8 e (d,e) ，此时T 1 2 3 4 5 6 7 8 ae be ce fe ie he ge de e 。 (9) 注意此时边(b, e) 是图 1 8 G {e ,,e }的割边，不能选取此边，可以选取 9 e (e, f ) ， 此时T 1 2 3 4 5 6 7 8 9 ae be ce fe ie he ge de ee f 。 (10) 选取 10 e ( f ,h) ，此时T 1 2 3 4 5 6 7 8 9 10 ae be ce fe ie he ge de ee fe h 。 (11) 选取 11 e (h,e) ，此时T 1 2 3 4 5 6 7 8 9 10 11 ae be ce fe ie he ge de ee fe he e 。 (12) 选取 12 e (e,b) ，此时T 1 2 3 4 5 6 7 8 9 10 11 12 ae be ce fe ie he ge de ee fe he ee b 。 (13) 选取 13 e (b,d ) ，此时T 1 2 3 4 5 6 7 8 9 10 11 12 13 ae be ce fe ie he ge de ee fe he ee be d 。 (14) 选取 14 e (d,a) ，此时T 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ae be ce fe ie he ge de ee fe he ee be de a 。 最终得到的 T 即为欧拉回路，可参看图 2。 习题 11.4 补如下习题： 13.判定给定的图是否具有欧拉闭迹，当存在欧拉闭迹时构造出这样的闭迹。如果不存在欧 拉闭迹，判定是否具有欧拉迹。若存在欧拉迹则构造出这样的迹
图11* 图11-* 11.4欧拉图和哈密顿图 下面推论紧接着280页推论11.7 【推论11.8*】设G是简单图，”，y,是不相邻顶点，且满足d()+d(v,)≥n。则G存在 哈密尔顿圈的充要条件是G+(y,V,)有哈密尔顿圈。 【证】必要性显然，下面证充分性。假定G中不存在哈密顿圈，则G+(,')中存在的哈 密顿圈一定经过边(y,y),删去(y,)),即G中存在一条以，y,为端点的哈密顿路，又 因d(y,)+d(v,)≥n,仿照定理11.9证明(2)(c)中的方法，可以构造出哈密顿圈，与假设矛 盾。 以下内容加在习题11.4前面 【定义11.*】若y,和v,是简单图G的不相邻顶点，且满足d(y)+d(v,)≥n,则令 G'=G+(心，y),对G重复上述过程，直至不再有这样的顶点对为止。最终得到的图称为 G的闭合图，记作C(G)。 【引理11.*】简单图的闭合图是唯一的。 【证】设C(G)和C2(G)是G的两个闭合图，E1={a,a2,…a,}，E2={b,b2,…b} 分别是C(G)和C,(G)中新加入边的集合，可以证明E,=E2,即C(G)=C,(G)。如若不
i g b c d e f h a 图11--** e d a b c 图11--** 11.4 欧拉图和哈密顿图 下面推论紧接着 280 页推论 11.7 【推论 11. 8*】 设G 是简单图， , i j v v 是不相邻顶点，且满足 ( ) ( ) i j d v d v n 。则G 存在 哈密尔顿圈的充要条件是 ( , ) G i j v v 有哈密尔顿圈。 【证】必要性显然，下面证充分性。假定G 中不存在哈密顿圈，则 ( , ) G i j v v 中存在的哈 密顿圈一定经过边( , ) i j v v ，删去 ( , ) i j v v ，即G 中存在一条以 , i j v v 为端点的哈密顿路，又 因 ( ) ( ) i j d v d v n ，仿照定理 11.9 证明(2)(c)中的方法，可以构造出哈密顿圈，与假设矛 盾。 以下内容加在习题 11.4 前面 【定义 11. *】若 i v 和 j v 是简单图 G 的不相邻顶点，且满足 ( ) ( ) i j d v d v n ，则令 ' ( , ) G G i j v v ，对G ' 重复上述过程，直至不再有这样的顶点对为止。最终得到的图称为 G 的闭合图，记作C(G)。 【引理 11. *】简单图的闭合图是唯一的。 【证】设 1 C (G) 和 2 C (G)是G 的两个闭合图， 1 1 2 { , , } E r a a a ， 2 1 2 { , , } E s b b b 分别是 1 C (G) 和 2 C (G)中新加入边的集合，可以证明 E1 E2 ，即 1 2 C (G) C (G) 。如若不
是这样，则不失一般性，设a+1=(u,v)∈E,是构造C(G)时第一条不属于E2的边，亦即 a1C2(G)。令H=GU{a,a2,…a,},，这时H是C(G)和C,(G)的子图。由于构造 C,(G)时要加入a1,显然H中满足d(w)+d(v)≥n,但(u,)C2(G),与C2(G)是G的 闭合图矛盾。 【定理11.*】简单图G是哈密顿图的充要条件是其闭合图是哈密顿图。 证明：设C(G)=GUE1,E,={e,e2,e,},由上面推论11.8*和引理11.*，G有哈密顿圈 台G+e,有哈密顿圈一…台GUE,有哈密顿圈。由于C(G)唯一，故定理得证。 请在排版时把此定理证明中的推论11.8*和引理11.*换成相应编号。 12.2欧拉公式和极大平面图 将289页第19行的“本节以下内容中的G均是简单连通可平面图，且共有n(n≥3)个顶 点，m条边，r个面。”删去（因为这句话在本节中只影响到了定理12.3）。并在此处加上 一个推论12.2（或者借用习题12.1第一题的结论），后面的推论编号相应增加1。 【推论12.2】设G是平面图，有k个连通分量（若G为连通图则k=1),n个顶点，m条 边，r个面，则n-m+r=k+1。 【证】对G中连通分量的个数k用归纳法来证明。当k=1时，G为连通图，由欧拉定理， 结论显然成立。假设当k=p-1时，n-m+r=k+1=p成立，考虑k=p时的情况。易证， 在G中一定存在这样的连通分量，它的内部面中没有其它的连通分量，即其它连通分量都 在它的外部面中。任取这样的一个连通分量G,设G有n个顶点，m条边，r个内部面， 则将G从G中移出后得到的子图G-G中，有n-n个顶点，m-m条边，r-r个面。这 是因为G的顶点和边都与其它连通分量不相交，而G的外部面在G-G中仍然保留，内部 面则全部移出。于是由归纳假设，G-G为有p-1个连通分量的平面图，有 (n-n,)-(m-m,)+(r-r)=p。而我们知道G是连通平面图，有r+1个面，由欧拉定理有 n-m,+(G+1)=2，于是易得n-m+r=p+1=k+1成立。证毕。 定理12.3改为： 【定理12.3】设G是简单连通平面图，有n个顶点，m条边，r个面，若G的每个面的度 大于等于k,则 ≤m≤km-2) 2 k-2
是这样，则不失一般性，设 1 1 ( , ) i a u v E 是构造 1 C (G) 时第一条不属于 E2 的边，亦即 1 2 ( ) i a C G 。令 1 2 { , , } H G i a a a ，这时 H 是 1 C (G) 和 2 C (G) 的子图。由于构造 1 C (G) 时要加入 i 1 a ，显然 H 中满足 d(u) d(v) n ，但 2 (u, v)C (G) ，与 2 C (G)是G 的 闭合图矛盾。 【定理 11. *】简单图G 是哈密顿图的充要条件是其闭合图是哈密顿图。 证明：设 1 C(G) G E , 1 1 2 { , , } E r e e e ,由上面推论 11.8*和引理 11.*， G 有哈密顿圈 G 1 e 有哈密顿圈 G E1有哈密顿圈。由于C(G) 唯一，故定理得证。 请在排版时把此定理证明中的推论 11.8*和引理 11.*换成相应编号。 12.2 欧拉公式和极大平面图 将 289 页第 19 行的 “本节以下内容中的 G 均是简单连通可平面图，且共有 n（n 3）个顶 点，m 条边，r 个面。” 删去（因为这句话在本节中只影响到了定理 12.3）。并在此处加上 一个推论 12.2（或者借用习题 12.1 第一题的结论），后面的推论编号相应增加 1。 【推论 12.2】 设 G 是平面图，有 k 个连通分量（若 G 为连通图则 k = 1），n 个顶点，m 条 边，r 个面，则 n – m + r = k + 1。 【证】 对 G 中连通分量的个数 k 用归纳法来证明。当 k = 1 时，G 为连通图，由欧拉定理， 结论显然成立。假设当 k = p – 1 时，n – m + r = k + 1 = p 成立，考虑 k = p 时的情况。易证， 在 G 中一定存在这样的连通分量，它的内部面中没有其它的连通分量，即其它连通分量都 在它的外部面中。任取这样的一个连通分量G1，设G1有 1 n 个顶点， m1 条边， 1r 个内部面， 则将G1从 G 中移出后得到的子图G G1 中，有 1 n n 个顶点， m m1 条边， 1 r r 个面。这 是因为G1的顶点和边都与其它连通分量不相交，而G1的外部面在G G1 中仍然保留，内部 面 则 全 部 移 出 。 于 是 由 归 纳 假 设 ， G G1 为 有 p – 1 个 连 通 分 量 的 平 面 图 ， 有 1 1 1 (n n ) (m m ) (r r ) p 。而我们知道G1是连通平面图，有 1r 1个面，由欧拉定理有 1 1 1 n m (r 1) 2 ，于是易得 n m r p 1 k 1成立。证毕。 定理 12.3 改为： 【定理 12.3】 设 G 是简单连通平面图，有 n 个顶点，m 条边，r 个面，若 G 的每个面的度 大于等于 k，则 ( 2) 2 2 n k k m kr
推论12.2改为12.3，且增加了对于G是非连通图的证明。 【推论12.3】G为n(n≥3)阶m条边的简单平面图，则m≤3n-6,且等号成立当且仅当 G是极大平面图。 【证】依据条件G中各面的度大于等于3，由定理12.1知，3r≤2m。再由推论12.2知n- m+r=k+1≥2，即r2m-n+2,代入3r≤2m中即得m≤3n-6。由定理12.5知，G是极 大平面图当且仅当G的每个面的度为3，从而3r=2m,即m=3n-6。证毕。 14.2生成树与最小生成树 在306页最后加上下面的定理。 【定理14.*】：对连通带权图G=(V,E)运行Kruskal算法，生成的树是最小生成树。 【证】：设V=n,记T是由Kruskal算法所得到的G的一棵生成树。T中的边的标号为 e,e2,en,这是该算法产生的顺序。对于G的每棵最小生成树T',定义f(T)=k，,如 果k是使得T和T'中都包括e,e2,…ek-1但exT'的最小正整数。 令T是一棵最小生成树并且满足f(T)=”最大。如果r=n,则T=T从而结论成立。 否则，有rr=f(T),这 就和对T的选择矛盾。因此T=T并且由Kurskal算法所产生的树是最小生成树
推论 12.2 改为 12.3，且增加了对于 G 是非连通图的证明。 【推论 12.3】G 为 n（n 3）阶 m 条边的简单平面图，则 m 3n – 6，且等号成立当且仅当 G 是极大平面图。 【证】 依据条件 G 中各面的度大于等于 3，由定理 12.1 知，3r 2m。再由推论 12.2 知 n – m + r = k + 1 2，即 r m – n + 2，代入 3r 2m 中即得 m 3n – 6。由定理 12.5 知，G 是极 大平面图当且仅当 G 的每个面的度为 3，从而 3r = 2m，即 m = 3n – 6。证毕。 14.2 生成树与最小生成树 在 306 页最后加上下面的定理。 【定理 14.*】：对连通带权图G (V ,E) 运行 Kruskal 算法，生成的树是最小生成树。 【证】：设|V | n ，记T 是由 Kruskal 算法所得到的 G 的一棵生成树。T 中的边的标号为 1 2 1 , , n e e e ，这是该算法产生的顺序。对于G 的每棵最小生成树T ，定义 f (T) k ，如 果 k 是使得T 和T 中都包括 1 2 1 , , k e e e 但 ' k e T 的最小正整数。 令T1是一棵最小生成树并且满足 1 f (T ) r 最大。如果 r n ，则T T1 从而结论成立。 否则，有 r n 并且把T 中的边 r e 加到T1上，就产生了圈C ，其中存在C 的一条边 r e ，这 条边在T1中，但不在T 中。 从树T1开始，把 r e 加到T1上并且删除 r e ，我们得到一个具有 n 个顶点和 n 1条边的连 通图。这个图是一棵生成树，记为T2 。T1和T2 满足 2 1 ( ) ( ) ( ) ( ) W T W T W r r e W e 。 在 Kurskal 算法选择了 1 2 1 , r e e e 后， r e 的选取要使得 ( ) W r e 最小，并且当 r e 加到由 1 2 1 , r e e e 组成的图上时，不会产生圈。由于 ( ) W r e 的最小性，说明了 ( ) ( ) W r r e W e 。因 此 2 1 W (T ) W (T ) 。但是由于T1是最小生成树，所以必须有 2 1 W (T ) W (T ) ，所以T2 是最 小生成树。 T2 是最小生成树并且和T1有公共边 1 2 1 , , r r e e e e ，所以 2 1 f (T ) r 1 r f (T ) ，这 就和对T1的选择矛盾。因此T1 T 并且由 Kurskal 算法所产生的树是最小生成树
【定理14.*】：对连通带权图G=(W,E)运行Prim算法，生成的树是最小生成树。 【证】：设该连通带权图有n个顶点，m条边。T是算法中边的集合，下面对T中的边数k进 行归纳法，证明生成树是最小的。 归纳假设是：当T有k条边时，T包含在某棵最小生成树中。 当k=0时，T是一个空集，由于连通带权图存在最小生成树，所以当m=0时，假设 成立。现在假设k=时，假设成立，即T包含在一棵最小生成树T'中。下面考虑 k=i+1。 设U是Prim算法给出的顶点集合，假设(u,v)是下一条将被加入到T中的边，其中u在 U中，v不在U中。如果(u,v)在T'中，那么归纳假设成立，证明完成。下面假设(u,v) 不在T'中，由于T'是一棵最小生成树，所以T'中存在一条从到v的通道。另外因为 u∈U,v庄U,所以此条通道一定包含一条边e,它的一个顶点在U中而另外一个顶点不 在U中。 从上面分析，我们知道Prim算法选择了边(u,v)而不是边e,所以(u,v)的权一定不大 于e的权。于是，如果将(u,v)加入到T'中，并从T'中去掉e构成T",那么T"的权不会增 加。由于T"是连通的且有n-1条边，所以它是一棵最小生成树。但T”包含了TU(u,v)的 i+1条边，这就对i+1证明了归纳假设。 由数学归纳法可知，Pm算法产生的树T总是包含在一棵最小生成树中。当算法结束 且n-1条边时，此时T即是最小生成树。总上，Prim算法产生一棵最小生成树。 习题14.2补二道习题 l3.分别利用Kruskal算法和Prim算法求下图的最小生成树。 G 14.利用Prim算法求出下图的最小生成树
【定理 14.*】：对连通带权图G (V ,E) 运行 Prim 算法，生成的树是最小生成树。 【证】：设该连通带权图有 n 个顶点，m 条边。T 是算法中边的集合，下面对T 中的边数 k 进 行归纳法，证明生成树是最小的。 归纳假设是：当T 有 k 条边时，T 包含在某棵最小生成树中。 当 k 0 时，T 是一个空集，由于连通带权图存在最小生成树，所以当 m 0时，假设 成立。现在假设 k i 时，假设成立，即T 包含在一棵最小生成树T 中。下面考虑 k i 1。 设U 是 Prim 算法给出的顶点集合，假设(u, v) 是下一条将被加入到T 中的边，其中u 在 U 中，v 不在U 中。 如果(u, v) 在T 中，那么归纳假设成立，证明完成。下面假设(u, v) 不在T 中，由于T 是一棵最小生成树，所以T 中存在一条从 u 到 v 的通道。另外因为 u U,v U ，所以此条通道一定包含一条边 e ，它的一个顶点在U 中而另外一个顶点不 在U 中。 从上面分析，我们知道 Prim 算法选择了边(u, v) 而不是边e ，所以(u, v) 的权一定不大 于e 的权。于是，如果将(u, v) 加入到T 中，并从T 中去掉e 构成T，那么T的权不会增 加。由于T是连通的且有 n 1条边，所以它是一棵最小生成树。但T包含了T (u,v) 的 i 1条边，这就对i 1证明了归纳假设。 由数学归纳法可知，Prim 算法产生的树T 总是包含在一棵最小生成树中。当算法结束 且 n 1条边时，此时T 即是最小生成树。总上，Prim 算法产生一棵最小生成树。 习题 14.2 补二道习题 13．分别利用 Kruskal 算法和 Prim 算法求下图的最小生成树。 a b g h i G c d e f 4 8 7 8 11 7 1 2 6 4 14 9 10 2 14．利用 Prim 算法求出下图的最小生成树
c 7 9 7 15 e d 8 9 f 1ì
9 7 8 d 6 f 155 115 5 8 9 5 7 g e a c b