第四章-平面图与图的着色I

2026/8/514.1平面图定义4.1：若能把图G画在一个平面上，使任何两条边都不相交，就称G可嵌入平面，或称G是可平面图。可平面图在平面上的一个嵌入称为平面图。2026/8/52v1v4v2v3(a)4.1平面图e1e2e3e4e5e6v1v4v2v3(b)e1e2e3e4e5e6v1v4v3v2(c)e1e2e3e4e5e6可平面图平面图平面图2026/8/534.1平面图定义4.2：设G是一个平面图，由G的一个初级回路围成的一个区域内如果不含任何结点及边，就称为G的一个面或域。包含这个域的各边称为该域的边界。平面图G的外边的无限区域称为无限域或外部区域，其他的域叫内部域。2026/8/54v1v4v2v3(b)F1F2F3F44.1平面图e1e2e3e4e5e6F1=v1

e1v2e6

v4e4v1边界为：{e1

,e6

,e4}F2=v1

e5v3e3

v4e4v1边界为：{e5

,e3

,e4}F3=v1

e1v2e2

v3e5v1边界为：{e1

,e2

,e5}F4=v2

e2v3e3

v4e6v2边界为：{e2

,e3

,e6}2026/8/55v1v4v2v3(c)F1F2F3F44.1平面图e1e2e3e4e5e6F1=v1

e1v2e6

v4e4v1边界为：{e1

,e6

,e4}F2=v1

e5v3e3

v4e4v1边界为：{e5

,e3

,e4}F3=v2

e2v3e3

v4e6v2边界为：{e2

,e3

,e6}F4=v1

e1v2e2

v3e5v1边界为：{e1

,e2

,e5}2026/8/564.1平面图

如果两个域有共同的边界，则称它们是相邻的，否则是不相邻的。如果边e不是割边，则e一定是某两个域的共同边界。2026/8/574.1平面图e7v1v4v2v3F1F2F3F7e1e2e3e4e5e6v5v8v6v7F4F5F6e8e9e10e11e12e13F1=v1

e1v2e6

v4e4v1与F2=v1

e5v3e3

v4e4v1相邻共同边界为：e4，割边e7只是面F7的边界。2026/8/584.1平面图定理4.1设G是有n个结点和m条边的平面连通图，则G的面的数目d是

d＝m－n＋2（欧拉公式）证明：设连通图G的支撑树是T。T包含n－1条边，不包含回路，因此T只有一个无限域。2026/8/594.1平面图TF02026/8/5104.1平面图

由G是平面图，每加入一条余树的边e，它一定不与其他边相交，即e一定在某个域的内部，把该域分成两部分。2026/8/5114.1平面图TF0eF1F2eeF3F4F52026/8/5124.1平面图这样，加入G的m－n＋1条边，生成了m－n＋1个新的域。加上无限域，共有d＝m－n＋2个域。2026/8/5134.1平面图推论4.1有n个结点和m条边的平面图G有k个连通支，则n－m＋d＝k＋1。推论4.2对任一平面图G，恒有

n－m＋d

2。v1v4v2v3F1F2F3F7e1e2e3e4e5e6v5v8v6v7F4F5F6e7e8e9e10e11e122026/8/5144.1平面图定理4.2设有n个结点和m条边的平面连通图G没有割边，且每个域的边界数至少是t，则

m

t(n－2)t－2亦即t(n－2)t－2m

m－n＋22mt证明：设G

有d个域，每个域的边界数至少是t，且每条边都与两个不同的域相邻。因此td2m。代入欧拉公式：2026/8/5154.2极大平面图定义4.3：设G是有n

3个结点的简单平面图，若在任意两个不相邻的结点vi，vj之间加入边(vi，vj)，就会破坏图的平面性，则称G是极大平面图。极大平面图不是极大平面图2026/8/5164.2极大平面图v1v2v3v4v52026/8/5174.2极大平面图设有n个结点和m条边的极大平面图G具有以下性质：性质1.

G是连通的。性质2.

G不存在割边。性质3.

