图论第6章-平面图课件

第六章平面图与着色平面图

一个图G能画在平面上，除顶点之外，再没有边与边相交，则称G为平面图。画出的没有边交叉的图称为G的一个平面嵌入或G的一个平面。在下图中(2)是(1)(K4)的平面嵌入,所以(1)是平面图,单独看(2)也是平面图,对于(3)(K5)无论怎样画法,也去不掉交叉边,所以不是平面图。(1)(2)(3)(4)

设G是一个连通的平面图,G的边将G所在的平面划分成若干个区域,每个区域称为G的一个面。其中面积无限的区域称为无限面或外部面,常记为R0,面积有限的区域称为有限面或内部面。包围每个面的所有边所构成的回路称为该面的边界,边界的长度称为该面的次数,R次数记为deg(R)。对于非连通的平面图G可以类似地定义它的面、边界及次数。v1v2v3v4v5v6R0R1R2例：下图为连通的平面图,共有3个面R0,R1,R2。R1的边界为初级回路v1v3v4v1,deg(R1)=3。R2的边界为初级回路v1v2v3v1,deg(R2)=3。R0无限面,它的边界为复杂回路v1v4v5v6v5v4v3v2v1,deg(R0)=8。v1v2v3v4v5v6v7R1R0R2又例：下图为非连通的平面图，有两个连通分支，deg(R1)=3，deg(R2)=4，R0的边界由两个初级回路v1v2v3v1和v4v5v6v7v4围成，deg(R0)=7。

定理：设G=V,E是有限平面图，有r个面，则所有面的次数之和等于边数的2倍。即

=2|E|。

证明：G的任何一边，或者是两个面的公共边界，为每一个面的次数增加1；或者在一个面中作为边界重复计算两次，为该面的次数增加2。无论那种情况G的任何一边为图中面的次数和增加2，故所有面的次数之和等于边数的2倍。

设G为一个平面图,如果在G中任意不相邻的两个顶点之间再加一条边,所得图为非平面图,则称G为极大平面图。GG'不是平面图关于极大平面图有以下的几个结论：①极大平面图是连通图。②结点数大于等于3的极大平面图不可能存在割点和桥。③设G为结点数大于等于3的简单连通平面图,G为极大平面图当且仅当G的每个面的次数均为3。

在非平面图G中任意删除一条边，所得图为平面图,则称G为极小非平面图。例：GG'

定理(欧拉公式)：任意连通平面图G，若有n个结点，m条边和r个面，则欧拉公式n-m+r=2成立。

证明：对边数m归纳证明。⑴设m=0，由于G是连通图，所以G只能是平凡图。这时，n=1，m=0，r=1，n-m+r=2成立。⑵设m=k(k≥1)时欧拉公式成立，下证当m=k+1时，欧拉公式也成立。

若G是树，则G是非平凡树，则G中至少有两片树叶。设v为其中一片树叶。令G′=G-v(从G中删除结点v，而得到G′)，则G′仍然是连通图。设n′、m′和r′分别是G′的结点数、边数和面数。则n′=n-1，m′=m-1=k，r′=r。于是n=n′+1，m=m′+1，r=r′。因为G′是连通图且m′=k，所以G′满足归纳假设的条件。由归纳假设知：n′-m′+r′=2，所以

n–m+r=(n′+1)–(m′+1)+r′=n′-m′+r′=2。

若G不是树，则G中含有回路。设边e在G的某个回路上。令G′=G-e(从G中删除边e，而得到G′)，则G′仍然是连通图。设n′，m′和r′分别是的结点数、边数和面数。则n′=n，m′=m-1=k，r′=r–1。于是n=n′，m=m′+1，r=r′+1。因为G′是连通图且m′=k，所以G′满足归纳假设的条件。由归纳假设知：n′–m′＋r′=2，所以

n–m+r=n′–(m′+1)+(r′+1)=n′-m′+r′=2。

欧拉公式成立是平面图的重要性质，条件是平面图的连通性。欧拉公式还可以推广到非连通的平面图中。定理：设G是平面图，有k个连通分支，n个结点，m条边，r个面，则公式n-m+r=k+1成立。

