离散第23讲 平面图的着色与树ppt课件.ppt

《离散第23讲 平面图的着色与树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程PowerPointTemplate_Sub1二分图2平面图3树2第23讲平面图的着色与树平面图的着色与树《离散数学》第23讲Page140to1471852年，格思里(FrancisGuthrie)注意到美国地图可以用4种颜色染色,使得相邻区域(有一段公共边界,不只是有一个公共点)有不同颜色;提出四色猜想4第23讲平面图的着色与树1878年，德.莫尔根(De.Morgan)凯莱(Cayley)把它提到伦敦数学学会上，“四色猜想”公诸于世，引起了各国数学界的注意和兴趣。1879年，开姆玻(Kempe)发表了第一个“证明”

2、1890年，希伍德(Heawood)发现了开姆玻的一个推理错误，对其证明加以修改，提出并证明了“五色定理”5第23讲平面图的着色与树1969年，奥尔(Ore)和斯坦普尔(Stemple)对少于40个国家的所有地图，证明了“四色猜想”的正确性。然而对任意多个国家，“四色猜想”的正确性仍然没有证明出来。1976年，美国数学家阿佩尔(K.Appel)和黑肯(W.Hakan)首次应用计算机证明了这一难题，使“四色猜想”成为“四色定理”。他们从1976年1月至6月在三部计算机上用了1200小时，作了近百亿次逻辑判断才得出结果，证明的正确性如果不借助

3、计算机也无法检验。至今还没有找到能用“纸和笔”给出的证明。但人们已经知道沿着上述方向是不可能使证明得到实质性的简化。6第23讲平面图的着色与树着色问题图的点着色平面图的面着色7第23讲平面图的着色与树平面图的面着色问题四色难题：是否任何平面图均可以4着色？容易证明：任何平面图均可以5着色。为便于研究，先把面着色转化为点着色任一平面图都有一个对偶图，平面图的面和它的对偶图的结点有着一一对应的关系，所以对平面图面的着色，可归化为对其对偶图点的着色，显然研究平面图点的着色要比研究图的着色更为方便。所以对地图面的着色都是归化为点的着色进行研究的。

4、8第23讲平面图的着色与树对偶图对连通平面图G实施下列步骤所得到的图G*称为G的对偶图(dualofgraph)：(1)在G的每一个面ri的内部作一个G*的顶点vi*。(2)若G中面ri与rj有公共边界，那么过边界的每一边ek作关联vi*与vj*的一条边ek*。ek*与G*的其它边不相交。(3)当ek为面ri的边界而非ri与其它面的公共边界时，作vi*的一条环与ek相交(且仅交于一处)。所作的环不与G*的边相交。9第23讲平面图的着色与树r3对偶图例2(3)当ek为面ri的边界而非ri与其它面的公共边界时，作vi*的一条环与ek相交(且仅

5、交于一处)。所作的环不与G*的边相交。(1)在G的每一个面ri的内部作一个G*的顶点vi*。(2)若G中面ri与rj有公共边界，那么过边界的每一边ek作关联vi*与vj*的一条边ek*。ek*与G*的其它边不相交。r1r2bdecav2v3v110第23讲平面图的着色与树对偶图例1(3)当ek为面ri的边界而非ri与其它面的公共边界时，作vi*的一条环与ek相交(且仅交于一处)。所作的环不与G*的边相交。(1)在G的每一个面ri的内部作一个G*的顶点vi*。(2)若G中面ri与rj有公共边界，那么过边界的每一边ek作关联vi*与vj*的一

6、条边ek*。ek*与G*的其它边不相交。11第23讲平面图的着色与树对偶图例同构图的对偶图可能不同构左边的对偶图有5度顶点,右边的对偶图却没有平面图的对偶图仍为平面图bdecafbdecaf25361425361425361412第23讲平面图的着色与树可k着色定义:无环图G称为可k-着色的，如果可用k种颜色给G的所有顶点着色，使每个顶点着一种颜色，而同一边的两个端点着不同颜色。若任意平面图可k-着色，则任意平面图的面可用k种颜色之一着色，使得相邻的面着不同颜色13第23讲平面图的着色与树5色定理定理:任何平面图都是可5-着色的。证：连通

7、分支、环和平行边与着色问题无关，因此可只讨论平面连通简单图。设G为任一平面连通简单图，顶点个数为n。对n归纳。当n≤5时命题显然成立。设n-1个顶点的平面图都是可5-着色的。考虑n个顶点的图G。由定理8.9顶点数n不少于4的平面连通简单图G，至少有一个顶点的度数不大于5。可知G至少有一个顶点的度不大于5，设v0为这样一个顶点。14第23讲平面图的着色与树5色定理将v0及与它关联的边中删去，得图G0=G-{v0}有n-1个结点，根据假设前论G0是5可着色的。现在将v0及原来与它关联的边仍加到G0上，图又恢复为n个结点的图G，这时有两种可能：

8、1）设d(v0)<5，那么只要取它相邻顶点所着颜色（至多4种)之外的一种颜色给v0着色，便可完成对G的5-着色。2）设d(v0)=5，如果证明与v0相邻的顶点可用少于五种颜色着色，便可完成对G