G的每个域的边界数都是3（极大平面图也称为平面三角剖分）。性质4.

3d=2m。2026/8/5184.2极大平面图性质3.G的每个域的边界数都是3。证明：由G是简单图，没有自环和重边，因此不存在边界数为1和2的域。假设G存在边界数大于3的域dj，不妨设dj是G的内部域，域dj的边界为：

dj=i1

e1

i2

e2

i3

e3

i4

e4i5…，这里结点i1,i2,i3,i4互不相同。e1i4dje2e3e4i1i2i3i52026/8/5194.2极大平面图性质3.G的每个域的边界数都是3。证明：若结点i1和i3

不相邻，则在域dj内加入边(i1,i3)后仍然是平面图，与G是极大平面图矛盾，因此边(i1,i3)

一定存在于域dj之外。e1i4dje2e3e4i1i2i3i5e1i4dje2e3e4i1i2i3i52026/8/5204.2极大平面图性质3.G的每个域的边界数都是3。证明：这时，在域dj之外不可能存在边(i2,i4)

。亦即i2和i4

不相邻，但在域dj内加入边(i2,i4)并不影响G的平面性，得到矛盾。e1i4dje2e3e4i1i2i3i52026/8/5214.2极大平面图性质4.3d=2m。证明：由性质2，每条边都是两个不同域的边界，再由性质3即得。2026/8/5224.2极大平面图定理4.2.1对有n个结点和m条边的极大平面图G，有

m＝3n－6，d＝2n－4证明：由极大平面图的性质4

3d=2m代入欧拉公式

d＝m－n＋2整理后即得。2026/8/5234.2极大平面图定理4.2.2简单平面图G中存在度小于6的结点。证明：设简单平面图G的每个结点的度都不小于6。由

d(vi)＝2m，得到6n

2m

因为G是简单平面图，又有3d

2m。代入欧拉公式的一般形式：n－m＋d

2

有

0=1/3m－m＋2/3m

2，得到矛盾。vi

V2026/8/5244.2极大平面图例4.2.27个结点的完全图K7不是平面图。证明：因为

7个结点的完全图K7的每个结点的度均为6。由定理4.2.2即得证。2026/8/5254.3非平面图如果对图G的任意一种平面嵌入，都至少存在两条边，它们在不是结点处相交，称G为非平面图。图平面图非平面图2026/8/5264.3非平面图如果图G不是简单图，可首先删去自环和重边，因为它们不影响图的平面性。因此只考虑简单图。考查在结点数固定情况下边数最少的非平面图。完全图K3

，K4是可平面图。任取一条边e，图K5

－e也是可平面图。2026/8/5274.3非平面图v1v4v2v3v1v2v3K3K4v1v2v3v4v5K5

－v3v5可平面图2026/8/5284.3非平面图定理4.3.1完全图K5是非平面图。证明：在完全图K5

中，n＝5，m＝10。如果K5是可平面图，应有m

3n－6。而对于K5

，3n－6＝9，得到矛盾。由此得到：K5是结点数最少的非平面图。2026/8/5294.3非平面图例4.3.1完全二分图K3,3中移去任一边后是可平面图。2026/8/5304.3非平面图定理4.3.2完全二分图K3,3是非平面图。K3,3是有6个结点的图中边数最少的非平面图。证明：假设K3,3是可平面图，由于n＝6，m＝9。由欧拉公式，d＝5。但K3,3中不含三角形。因此每个域的边界数至少是4，且每条边都与两个不同的域相邻。所以4d

2m，即20

18，得到矛盾。有6个结点的图中边数m<9的图均为平面图。2026/8/5314.3非平面图

K5和K3,3分别记为K(1)和K(2)。定义4.3.1：在图K(1)和K(2)

