第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区域