对于给定的平面图G

1、 ()刘晓华刘晓华4.5 对偶图对偶图 1. 定义定义: 对于给定的平面图对于给定的平面图G，作相应，作相应的一个图的一个图G：在：在G的每个域内设置的每个域内设置G的一的一个结点；对个结点；对G中每条边中每条边e作作G相应的一条相应的一条边边e，联结以，联结以e为边界的为边界的G的两域中的两域中G的两的两个结点。这样得到的个结点。这样得到的G，称为，称为G的的对偶图对偶图。 对偶图的意义对偶图的意义在于，关于在于，关于域域的问题可以的问题可以转换成关于转换成关于结点结点的问题。的问题。注意：简单平面图的对偶图是平面图，注意：简单平面图的对偶图是平面图，但不一定是简单图（可能含重边或环）。但不

2、一定是简单图（可能含重边或环）。对偶图点数对偶图点数= =原图的域数原图的域数对偶图边数对偶图边数= =原图边数原图边数例求下列图的对偶图。例求下列图的对偶图。14253abcd14253abcd 2. 对偶图的性质对偶图的性质 1) 若若G是平面图，则其对偶图是平面图，则其对偶图G*是唯一的。是唯一的。 2) 平面图平面图G的对偶图的对偶图G*是连通的。是连通的。 3) 若若G是平面图，则是平面图，则(G*)*=G。 4) G*结点数结点数= G域数，域数， G*边数边数= G边数边数 G*域数域数= G结点数。结点数。证证：2) 因为因为G的所有域之间都是相互邻接的。的所有域之间都是相互邻

3、接的。 3)由对偶图的作图过程知，由对偶图的作图过程知，G与与G的结点与的结点与域相互对应。域相互对应。 4)由对偶图的作图过程知。由对偶图的作图过程知。6) G有对偶图充要条件有对偶图充要条件G是平面图。是平面图。 5) 若若C是平面图是平面图G的初级回路，的初级回路，S*是是G*中与中与C的各边的各边ei 对应对应的的ei*的集合，那么的集合，那么S*是是G*的一的一个割集。个割集。(C为蓝圈，为蓝圈，S*为红边的集合为红边的集合)证证：C将将G*的所有结点分为内外两部分的所有结点分为内外两部分N1,N2, 则则S*即是即是N1,N2间的割集。间的割集。 例例 下图是一所房子的俯视图，设每

4、一面墙下图是一所房子的俯视图，设每一面墙都有一个门。问都有一个门。问: 能否从某个房间开始过每扇能否从某个房间开始过每扇门一次最后返回。门一次最后返回。 作原图的对偶图作原图的对偶图(红图红图)。问题相当于问，其对。问题相当于问，其对偶图中是否存在偶图中是否存在Euler回路。由于图中有结点度数回路。由于图中有结点度数为奇，故不存在为奇，故不存在Euler回路。回路。 例例 对平面连通图对平面连通图G的无限域边界上的任意的无限域边界上的任意两结点两结点i和和j，求，求G中分离中分离i和和j的所有割集。的所有割集。ijab 根据性质根据性质5，只需找出经过，只需找出经过a,b的全部这样的回路的全

5、部这样的回路i在回路内、在回路内、j在回路外在回路外a到到b的红色道路加上绿色虚的红色道路加上绿色虚线边所成回路，这用线边所成回路，这用G的对偶图可得。的对偶图可得。a到到b的红色道的红色道路有多少条，符合要求的割集就有多少个。路有多少条，符合要求的割集就有多少个。 3. 对偶图的应用对偶图的应用 定理定理 每一个平面图每一个平面图G都是都是5 -可着色的。可着色的。 证明的思路是作证明的思路是作G的对偶图，使问题转化为一的对偶图，使问题转化为一个平面图的点着色问题个平面图的点着色问题(相邻点不同色相邻点不同色)。因为环。因为环和重边不影响点的着色，故可去掉环和重边，这和重边不影响点的着色，故

6、可去掉环和重边，这样只需要证明一个简单平面图的点样只需要证明一个简单平面图的点5 -可着色即可。可着色即可。可用数学归纳法证之，具体证明过程略。可用数学归纳法证之，具体证明过程略。 经验表明，一张实际的彩色地图使用四种不同颜色即经验表明，一张实际的彩色地图使用四种不同颜色即可区别相邻国家的疆域。可区别相邻国家的疆域。“四色猜想四色猜想”断言，对于任何断言，对于任何一个平面图一个平面图 (地图地图)这个结论成立。这个结论成立。 四色猜想已由美国数学家阿佩尔与黑肯四色猜想已由美国数学家阿佩尔与黑肯(1976年年)用计用计算机程序证明，但尚未找到数学方法给予简练证明。算机程序证明，但尚未找到数学方法

