离散数学教学课件08-几类典型的图.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * 练习 例8.4.2 给定两个平面图G1和G2，试作出他们的对偶图。 G1 G2 * 对偶图 定理：若G=V, E, F是平面图，则? d(f)=2|E| 证明：令G*=V*, E*是G的对偶图，则 ? dG(fi)= ? dG*(vi*) = 2|E*| = 2|E| 定义：若图G的对偶图G*同构于G，则称G是自对偶图 定理： 若平面图G =V, E, F是自对偶图，则 |E| = 2(|V|-1) (作业8-22) * 着色问题 1852年，英国的一个青年盖思里(Guthrie)提出地图的四色猜想问题：在画地图时，如果规定一条边界分开的两个区域涂不同的颜色，那么任何地图可以只用4种颜色涂色 由对偶图的定义容易知道，对于地图的着色问题，可以化为一种等价的对于平面图的结点的着色问题 因此，四色问题可以归结为：对于任意平面图，一定可以用四种颜色，对其结点进行着色，使得相邻结点有不同颜色 * 着色问题 1879年，伦敦的律师和业余数学家艾尔弗雷德·肯普(Kemple)发表了四色定理的证明。数学家们一直把他的证明当作正确的证明来接受。 1890年，这个证明被发现了一处错误而推翻了。不过希伍德(Heawood)沿用肯普的技巧证明了五色定理。 对平面图G着色时，需要最少颜色数称为G的着色数，记为?(G) 五色定理：对于任何简单平面图G=V, E，均有?(G) ≤ 5 * 着色问题 证明：当|V|≤5，显然 ?(G) ≤ 5 假设对于所有平面图，当|V|=k时 ?(G) ≤ 5成立 则当|V|=k+1时，可知存在v0 ? V，有d(v0) ≤ 5 由假设可知， ?(G- v0) ≤ 5 若d(v0) 5，则与v0邻接的结点数不超过4，故可对v0着色，使得G可以正常着色 若d(v0) = 5，则将与v0邻接的结点 v1 v2 v3 v4 v5顺时针排列对它们分别着不同的五色 v0 v2 v3 v4 v5 v1 * 着色问题 称G- v0中所有红、绿色结点为红绿集，所有黄、蓝色结点为黄蓝集。 我们记红绿集所诱导的G- v0的子图为Grg，黄蓝集所诱导的G- v0的子图为Gyb，于是产生了下面两种可能： v1和v3属于Grg的两个不同的分图中 v0 v2 v3 v4 v5 v1 将v3所在分图中的结点红绿对调，并不影响G- v0的正常着色 * 着色问题 称G- v0中所有红、绿色结点为红绿集，所有黄、蓝色结点为黄蓝集。 我们记红绿集所诱导的G- v0的子图为Grg，黄蓝集所诱导的G- v0的子图为Gyb，于是产生了下面两种可能： v1和v3属于Grg的两个不同的分图中 v0 v2 v3 v4 v5 v1 将v3所在分图中的结点红绿对调，并不影响G- v0的正常着色 于是，将v0着为绿色即可得到G的正常着色 * 着色问题 v1和v3属于Grg的同一个分图中 v0 v2 v3 v4 v5 v1 则v1和v3之间存在一条链P，则v0Pv0构成了一个圈， 因此v2和v5必定不可达 因此v2和v5定属于Gyb的两个不同的分图中 将该问题转化为1)的问题，将黄蓝集按1)的办法处理定能得到G的正常着色 综上所述，可知：?(G) ≤ 5 * 着色问题 虽然肯普的证明有错误，但给后面的证明提供了基础 1976年，美国数学家肯尼思·阿佩尔(Appel)和沃尔夫冈·黑肯(Haken)最终借助计算机，用来10亿多个判断，经过了1200多个机时的运行计算，将四色定理加以证明。 四色定理：对于任何简单平面图G=V, E，均有?(G) ≤ 4 * 着色问题 阿佩尔和黑肯的证明依赖于计算机所完成的逐个对各种情形的仔细分析： 他们证明，若四色定理为假，则存在一个反例，应当是大约2000种不同类型的一种。 然后他们证明这些类型都没有导致反例 这个证明引起了广泛的争论，原因是计算机在里面起到如此重要的作用。例如：计算机程序中有没有导致不正确结果的错误？假如他们的论证依赖于或许不可靠的计算机输出，那么是否有效？ * 着色问题 1996年，罗布森等人找到了四色定理的简化证明，将证明的计算部分减少到了检查633种格局，但是仍然还没有找到不依赖于大量计算的证明。 * 着色问题 四色定理只能用于平面图 要证明一个图（不一定是平面图）的着色数是n，需要证明： 用n中颜色可以着色该图 用少于n中颜色不能着色该图 * G a b c d e f g 着色问题 例8.4.2 下面图G中的着色数是多少？ 由a, b, f组成的圈可以看出：G中的着色数不可能小于3 因此， ?(G) = 3 * G a b c d e f g 着色问题 例8.4.3