1、7-6 对偶图与着色掌握对偶图的定义，会画图 G的对偶图 G*掌握自对偶图的定义及必要条件。n 与平面图有密切关系的一个图论的应用是图形的着色问题，这个问题最早起源于地图的着色，一个地图中相邻国家着以不同颜色，那么最少需用多少种颜色？n 一百多年前，英国格色里 (Guthrie)提出了用四种颜色即可对地图着色的猜想， 1879年肯普 (Kempe)给出了这个猜想的第一个证明，但到 1890年希伍德(Hewood)发现肯普证明是错误的，但他指出肯普的方法 虽不能证明地图着色用四种颜色就够了，但可证明用五种颜色就够了，即五色定理成立。n 此后四色猜想一直成为数学家感兴趣而未能解决的难题。n 直到
2、1976年美国数学家阿佩尔和黑肯宣布：他们用电子计算机证明了四色猜想是成立的。所以从 1976年以后就把四色猜想这个名词改成 “四色定理 ”了。n 为了叙述图形着色的有关定理，下面先介绍对偶图的概念。一、对偶图1、对偶图定义定义 7-6.1 对具有面 F1 ,F2,., Fn的连通平面图G=实施下列步骤所得到的图 G*称为图 G的 对偶图 （ dual of graph）：如果存在一个图 G*=满足下述条件：（ a）在 G的每一个面 Fi的内部作一个 G*的顶点 vi* 。即 对图 G的任一个面 Fi内部有且仅有一个结点 vi* V*。(b)若 G的面 Fi， Fj有公共边 ek， 则作 ek
3、*=(vi*， vj*)，且ek*与 ek相交。即若 G中面 Fi与 Fj有公共边界 ek ， 那么过边界的每一边 ek作关联 vi*与 vj*的一条边 ek* =(vi*, vj*) 。 ek*与 G*的其它边不相交。(c)当且仅当 ek只是一个面 Fi的边界时 (割边 )， vi*存在一个环 e*k与 ek相交。即当 ek为单一面 Fi的边界而不是与其它面的公共边界时，作 vi*的一条环与 ek相交（且仅交于一处）。所作的环不与 G*的边相交。则称图 G*为 G的对偶图。实线边图为平面图，虚线边图为其对偶图。v*=r， e*=e， r*=v2、自对偶图定义定义 7-6.2 如果图 G的对偶图 G*同构于 G,则称 G是自对偶图。二、图的着色1、问题的提出n 该问题起源于地图的着色问题。n 图着色的三种情况 :n 对点着色 是对图 G的每个结点指定一种颜色，使得相邻结点的颜色不同 ;n 对边着色 给每条边指定一种颜色使得相邻的边的颜色不同，n 给面着色 给每个面指定一种颜色使得有公共边的两个面有不同的颜色。n 对边着色和对面着色均可转化为对结点着色问题。