7、给予简练证明。4.6 色数与色数多项式色数与色数多项式 上节表明，域的着色问题可以转化为点上节表明，域的着色问题可以转化为点的着色问题。还有一些实际问题，也需要的着色问题。还有一些实际问题，也需要解决点或边的着色问题。解决点或边的着色问题。 例例：有：有6种货物需堆放到仓库中。若某两种货物需堆放到仓库中。若某两种货不能存放同一个仓库中，则彼此用一种货不能存放同一个仓库中，则彼此用一条线相连条线相连(见下图见下图)。问最少需要多少个仓库。问最少需要多少个仓库。 132123 1. 定义定义1 给图给图G的的结点结点着色着色(相邻结点不同色相邻结点不同色)，所需的最少颜色数称为所需的最少颜色数称为

8、色数色数，记作，记作 (G)。 定义定义2 给图给图G的的边边着色着色(相邻边不同色相邻边不同色)，所需，所需的最少颜色数称为的最少颜色数称为边色数边色数，记作，记作 (G)。 边着色问题可以转化为点着色问题，边着色问题可以转化为点着色问题，具体方具体方法如下。法如下。 根据原图根据原图G作一个相应的图作一个相应的图G：在：在G的每条的每条边上作边上作G的一个结点；如果的一个结点；如果G的两条边相邻，的两条边相邻，则将此二边上的则将此二边上的G的结点用边相联。的结点用边相联。 这样，这样，G的边着色问题即为的边着色问题即为G的点着色问的点着色问题。题。 例例 欲边着色的图欲边着色的图G与等价的

9、点着色的图与等价的点着色的图G. 2. 常见图的色数常见图的色数 1)* (Kn) = n ; 2) (Kn- e) = n-1 ; 3) G为空图时为空图时 (G) = 1 ; 4) G为二分图时为二分图时 (G) = 2 ; 5)* G恰为一个偶数个结点的回路时恰为一个偶数个结点的回路时 (G) = 2 ; 6)* G恰为一个奇数个结点的回路时恰为一个奇数个结点的回路时 (G) = 3 ; 7)* G为结点数大于为结点数大于1 的一棵树时的一棵树时 (G) = 2 ;证证: 1)因为任意两点间有边相联因为任意两点间有边相联, 故每点着色互异。故每点着色互异。 2)让让e的两端点同色，其余各

10、结点异色。的两端点同色，其余各结点异色。 3)因为空图有点无边。因为空图有点无边。 4)仅两结点集间有边相联，故一个结点集用仅两结点集间有边相联，故一个结点集用一种色即可。一种色即可。 5) 依顺时针方向，对结点用红绿两色交替着色。依顺时针方向，对结点用红绿两色交替着色。 6)依顺时针方向，对结点用红绿两色交替着色，依顺时针方向，对结点用红绿两色交替着色，最后结点用黄色。最后结点用黄色。(用两色不可能，用三色能实现用两色不可能，用三色能实现) 偶数个结点的回路偶数个结点的回路奇数个结点的回路奇数个结点的回路 7) 根结点着红色。以后只使用绿红两色，对根结点着红色。以后只使用绿红两色，对于每个已

11、着色的结点于每个已着色的结点v，让其相邻的未着色结点，让其相邻的未着色结点染色与染色与v不同即可。不同即可。 3. 2-着色的充要条件着色的充要条件 定理定理 若若G为非空图为非空图, 则则 (G)=2 G不含奇回路。不含奇回路。 证证:1) 充分性充分性. 对于对于G的每个连通分支确定其一个支撑树，的每个连通分支确定其一个支撑树，这些支撑树构成了这些支撑树构成了G的一个林的一个林T。因为其中每棵。因为其中每棵树都只需两种色为结点着色树都只需两种色为结点着色, 故故 (T)=2. 依次加入依次加入T以外的以外的G的边，所得回路都是偶的边，所得回路都是偶回路，故不影响已着的色回路，故不影响已着的

12、色(相邻结点色不同相邻结点色不同)，即，即 (G)=2 。 2) 必要性必要性. 若若G含有某个奇回路含有某个奇回路C，则，则 (C)=3。 于是，于是， (T) (C)=3，矛盾。，矛盾。 定理定理 平面连通图平面连通图G的域可的域可2-着色着色 G中存在欧中存在欧拉回路。拉回路。 证证: 因为因为G是平面图是平面图, 故其对偶图故其对偶图G*存在。于是，存在。于是，命题即为命题即为“G*可点可点2-着色着色 G中存在欧拉回中存在欧拉回路路”。 1) 必要性必要性. 由上一定理，由上一定理，G的每个结点的度均的每个结点的度均为偶数为偶数(否则此结点的否则此结点的G*的回路为奇回路的回路为奇回

13、路)。于是，。于是，G中存在欧拉回路。中存在欧拉回路。 2) 充分性充分性. 因为因为G中每个结点中每个结点vi的度都是偶数，的度都是偶数，故故G*中围绕中围绕vi的回路是偶回路。的回路是偶回路。 下面证明下面证明G*中任何回路中任何回路C必为偶回路，从而必为偶回路，从而应用上一定理即知应用上一定理即知G*可点可点2-着色着色 。 对对G*中回路中回路Ok中所含的中所含的G的结点数的结点数k作归纳作归纳法。当法。当k=1时，刚才已说明时，刚才已说明O1为偶回路。为偶回路。 设设Ok为偶回路。对于为偶回路。对于k+1情形：情形：OkO1Ok+1Ok+1= Ok O1 在在Ok+1所围所围G结点中

