第23讲 平面图 北京大学计算机系离散数学讲义(ppt版).pptVIP

《集合论与图论》第23讲 第23讲 平面图 四色问题 平面图,面, 极大平面图 欧拉公式 Kuratowski定理 对偶图,自对偶图 外平面图 平面哈密顿图 四色问题(Four Color Problem) 1852, Francis Guthrie, 注意到英格兰地图可以用4种颜色染色, 使得相邻区域(有一段公共边界,不只是有一个公共点)有不同颜色; 他问其弟 Frederick 是否任意地图都有此性质? Frederick Guthrie ? DeMorgan ? Hamilton. 1878, Cayley, 提交伦敦数学会. 约定: 无飞地 四色问题(Four Color Problem) 四色问题(Four Color Problem) 1879, Kempe, 第一次“证明” 1890, Heawood 发现Kempe证明的错误 1880, Tait, 另一个错误证明 1891, Petersen发现Tait证明的漏洞(Tait猜想) 1946, Tutte发现Tait证明的错误(Tait猜想反例) 两次错误证明带来的收获: “Kempe chains”, 用“3-边-着色”描述的四色定理的等价形式. 四色问题(Four Color Problem) 1913, Birkhoff, 下一个大贡献, 导致 1922, Franklin, 证明不超过25个区域的地图四色猜想成立 其他人取得其他形式进展:1974,52区域 四色问题(Four Color Problem) 1936-50,Heesch,最终解决问题的两个要素: 10000个情形,100年 约化(reducibility), 放电(discharging). 1972-76, Appel, Haken, 1482个情形, IBM360, 1200小时, 论文139页+400页程序, conjectureagnogramstheorem 四色问题(Four Color Problem) 猜想(conjecture)agnograms定理(theorem) 另外一个证明? 四色问题(Four Color Problem) 平面图 可平面图(planar graph): 可以画在平面上,使得边与边不在非顶点处相交的图 平面嵌入(imbedding): 画在平面上使得边与边不在非顶点处相交 平面图(plane graph): 在平面上边与边不在非顶点处相交的图 球面嵌入, 曲面嵌入 球面嵌入: 画在球面上使得边与边不在非顶点处相交 曲面嵌入: 画在曲面上使得边与边不在非顶点处相交, 如环面嵌入 定理11.1: 可平面嵌入?可球面嵌入 证明: 连续球极投影. # 面 区域(region):不含顶点与边的极大连通曲面, R 外部区域(exterior region): 面积无限的区域, R0 区域边界(boundary of region): 与R关联的边和顶点构成的子图 面(face): 区域及其边界 面的次数(degree): deg( R )=边界长度 定理 定理11.2: ?ri=1deg(Ri)=2m. # 定理11.3: 任何平面嵌入的内部面都可以在另一种平面嵌入下成为外部面 证明: 平面嵌入? 球面嵌入? 把该面旋转到北极 ? 平面嵌入. # 极大(maximal)平面图 极大平面图: 是平面图, 但是在任意两个不相邻顶点之间加边就是非平面图 定理11.4: n(?3)阶简单连通平面图是极大平面图??R,deg( R )=3 证明: (?)简单图?deg( R )?3, 极大平面图?deg( R )?3 (?)?R,deg(R )=3?不能加边而不交叉. # 极小非平面图:是非平面图, 但是删除任意1边就是平面图 欧拉公式 欧拉公式: 设G是连通平面图, 则 n-m+r=2 其中r是G的面数. 例: n=7,m=11,r=6: 7-11+6=2. # 欧拉公式(推广形式) 欧拉公式: 设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. # 定理11.8 定理11.8: 设G是连通平面图, G的各面的次数至少是l(?3), 则 m?(n-2)l/(l-2) 证明: r=2+m-n, 2m=?ri=1deg(Ri)?l?r=l?(2+m-n), 所以 m?(n-2)l/(l-2). # 定理11.9: 设