《集合论与图论》第23讲1 第23讲平面图 ?四色问题 ?平面图,面, 极大平面图 ?欧拉公式 ?Kuratowski定理 ?对偶图,自对偶图 ?外平面图 ?平面哈密顿图 《集合论与图论》第23讲2 四色问题(Four Color Problem) ?1852, Francis Guthrie, 注意到英格兰地 图可以用4种颜色染色, 使得相邻区域(有 一段公共边界,不只是有一个公共点)有不 同颜色;他问其弟Frederick 是否任意地 图都有此性质? Frederick Guthrie ? DeMorgan ? Hamilton. ?1878, Cayley, 提交伦敦数学会. ?约定: 无飞地 《集合论与图论》第23讲3 四色问题(Four Color Problem) 《集合论与图论》第23讲4 四色问题(Four Color Problem) ? 1879, Kempe, 第一次“证明” ? 1890, Heawood 发现Kempe证明的错误 ? 1880, Tait, 另一个错误证明 ? 1891, Petersen发现Tait证明的漏洞(Tait猜想) ? 1946, Tutte发现Tait证明的错误(Tait猜想反例) ?两次错误证明带来的收获: ? “Kempe chains”, ?用“3-边-着色”描述的四色定理的等价形式. 《集合论与图论》第23讲5 四色问题(Four Color Problem) ?1913, Birkhoff, 下一个大贡献, 导致 ?1922, Franklin, 证明不超过25个区域的 地图四色猜想成立 ?其他人取得其他形式进展:1974,52区域 《集合论与图论》第23讲6 四色问题(Four Color Problem) ?1936-50,Heesch,最终解决问题的两个要 素: 10000个情形,100年 ?约化(reducibility), ?放电(discharging). ?1972-76, Appel, Haken, 1482个情形, IBM360, 1200小时, 论文139页+400页程 序, conjecture<agnograms<theorem 《集合论与图论》第23讲7 四色问题(Four Color Problem) ?猜想(conjecture)<agnograms<定理 (theorem) ?另外一个证明? 《集合论与图论》第23讲8 四色问题(Four Color Problem) 《集合论与图论》第23讲9 平面图 ?可平面图(planar graph): 可以画在平面上, 使得边与边不在非顶点处相交的图 ?平面嵌入(imbedding): 画在平面上使得边 与边不在非顶点处相交 ?平面图(plane graph): 在平面上边与边不 在非顶点处相交的图 《集合论与图论》第23讲10 球面嵌入, 曲面嵌入 ?球面嵌入: 画在球面上使得边与边不在非 顶点处相交 ?曲面嵌入: 画在曲面上使得边与边不在非 顶点处相交, 如环面嵌入 ?定理11.1: 可平面嵌入?可球面嵌入 ?证明: 连续球极投影. # 《集合论与图论》第23讲11 面 ?区域(region):不含顶点与边的极大连通曲 面, R ?外部区域(exterior region): 面积无限的区 域, R 0 ?区域边界(boundary of region): 与R 关联的边和顶点构成的子图 ?面(face): 区域及其边界 ?面的次数(degree): deg( R )=边界长度 R? 《集合论与图论》第23讲12 定理 ?定理11.2: Σ r i=1 deg(R i )=2m. # ?定理11.3: 任何平面嵌入的内部面都可以 在另一种平面嵌入下成为外部面 ?证明: 平面嵌入?球面嵌入?把该面旋 转到北极?平面嵌入. # 《集合论与图论》第23讲13 极大(maximal)平面图 ?极大平面图: 是平面图, 但是在任意两个 不相邻顶点之间加边就是非平面图 ?定理11.4: n(≥3)阶简单连通平面图是极大 平面图??R,deg( R )=3 ?证明: (?)简单图?deg( R )≥3, 极大平面图?deg( R )≤3 (?)?R,deg(R )=3?不能加边而不交叉. # ?极小非平面图:是非平面图, 但是删除任 意1边就是平面图 《集合论与图论》第23讲14 欧拉公式 ?欧拉公式: 设G是连通平面图, 则 n-m+r=2 其中r是G的面数. ?例: n=7,m=11,r=6: 7-11+6=2. # 《集合论与图论》第23讲15 欧拉公式(推广形式) ?欧拉公式: 设G是平面图, 则 n-m+r=1+p 其中r是G的面数, p是G的连通分支数 ?证明:(破圈法)任选一个回路,删除回路上1 边,m’=m-1,这边分隔的2个面合并,r’=r-1, 所以n-m+r=n-m’+r’. 到最后无回路时是 森林, m’’=n-p, r’’=1, 即n-m+r=n- m’’+r’’=1+p. # 《集合论与图论》第23讲16 定理11.8 ?定理11.8: 设G是连通平面图, G的各面的 次数至少是l(≥3), 则 m≤(n-2)l/(l-2) ?证明: r=2+m-n, 2m=Σ r i=1 deg(R i )≥l?r=l?(2+m-n), 所以m≤(n-2)l/(l-2). # ?定理11.9: 设平面图G有p个连通分支, G 的各面的次数至少是l(≥3), 则 m≤(n-p-1)l/(l-2). # 《集合论与图论》第23讲17 推论 ?推论: K 5 和K 3,3 都不是平面图. ?证明: (反证)假设K 5 和K 3,3 都是平面图. (1) K 5 是简单图, 所以l =3, 10=m≤(n-2)l/(l-2)=(5-2)3/(3-2)=9, 矛盾! (2) K 3,3 是偶图,无奇圈,所以l =4, 9=m≤(n-2)l/(l-2)=(6-2)4/(4-2)=8, 矛盾! # ? Jordan定理: Jordan曲线(自身不相交封闭曲线) 把平面分为2部分, 连接内部与外部点的任意曲 线必然与Jordan曲线相交. 《集合论与图论》第23讲18 定理11.10 ?定理11.10: 设n(≥3)阶简单平面图G有m 条边,则m≤3n-6. # ?证明: G是简单图, 所以l ≥3, m≤(n-p-1)l/(l-2)≤(n-2)3=3n-6, 其中p≥1, l/(l-2)在l =3时达到最大值. # ?定理11.11: 设n(≥3)阶简单极大平面图G 有m条边,则m=3n-6. # ?证明: G是极大平面图, 所以2m=3r, r=2+m-n. # 《集合论与图论》第23讲19 定理11.12 ?定理11.12: 设G是简单平面图,则δ(G)≤5. ?证明: (反证) 设n≥6并且δ≥6, 则 2m=Σd(v)≥nδ≥6n ? m≥3n, 与m≤3n-6 矛盾. # 《集合论与图论》第23讲20 同胚(homomorphism) ?插入2度顶点: 把(u,v)变成(u,w),(w,v) ?删除2度顶点: deg(w)=2, 把(u,w),(w,v)变 成(u,v) ?同胚: 反复插入或删除2度顶点后同构 uuvvw 《集合论与图论》第23讲21 Kuratowski定理 ?定理11.13: 图G是平面图? G没有与K 5 或K 3,3 同胚的子图 ?定理11.14: 图G是平面图? G没有可以 边收缩到K 5 或K 3,3 的子图 《集合论与图论》第23讲22 例11.3 《集合论与图论》第23讲23 例11.3(1) K 5 K 3,3 《集合论与图论》第23讲24 例11.3(2) K 5 K 3,3 《集合论与图论》第23讲25 例11.3(3) K 5 K 3,3 《集合论与图论》第23讲26 例11.6 ?例11.6: K 6 的含K 3,3 的非同构子图有哪些? ?解: K 6 有15条边, K 3,3 有9条边, 分别给K 3,3 加0,1,2,3,4,5,6条边: 共10种. # 《集合论与图论》第23讲27 对偶图(dual graph) ?对偶图: 平面图G=<V,E>的对偶图是 G*=<V*,E*>, 设G和G*的面集合是R和R*, 则V*与R, E*与E,都是一一对应的 《集合论与图论》第23讲28 对偶图的性质 ?对偶图是连通平面图 ?环与桥互相对偶 ?平行边对偶于2个面之间的多条边界 ?n*=r,m*=m,r*=n-p+1,d G* (v i *)=deg G (R i ) ?G 1 ?G 2 ,不一定G 1 *?G 2 * 《集合论与图论》第23讲29 自对偶(self-dual)图 ?自对偶图: G?G*. ?n≥4时, 轮图W n 是自对偶图 ?G连通? G?G**(要求G*不改变形状) 《集合论与图论》第23讲30 外平面图 ?外平面图: 平面图的所有顶点可都在一个 面的边界上, 例: (1)(2) ?极大外平面图: 本身是外平面图,但是在 不相邻顶点之间加边就不是外平面图了, 例: (1) 《集合论与图论》第23讲31 外平面图(充要条件) ?定理11.22: G是外平面图? G不含与K 4 或K 2,3 同胚的子图. # 《集合论与图论》第23讲32 极大外平面图(充要条件) ?定理11.19: 设G是所有顶点在外部面边界 上的n(≥3)阶外平面图, 则G是极大外平 面图? G外部面边界是n-圈, 所有内部面 边界是3-圈. # (“三角剖分”) 《集合论与图论》第23讲33 极大外平面图(必要条件) ?定理11.20:设G是所有顶点在外部面边界 上的n(≥3)阶极大外平面图,则G有n-2个 内部面. # ?定理11.21: 设G是n(≥3)阶极大外平面图, 则m=2n-3, κ=2, 至少有3个顶点度数≤3, 至少有2个顶点度数=2. # 《集合论与图论》第23讲34 平面哈密顿图(Tait猜想) ?Tait猜想(1880): 3连通3正则平面图都是 哈密顿图 ?Tutte图(1946): 46阶反例(左图) ?Lederberg图(1967): 38阶反例(右图) 《集合论与图论》第23讲35 平面哈密顿图(充分条件) ?定理(Tutte,1956): 4连通平面图是哈密顿 图. # 《集合论与图论》第23讲36 平面哈密顿图(必要条件) ?定理(grinberg,1968): 设G是n阶简单平面 哈密顿图, C是其中的哈密顿回路, 在C内 (外)部次数为i的面数为r i ’(r i ”), 则 Σ n i=3 (i-2)(r i ’-r i ”)=0. # ?证明: 设C内有m 1 条边,则Σ n i=3 r i ’=m 1 +1. 又Σ Rj内部面 deg( R j )=Σ n i=3 ir i ’=2m 1 +n, 所以 Σ n i=3 (i-2)r i ’=n-2, 同理Σ n i=3 (i-2)r i ”=n-2. # 《集合论与图论》第23讲37 例11.5 ?例11.5: 下图中不存在过边(a,b)的哈密顿 回路. (由此可证Tutte图和Lederberg图 不是哈密顿图.) # 38 5 5 5 5 5 4 4 a b 《集合论与图论》第23讲38 总结 ?四色问题 ?平面图,面,极大平面图 ?欧拉公式, Kuratowski定理 ?对偶图,自对偶图 ?外平面图 ?平面哈密顿图 《集合论与图论》第23讲39 作业(#19) ? p298, 习题十一, 3,6,7,13,14 ?今天交作业#17, #18 《集合论与图论》第23讲40 习题讲解(#14) ?p234, 习题八, 7,9,13 ?7. 《集合论与图论》第23讲41 习题讲解(#14) ?p234, 习题八, 7,9,13 ?9. |E(K n )|=n(n-1)/2, m=(n-1)(n-2)/2+2, |E(K n )|-m=n-3, G是从K n 删除n-3边. ?u,v∈V(G), (u,v)?E(G)?d(u)+d(v)≥ 2(n-1)-2-(n-4)=n, ∴ G是哈密顿图. 反例: G是从K n 删除n-2边, δ(G)=1. # 《集合论与图论》第23讲42 习题讲解(#14) ?p234, 习题八, 7,9,13 ?13. G=<V,E>,E={ (u,v) | u和v认识}, ?u,v∈V(G), d(u)+d(v) ≥ n-2, n≥4 ? d(u)+d(v)≥ n-2 ≥ n/2 , ∴ n≥4时G是哈密顿图(?). n=3时, 只有2种 可能: K 3 或K 3 删除1边, G是半哈密顿图. # 《集合论与图论》第23讲43 习题讲解(#15) ? p256, 习题九, 2,3,6,11 ? 2. 设有x个4度顶点, 由握手定理 9+3×3+4x=2(9+3+x-1), x=2. 度数列1 9 3 3 4 2 , 考虑3 3 4 2 , d(T)=T直径 d(T)=6: 33344, 33434, 34334, 43334, 33443, 34343 d(T)=5: 3443, 4433, 4343, 4333, 4333, 3433, 3433, d(T)=4: 344, 14种非同构的. # 《集合论与图论》第23讲44 习题讲解(#15) ?p256, 习题九, 2,3,6,11 ?3. 设有x个树叶, 由握手定理 2(x+n 2 +…+n k -1)=x+2n 2 +3n 3 +…+kn k x= n 3 +2n 4 +…+(k-2)n k +2. # ?6. (反证)假设G和G都无圈, 即都是森林, 所以|E(K n )|=|E(G)|+|E(G)|≤2(n-1), n≥5?|E(K n )|=n(n-1)/2>2(n-1), 矛盾! # 《集合论与图论》第23讲45 习题讲解(#15) ?p256, 习题九, 2,3,6,11 ?11. 设有x个树叶, 由握手定理 2(n-1)=2m =Σd(v)=Σ d(v)=1 d(v)+Σ d(v)=Δ d(v)+Σ 其余v d(v) ≥x+k+2(n-x-1) ∴ x≥k. # 《集合论与图论》第23讲46 习题讲解(#16) ?p256, 习题九, 10, 12 ?10. T={e,g,d,j,i}, T={a,b,c,f,h}, C a =aegdj,C b =bgdji,C c =cgd, C f =fge, C h =hji, C 基 ={C a ,C b ,C c ,C f ,C h }. S e ={e,a,f}, S g ={g,a,b,c,f},S d ={d,b,c,a}, S j ={j,a,b,h}, S i ={i,b,h}, S 基 ={S e ,S g ,S d ,S j ,S i }. # 《集合论与图论》第23讲47 习题讲解(#16) ?p256, 习题九, 10, 12 ?12. 证明: 引理: G连通, 设(V,V)是断集,则 (V,V)是割集? G[V]和G[V]都连通 证明引理: 割集的极小性. # 《集合论与图论》第23讲48 习题讲解(#16) ?p256, 习题九, 10, 12 ?12. 证明(续): 利用引理, 考虑圈C所在的 连通分支G 1 . 设C-{e 1 ,e 2 }的两个连通分支 是C 1 和C 2 . G 1 的顶点分成5组(可能为空): V 1 =V(C 1 ), V 2 =V(C 2 ), V 3 ={v?V 1 |v与C 1 连 通}, V 4 ={v?V 2 |v与C 2 连通}, V 5 =V(G 1 )- U 4 i=1 V i . 令V=V 1 ∪V 3 , 则(V,V)是含e 1 ,e 2 的 割集. # 《集合论与图论》第23讲49 习题讲解(#16) ?p370, 习题十四, 9 ?9. 避圈,破圈,断集,逐步短接 12 3 44 7 56 12 3 44 7 56 12 3 44 7 56 12 3 44 7 56 12 3 44 7 56 12 3 44 7 56 12 3 44 56 12 3 4 56 12 4 56 《集合论与图论》第23讲50 习题讲解(#16) ?9. 避圈,破圈,断集,逐步短接 12 3 44 7 56 12 3 44 7 56 12 3 44 7 56 12 3 44 7 56 12 3 44 7 56 12 3 44 7 56 12 3 44 56 2 3 4 56 4 56 77 744 56 7 6 7