上任意增加一些度为2的结点之后得到的图称为K(1)型和K(2)型图，统称为K型图。2026/8/5324.3非平面图K型(K(1)型和K(2)

型)图均为非平面图。2026/8/5334.3非平面图定理4.3.3(库拉图斯基定理)：G是可平面图的充要条件是G不存在在K型子图。K(1)型子图K(2)型子图例4.3.2完全图K6既含有K(1)型子图，也含有K(2)型子图，所以是非平面图。如图：2026/8/5344.4图的平面性检验可平面性检验的预处理：1.如果G是非连通的，则分别检验每一个连通分支。当所有的连通分支都是可平面图时，G才是可平面图。v11v21B1B2B3v12v222026/8/5352.如果G中存在割点v，可把图G从割点处分离，构成若干个不含割点的连通子图，称为块。4.4图的平面性检验2026/8/536G是可平面图，当且仅当每个块是可平面图。4.4图的平面性检验v1v2v11v21B1B2B3v12v222026/8/5374.4图的平面性检验3.移去自环。v11B1v11B12026/8/5384.4图的平面性检验4.移去度为2的结点vi及其所关联的边，同时在vi的两个邻结点vj,vk之间加入边(vj,vk)。v11B1B1原图是可平面图，当且仅当新图是可平面图。2026/8/5394.4图的平面性检验5.移去重边。B1B12026/8/5404.4图的平面性检验反复运用4和5。最后，如果

a.m<9或n<5,则G是可平面图。

b.m>3n-6，则G是非平面的。

c.不满足a和b，需要进一步检查。2026/8/5414.4图的平面性检验例4.4.1判断下图的可平面性。v1v2G由判定规则2，G有两个割点v1和v2

；可分成3个块。2026/8/5424.4图的平面性检验v11B1对块B2，n<5，所以块B2是平面图。v21B2v12B3v22由判定规则4处理块B1和B3

，得到如下的图。2026/8/5434.4图的平面性检验B1B3v22由判定规则5

，得到如下的图。B1B3v22对块B3，m<9，所以块B3是平面图。2026/8/5444.4图的平面性检验由判定规则4处理块B1，得到如下的图。B1由判定规则5

，得到如下的图。B1对块B1，n<5，所以块B1是平面图。2026/8/5454.4图的平面性检验例4.4.1判断下图的可平面性。v1v2G所以图G是可平面图。2026/8/5464.4图的平面性检验图G的平面嵌入如下：v1v2G2026/8/5474.4对偶图给定一个平面图G定义4.5.1满足下列条件的图G*

称为G

的对偶图。

1.在G中每个域Fi

内设置一个结点vi*。

2.对域Fi和Fj的共同边界ek，有一条边

ek*＝(vi*,vj*)

E(G*)，并且与ek相交一次。

3.若边ek位于域Fi之内，则vi*有一自环ek*与ek相交一次。2026/8/5484.4对偶图v1v2v3v4v5v4*v1*v2*v3*F1F2F3F4图G

的对偶图G*

：e1*e1e2e7*e4e2*e3*e3e4*e5e5*e6e6*e72026/8/5494.4对偶图v4*v1*v2*v3*图G

的对偶图G*

：e1*e7*e2*e3*e4*e5*e6*2026/8/550

F1

F2

F4

F5

v3v4e1e2e3e4e5

F0

v1v2v54.4对偶图求图G

的对偶图G*

：2026/8/551v2*4.4对偶图

F0

F1

F2

F3

F4

F5

v1*v0*v3*v4*v5*v1v2v3v4v5e1e1*e2e3e4e5e2*e3*e4*e5*图G

的对偶图G*2026/8/552v2*4.4对偶图v1*v0*v3*v4*v5*e1*e2*e3*e4*e5*图G

的对偶图G*2026/8/5534.4对偶图v1v2v3v4v5v6v1*v2*v3*求图G

的对偶图G*

：2026/8/5544.4对偶图v1*v2*v3*求图G

的对偶图G*

：2026/8/5554.4对偶图性质4.5.1如果G是平面图，G一定有对偶图G*

，而且G的对偶图G*是唯一的。性质4.5.2G*

是连通的。性质4.5.3若G是平面连通图，则(G*)*

＝G。性质4.5.4平面连通图G与其对偶图G*

的结点、边和域之间存在如下对应关系：m*

＝m