14、选定一结点中选定一(红红)点，使其关点，使其关联的边与联的边与G*中回路中回路Ok+1相交。于是有分解相交。于是有分解Ok+1 = Ok O1。根据归纳假设。根据归纳假设Ok与与O1均为偶回路均为偶回路, 而而两个偶回路的对称差仍为偶回路两个偶回路的对称差仍为偶回路(边数边数=两回路总两回路总边数减去二倍公共边数边数减去二倍公共边数)，即知，即知Ok+1为偶回路为偶回路。 4. 色数的上界估计色数的上界估计 定理定理 对于图对于图G, 设设G的结点最大度数为的结点最大度数为d0, 则有则有 (G) d0 +1. 证证: 对结点数对结点数k作归纳法。作归纳法。k=1时显然成立，设时显然成立，设k

15、时命题成立。当结点数为时命题成立。当结点数为k+1时，设时，设v为为G中一中一结点。考虑结点。考虑G=G-v，记，记d1为为G的结点最大度数的结点最大度数，则，则d1 d0 . 据归纳假设，据归纳假设， (G) d1 +1 d0 +1，即可用，即可用d0 +1种颜色为种颜色为G的结点着色的结点着色. 对对G的结点着色后将的结点着色后将v放回，恢复成放回，恢复成G。因为。因为d(v) d0 ,故与故与v相邻的结点中至少还有一种颜色相邻的结点中至少还有一种颜色未用到，可用来给未用到，可用来给v着色。证毕。着色。证毕。定理定理 对于任意一个图对于任意一个图G, 有有 (G) max (G)+1，G是

16、是G的导出子图的导出子图, (G)是是G的结点的最小度的结点的最小度.5. 色数色数 (G)的计算方法的计算方法 1) 对于图对于图G中任意两个中任意两个不相邻不相邻的结点的结点i,j, 记记所所得得之之图图。一一条条相相重重边边只只保保留留合合并并为为一一个个结结点点两两结结点点的的为为将将所所得得之之图图添添上上边边为为)(,),(jiGGjiGGijij ijGijijGvijijG 2) (G)的计算方法的计算方法 定理定理 设设i,j 是简单图是简单图G不相邻的两个结点，则不相邻的两个结点，则 证明证明: 对对G中结点的任何着色中结点的任何着色, i 和和j或者将着以或者将着以同色同

17、色,或者着异色或者着异色,二者必居其一二者必居其一.).(),ijijGG(min(G) ).(,);,ijijGGjiG着着色色数数为为的的最最少少着着色色为为同同色色的的情情况况下下在在的的最最少少着着色色数数为为着着异异色色的的情情况况下下在在(Gji, 因此，命题中等式成立。因此，命题中等式成立。应用此递推式，将应用此递推式，将G逐级分解，最后得到可立即确定逐级分解，最后得到可立即确定其色数的若干图其色数的若干图(常为大小不一的若干完全图常为大小不一的若干完全图)，其中，其中最最小小的色数，即为的色数，即为G的色数。的色数。 例例 试确定下图的色数。试确定下图的色数。故故 (G)=mi

18、n (K5), (K4), (K3)=3.vijvijvijvij返回3)色数多项式色数多项式 给定图给定图G,如果最多使用如果最多使用t 种颜色对它的结点进行着色种颜色对它的结点进行着色,满足相邻结点着以不同颜色满足相邻结点着以不同颜色,其着色的不同方案数用其着色的不同方案数用f(G,t)表示。称表示。称f(G,t)为为G的的色数多项式色数多项式。 显然，当显然，当t 0的最少颜色的最少颜色数数t= (G). 对平面图对平面图G: 五色定理五色定理断言断言 f(G,5)0， 四色定理四色定理断言断言 f(G,4)0。特殊图的色数多项式特殊图的色数多项式 定理定理 (1) f(Kn,t)=t(

19、t-1)(t-n+1) (t n) (2) f(Tn,t)=t(t-1)n-1 (Tn为为n个结点的树个结点的树)证证: (2)先对根结点着色，有先对根结点着色，有t 种颜色选择。对于每个已着种颜色选择。对于每个已着色的结点，其相邻的每个结点均有色的结点，其相邻的每个结点均有t-1种颜色可选择。种颜色可选择。 一般图色数多项式的计算一般图色数多项式的计算 定理定理 设设i,j是是G的不相邻结点的不相邻结点,则有则有).,(),tGftGffijij (t)(G, 证明证明: 对对G中结点的任何着色中结点的任何着色, i 和和j或者将着以或者将着以同色同色,或者着异色或者着异色,二者必居其一二者必居其一.).(,);,iji