北京大学：《离散数学》系列课程之一《集合论与图论》第23讲 平面图

第23讲平面图 四色问题 秦平面图,面,极大平面图 秦欧拉公式 秦 Kuratowski定理 秦对偶图,自对偶图 外平面图 平面哈密顿图 《集合论与图论》第23讲

《集合论与图论》第23讲 1 第23讲 平面图 四色问题 平面图,面, 极大平面图 欧拉公式 Kuratowski定理 对偶图,自对偶图 外平面图 平面哈密顿图

四色问题( Four color problem 婚1852, Francis guthrie,注意到英格兰地 图可以用4种颜色染色,使得相邻区域(有 段公共边界不只是有一个公共点)有不 同颜色;他问其弟 Frederick是否任意地 图都有此性质? Frederick guthrie→ DeMorgan Hamilton 1878, Cayley,提交伦敦数学会 秦约定:无飞地 《集合论与图论》第23讲

《集合论与图论》第23讲 2 四色问题(Four Color Problem) 1852, Francis Guthrie, 注意到英格兰地 图可以用4种颜色染色, 使得相邻区域(有 一段公共边界,不只是有一个公共点)有不 同颜色; 他问其弟 Frederick 是否任意地 图都有此性质? Frederick Guthrie Æ DeMorgan Æ Hamilton. 1878, Cayley, 提交伦敦数学会. 约定: 无飞地

四色问题( Four color problem 《集合论与图论》第23讲

《集合论与图论》第23讲 3 四色问题(Four Color Problem)

四色问题( Four color problem 1879, Kempe,第一次“证明” 1890, Heawood发现 Kempe证明的错误 1880,Ta,另一个错误证明 1891, Petersen发现Taii明的漏洞(Tat猜想) 1946,Tutt发现Tait证明的错误(Tait猜想反例) 两次错误证明带来的收获: “ Kempe chains, ●用“3-边-着色”描述的四色定理的等价形式 《集合论与图论》第23讲

《集合论与图论》第23讲 4 四色问题(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, Birkhof,下一个大贡献,导致 秦192, Franklin,证明不超过25个区域的 地图四色猜想成立 其他人取得其他形式进展:1974,52区域 《集合论与图论》第23讲

《集合论与图论》第23讲 5 四色问题(Four Color Problem) 1913, Birkhoff, 下一个大贡献, 导致 1922, Franklin, 证明不超过25个区域的 地图四色猜想成立 其他人取得其他形式进展:1974,52区域

四色问题( Four color problem 1936-50Hech,最终解决问题的两个要 素:1000C个情形,100年 约化 (reducibility 放电( ischarging) 1972-76, Appel, Haken,1482个情形, BM360,1200小时,论文139页+400页程 F, conjecture<agnograms <theorem 《集合论与图论》第23讲

《集合论与图论》第23讲 6 四色问题(Four Color Problem) 1936-50,Heesch,最终解决问题的两个要 素: 10000个情形,100年 约化(reducibility), 放电(discharging). 1972-76, Appel, Haken, 1482个情形, IBM360, 1200小时, 论文139页+400页程 序, conjecture<agnograms<theorem

四色问题( Four color problem 猜想( conjecture)< sagnograms<定理 ( theorem 另外一个证明? 《集合论与图论》第23讲

《集合论与图论》第23讲 7 四色问题(Four Color Problem) 猜想(conjecture)<agnograms<定理 (theorem) 另外一个证明?

四色问题( Four color problem 《集合论与图论》第23讲

《集合论与图论》第23讲 8 四色问题(Four Color Problem)

平面图 可平面图( planar graph)可以画在平面上, 使得边与边不在非顶点处相交的图 平面嵌入( imbedding):画在平面上使得边 与边不在非顶点处相交 平面图( plane graph在平面上边与边不 在非顶点处相交的图 《集合论与图论》第23讲

《集合论与图论》第23讲 9 平面图 可平面图(planar graph): 可以画在平面上, 使得边与边不在非顶点处相交的图 平面嵌入(imbedding): 画在平面上使得边 与边不在非顶点处相交 平面图(plane graph): 在平面上边与边不 在非顶点处相交的图

球面嵌入,曲面嵌入 婚球面嵌入:画在球面上使得边与边不在非 顶点处相交 曲面嵌入:画在曲面上使得边与边不在非 顶点处相交,如环面嵌入 定理111可平面嵌入兮可球面嵌 证明:连续球极投影.# 《集合论与图论》第23讲

《集合论与图论》第23讲 10 球面嵌入, 曲面嵌入 球面嵌入: 画在球面上使得边与边不在非 顶点处相交 曲面嵌入: 画在曲面上使得边与边不在非 顶点处相交, 如环面嵌入 定理11.1: 可平面嵌入⇔可球面嵌入 证明: 连续球极投影. #