，n*

＝d

，d*

＝n2026/8/5564.4对偶图v1v2v3v4v5v4*v1*v2*v3*2026/8/5574.4对偶图v1v2v3v4v5v6v1*v2*v3*2026/8/5584.4对偶图性质4.5.5设C

是平面图G的一个初级回路，S*是G*中与C的各边ei对应的边ei*的集合，则S*是G*的一个割集。证明：C把G的域分成了两部分，因此E(G*)－S*把G*的结点分成不连通的两部分。由G*是连通图，G*被分开的两部分都是连通的，因此S*是G*的一个割集。2026/8/5594.4对偶图v1v2v3v4v5v4*v1*v2*v3*C＝v1v2v32026/8/5604.4对偶图v4*v1*v2*v3*C＝v1v2v3S*＝{v2*v3*,v2*v3*,

v2*v4*,}2026/8/5614.4对偶图例4.5.3设i

和j

是平面连通图无限域边界上的两个结点，求G中分离i

和

j的所有割集。ij解：在G的无限域中添入边(i,j),

得到图G1。GG1作G1的对偶图G1*。2026/8/5624.4对偶图则G1*中除边(i

,j

)之外的从i

到j

的初级道路所对应的G的诸边都构成G中分离i

和j的割集。iji

j

例4.5.3设i

和j

是平面连通图无限域边界上的两个结点，求G中分离i

和

j的所有割集。ij解：在G的无限域中添入边(i,j),

得到图G1。作G1的对偶图G1*。2026/8/5634.4对偶图例4.5.3设i

和j

是平面连通图无限域边界上的两个结点，求G中分离

i

和

j的所有割集。解：在G的无限域中添入边(i,j),

得到图G1。作G1的对偶图G1*。则G1*中除边(i

,j

)之外的从i

到j

的初级道路所对应的G的诸边都构成了G中分离i

和

j的割集。i

j

ij2026/8/5644.4对偶图四色猜想－四色问题任何一张地图都可以最多用四种颜色着色，使得具有共同边界的国家染上不同的颜色。简称为地图是4－可着色的。

这里具有共同边界是指有一整段共同边界。2026/8/5654.4对偶图四色猜想来自英国,1852年由格里斯兄弟提出,1872年由数学家凯利正式向倫敦数学学会提出,从而成为世界数学难题。1976年6月哈肯和阿佩尔在美国伊利诺斯大学用两台不同的电子计算机，花了1200个小时，作了100亿次判断，完成了四色定理的证明。2026/8/5664.4对偶图用1，2，3，4代表四种染色111222342026/8/5674.4对偶图一张地图可看成是一个平面图G。作G的对偶图G*111222232026/8/5684.4对偶图对平面图地图G的域的着色可看成是G的对偶图G*的结点的着色。111222232026/8/5694.4对偶图－5色定理定理4.5.2每一个平面图G的结点是5－可着色的。证明：由于自环和重边不影响结点染色。所以可移去G中的自环和重边，得到简单平面图G0。2026/8/5704.4对偶图－5色定理定理4.5.2每一个平面图G的结点是5－可着色的。证明：对G0的结点数用归纳法证明。当结点数n

5时，结论显然成立；设当简单平面图G0

的结点数是n－1时结论成立。现设G0是有n个结点的简单平面图。由定理4.2.2，G0中存在结点v，d(v)<6。在G0中移去结点v后得到的图是G0

，即G0

＝G0－v。由归纳假设，G0

的结点是可5－可着色的。

2026/8/5714.4对偶图－5色定理定理4.5.2每一个平面图G的结点是5－可着色的。证明：对G0

的结点着好色之后，再把结点v放回到G0中。由于G0是平面图，结点v

一定在G0

的某个域内。若d(v)

4，或者d(v)＝5，同时v

的邻点没有用完5种颜色，再將G0

的结点着色中邻接于v

的结点所未用的顏色给结点v