证明：设G的连通分支为Gi，ni、mi和ri分别是Gi的结点数、边数和面数，ni-mi+ri=2，i=1,…,k。而=m，=n，由于每一个Gi有一个外部面，而G只有一个外部面，所以G的面数r=-k+1，即=r+k-1。所以2k===–＋=n-m+r+k-1

整理后有n-m+r=k+1。定理：设G是连通的平面图，且每个面的次数至少为l(l≥3），则

其中,n为G中的顶点数,m为边数。例：如右所示的平面图

m=8n=6l≥3R3R1R2R0m≤(n–2)l-2l∴8≤12(取l=3或4)

定理设G是简单平面图，有n(n≥3)个结点，m条边，则m≤3n-6

证明:设G有s(s≥1)个连通分支。若G为树或森林，则

m=n-s≤n=n+6-6=n+3+3-6≤n+n+n-6=3n–6。即m≤3n–6

若G不是树，也不是森林，则G中必含有回路。又因为G是简单平面图，所以其中的回路的长度均大于等于3，因而各面次数k≥3，又=1+，当k=3时，达到最大值3，因此：

m≤≤3(n-s-1)≤3(n-1-1)≤3n-6。定理：设G是极大平面图，有n(n≥3)个结点，m条边，则m=3n–6。证明：设G有r个面。由于极大平面图是连通图，所以G是连通图。由欧拉公式得r=2+m-n，又因为G是极大平面图，G的每个面的次数均为3，所以2m==3r=3(2+m-n)。整理后，m=3n–6。

定理：设G是简单平面图，则G的最小度(G)≤5。

证明：设G有n个结点，m条边。当n≤6，因为G是简单图，因此，(G)≤(G)≤5。以下证n≥7的情况，若(G)≥6，即每个结点的度数大于等于6，G中所有结点度数之和大于等于6n。于是2m=≥6n，m≥3n＞3n–6，即m＞3n–6，矛盾。库拉图斯基定理

设G是一个平面图，通过除G的一条边{x,y},并增加一个新结点a和两条边{x,a}与{a,y}（所获得的任何图也是平面图），这样的操作称为初等细分。若可以从相同的图G通过一系列初等细分来获得图G1和G2，称G1和G2是同胚的。如下图G1,G2,G3是同胚的。G1G2G3定理(库拉斯基定理)

一个图G是非平面的，当且仅当它包含一个同胚于K3.3或K5的子图。例说明彼得森图不是平面图。解:删去下图(a)皮得森图的结点b,得其子图(b)H。而H胚于K3,3,所以皮得森不是平面图。abcdefghijfaedighjcfdjeih(a)(b)H(c)K3,3重要结论：

(1)图G可嵌入球面图G可嵌入平面。

(2)平面图的子图都是平面图。

(3)非平面图的母图都是非平面图。

(4)平面图在加环或平行边后还是平面图。例：立方体是平面图。凸多面体

平面图的理论与多面体的研究密切相关:事实上,由于每个凸多面体P可以与一个连通可平面图G对应,G的顶点和边是P的顶点和棱,那么G的每个顶点的度至少为3.由于G是一个平面图,则P的面就是G的面,并且G的每一条边落在两个不同面的边界上.

一个多面体P的顶点,棱和面的数目分别用V,E和F来表示,而且,这些分别是连通图G的顶点,边和面的数目.故欧拉公式可写成V-E+F=2,这就是著名的Euler凸多面体公式.

为方便起见,用Vn和Fn分别表示凸多面体P的n度点和n度面的数目,则n3且

多面体的一些性质定理定理每个凸多面体都至少有一个n度面,其中3n5.证明:设F3=F4=F5=0,则:

即有F1/3E,又即V2/3E,所以E=V+F-21/3E+2/3E-2=E-2.矛盾.

所以结论成立.正多面体每个面且每个多面角都相等的凸多面体。定理:

只有五个正多面体:四面体、立方体、十二面体、八面体、二十面体.证明:设P是正多面体且G是对应的平面图,对任何凸多面体均有:

因为P是正多面体,所以存在两个正整数h(3)和k(3)使F=Fh且V=Vk,因此,有-8=(h-4)Fh+(k-4)Vk,且hFh=2E=kVk,因3h5.(1)当h=3时,有12=(6-k)Vk,由3k5.当k=3时,V3=4,F3=4,此时P是四面体.当k=4时,V4=6,F3=8,此时P是八面体当k=5时,V5=12,F3=20,此时P是十二面体(2)当h=4时,有8=(4-k)Vk,所以k=3,V3=8,F4=6,即P是立方体.(3)当h=5时,有20=(10-3k)Vk,所以k=3,V3=20,F5=12,即P是十二面体.图的平面性检测定义（图G的H片）:设H是G的子图，在E(G)-E(H)上定义二元关系R如下：xRy在G-E(H)中存在一条链W使得:（1）W的第一条边为x，最后一条边为y；（2）W中只有两个端点属于H(即W的内部点不属于H).R是E(G)-E(H)上的等价关系。R确定E(G)-E(H)上的一个划分设为S={S1、S2、…，Sm}由Si导出的G-E(H)的子图：B1、B2、…Bm称为G的H片。定义：若H1和H2都是图G的子图，称V（H1）V（H2）为H1和H2在G中的接触点集。记作VG(H1,H2).定义：

设H是可平面图G的子图，是H的平面表示，若存在G的平面表示,使称是G容许的。GG容许的子图G1非G容许的子图G2若B是G的H片，f是的面，而且

，称B在f内可画出，其中是f的边界。定理：设是G容许的，则对的每一个片B，有这里证明:若是G容许的,则存在G的一个平面表示

.显然,H的片B所对应的的子图必然限制在的一个面中,因此.

图G的平面检测的DMP算法DMP算法是由Demoucron,Malgrange,Pertuiset提供的.在介绍该算法前,先对图G进行如下预处理:(1)若G不连通,分别检测每一个连通分支.当且仅当所有的连通分支都是平面图,G就是平面图.(2)若G有割点,分别检测每一块.当且仅当每一块是平面图.(3)删去G中的环.(4)用一条边代替G中2度点和与之相关联的两条边.(5)删去平行边.

反复交错使用(4)与(5),直到不能使用为止.在做了上述简化后,在简单图G中利用(6)和(7)两个基本判断法:(6)若e<9或v<5,则G是平面图;(7)若e>3v-6或>5,则G不是平面图.

若不满足(6)和(7),则需进一步检测.例：利用DMP算法检测图G的平面性123456782134875613132661234276134对偶图设G是有n个顶点，m条边和r个面的平面图，令G的r个面为S1,S2,…,Sr。在G的每个图Si内部放置一个顶点vi*,如果面Si和Sj相邻,则用边(vi*,vj*)连接vi*和vj*点，使它与面Si，Sj的公共边只相交一次，且与G的其它边界无交点。这样得到的图G*称为G的对偶图。

用n*,m*,r*和n，m，r分别为G*和G的顶点数、边数和面数，则

(1)n*

＝r(2)m*＝m(3)r*

＝n这就是G*是连通平面图G的对偶图的对应关系。例：下图中实心点、虚线边图是空心点、实线边图的对偶图。abcedfv1*v2*v3*v4*

设G是平面图G=<V,E>,G有r个面，n个顶点，m条边，用如下方法构造图G*：

(1)在G的每个面Ri中任取一个顶点vi*作为G*的顶点集V*=v1*,v2*,…,vr*；

(2)若面Ri和Rj的边界中有公共边ek,连接对应顶点vi*和vj*,得G*的边ek*与ek相交,当ek只在G的一个面Ri的边界中出现时,以Ri中的顶点做环ek*,ek*为G*中一个环。设G*的边集为E*，由于G*的边数与G的边数相同，则E*=e1*,e2*,…,er*,称G*=<V*,E*>为G的对偶图。

非连通平面图G与其对偶图G*的关系

(1)n*=r

(2)m*=m

(3)r*=n-k+1(k为G的连通分支数，若G连通则k=1)

(4)设v*在面R中，则v*的度数等于R的次数自对偶图平面图G与其要对偶图G*同构，则称G是自对偶图。

在边形内放置一个顶点，使这个顶点与上的所有顶点均相邻，所得的阶简单图称为轮图。

所有轮图都是自对偶图。定理：任意平面图的对偶图都是连通的。(1)顶点着色：图的着色是对该图的每个顶点都指定一种颜色，使没有两个相邻的顶点指定为相同的颜色。(2)k着色：如果这些顶点选自于一个有k种颜色的集合，而不管k种颜色是否都用到，这样的着色称为k着色。(3)图G的色数是着色这个图G所需要的最少颜色数。记作(G)。(4)图G的不同K—着色的数目称为图G的色多项式。记作f(G,k).图的着色(5)Guv:设u,v是图G的不邻接的两个顶点，把u,v收缩成一个顶点x，并把G中凡与u,v关联的边均使之与x关联,这样所得的新图记作Guv。(6)G:e:把图G的一条边删去并使它的两个端点重合,也即边e被收缩。这样得到的新图记作G:e。说明:(1)若k<x(G)，此时k-着色不存在，显然有f(G,k)=0,

从而即知，满足f(G,k)>0的最小k即为G的色数。

(2)设mi是i种颜色对图G的顶点进行着色的不同方案数。用k(ki)种颜色对图G进行着色，每取i种颜色时，共有miCki种不同的着色方案，故有:f(G,k)=m1Ck1+m2Ck2+…+mnCkn,其中n为图G的顶点数。显然,f(G,k)是k的多项式。完全图的色多项式例：对三阶完全图K3而言,有f(K3,k)=k(k-1)(k-2)。解:由于对K3中的任何指定一个顶点,可以用k种颜色中的任何一种进行着色;对K3的第二个顶点,可以用k-1种颜色中的任何一种进行着色;对K3的第三个顶点,可以用k-2种颜色中的任何一种进行着色。一般地,有f(Kp,k)=k(k-1)(k-2)…(k-p+1)。定理：设u,v是G的两个不相邻的顶点则f(G,k)=f(G+{u,v},k)+f(G:uv,k)推论：设e={u,v}是图G的边，则f(G,k)=f(G-e,k)-f(G:e,k)说明:定理表明,若G是有P个顶点和q条边的图，则有一个q+1条边的图G1=G+{u,v}(u与v不相邻接)和一个有P-1个顶点的图G2=Guv，使f(G,k)=f(G1,k)+f(G2,k)。对G1和G2依次类推，直到只出现完全图为止。因此,一个图的色多项式f(G,k)是f(Kn,k)型的表达式的和。例：求图G的色多项式。f(G,k)=k5+3k4+k3=k(k-1)(k-2)(k-3)(k-4)+3k(k-1)(k-2)(k-2)(k-3)+k(k-1)(k-2)=k5-7k4+18k3-20k2+8kG四色问题:连通简单平面图的色素不超过4。

四色问题是盖思里于1852年提出,后经众多数学家尝试证明,均以失败告终.1976年,美国数学家阿佩尔和黑肯宣布借助用计算机证明,但时间超过了1000小时,其可靠性仍在置疑之中。定理（五色定理）连通简单平面图G的色数为不超过5。证明:对图的顶点数作归纳。

n5时,结论显然.若n-1个顶点时结论成立。下证有n个顶点时结论也成立.由于G是平面图,则(G)5。故在G中至少存在一个顶点v0,其度数d(v0)5.在图中删去顶点v0得图G’,由归纳假设知G’的色素为5.然后将v0又加回去,有两种情况:(1)d(v0)<5或d(v0)=5但和v0邻接的5个结点的颜色数小于5.则v0极易着色,只要选择与四周顶点不同的颜色着色即可。(2)d(v0)=5且和v0邻