即可得G0的结点5-着色。2026/8/5724.5对偶图vv2026/8/5732026/8/5744.4对偶图－5色定理定理4.5.2每一个平面图G的结点是5－可着色的。证明：如果G0中，结点v的邻点恰好用了5种颜色，比如1,2,3,4,5。2026/8/5752026/8/5764.4对偶图－5色定理定理4.5.2每一个平面图G的结点是5－可着色的。证明：设在G0

的着色中，G0中与结点v邻接的着颜色i

的结点记为vi。设G13是G0

＝G0－v的由着颜色1和3的结点导出的子图。2026/8/5772026/8/5784.4对偶图－5色定理定理4.5.2每一个平面图G的结点是5－可着色的。证明：若v1和v3分别属于G13的不同连通支，则将v1所在的连通支的各结点着的颜色1和3对换。对换后，在G0

的结点5－着色中，G0

的结点v

的邻点没有用到颜色1

，所以在G0中可用颜色1

给结点v着色，得G0的结点5-着色。2026/8/5794.4对偶图－5色定理定理4.5.2每一个平面图G的结点是5－可着色的。证明：如果v1和v3属于G13的同一个连通支，则存在由v1到v3

的、结点交替着颜色1和3的道路P。在G0中P＋(v,v1)＋(v,v3)构成一个回路C。C把v2与v4

、v5分隔在不同的区域。因此，在G0中不存在由v2到v4

的、结点交替着颜色2和4的道路。2026/8/5804.5对偶图2026/8/5814.4对偶图－5色定理定理4.5.2每一个平面图G的结点是5－可着色的。证明：在G0

＝G0－v的由着颜色2和4的结点导出的子图G24

中，v2和v4分别属于G24的不同连通支。则将v2所在的连通支的各结点着的颜色2和4对换。对换后，在G0

的结点5－着色中，G0

的结点v

的邻点没有用到颜色2

，所以在G0中可用颜色2

给结点v着色，得G0的结点5-着色。2026/8/5824.2极大平面图推论4.2.1设有n个结点和m条边的任意简单平面图G满足m

3n－6，d

2n－4证明：设G的域的边界数分别为E1,E2,…,Ed，由G中没有自环和重边，所以Ei

3，1i

d。如果G中没有割边，则

E1＋E2＋…＋Ed＝2m，若G有割边，则E1＋E2＋…＋Ed

2m。总之有2m

E1＋E2＋…＋Ed3d。代入欧拉公式即得。2026/8/5834.4图的平面性检验设H是G的可平面子图，如果在G－H中存在另一个G的平面子图B，且B与H有2个以上共同结点，则称B是G中H的片，片B与H的公共结点称为片B的附着点。2026/8/5844.4图的平面性检验例4.4.2在图G中，令H是回路(v1,v2,v3,v4)，则H是G的可平面子图。v1v2v3v4v5G2026/8/585

4.4图的平面性检验在图G中，H＝(v1,v2,v3,v4)有三个片：B1＝{(v2,v4)}，附着点是v2,v4

；B2＝{(v1,v3)}，附着点是v1,v3

；B3＝{(v1,v5),(v2,v5),(v3,v5),(v4,v5)}，附着点是v1,v2,v3,v4

；v1v2v3v4v4v1v2v3v1v2v3v4v5B1B2B32026/8/5864.4图的平面性检验可平面子图H的片2026/8/5874.4图的平面性检验命题：设H是图G的一个可平面子图，H是子图H的一个平面嵌入，令B是G中H的片。则只有当片B的所有附着点都在H

的某个面

f

的边界上时，片B才能画在H

的一个面内。～～～v1v2v3v4v4v1v2v3v1v2v3v4v5B1B2B32026/8/5884.4图的平面性检验设H是例4.4.2的子图H的一个平面嵌入。片B1＝{(v2,v4)}

画在H

的内部面上，得到的子图是H1，H1的平面嵌入是H1

。～～～v4v1v2v3B1H1～2026/8/5894.4图的平面性检验此时，片B2

的所有附着点都位于

H1

的外部面的边界上。把B2画在H1

的外部面上得到子图H2。H2的平面嵌入是H2。～～～v4v1