平面图和图的着色

平面图和图的着色1第1页，课件共55页，创作于2023年2月

9.1平面图及欧拉公式

uv

uv

定义9.1.1

图G称为被嵌入平面S内，如果G的图解已画在平面S上，而且任何两条边均不相交(除顶点外)。已嵌入平面的图称为平面图。如果一个图可以嵌入平面，则称此图是可平面的。

2第2页，课件共55页，创作于2023年2月几点说明及一些简单结论一般所谈平面图不一定是指平面嵌入。但讨论某些性质时，是指平面嵌入.结论：

(1)K5,K3,3都不是平面图(待证).(2)设G

G，若G为平面图，则G

也是平面图.由此可知，Kn(n≤4)，K2,n(n

1)都是平面图.(3)设G

G，若G

为非平面图，则G也是非平面图.由此可知，Kn(n

5)，Km,n(m,n

3)都是非平面图.(4)平行边与环不影响平面性.

3第3页，课件共55页，创作于2023年2月

uvf1f2f3f4

定义9.1.2

平面图把平面分成了若干个区域，这些区域都是单连通的，称之为G的面，其中无界的那个连通区域称为G的外部面，其余的单连通区域称为G的内部面。平面图的内部面与外部面4第4页，课件共55页，创作于2023年2月平面图的每个内部面都是G的某个圈围成的单连通区域。没有圈的图没有内部面，只有一个外部面。

uvf1f2f3f4

图15第5页，课件共55页，创作于2023年2月(2)面Ri的边界——包围Ri的闭通道组(3)面Ri的次数——Ri边界的长度几点补充(1)若平面图G有k个面，可用R1,R2,…,Rk表示.(4)闭通道组是指：边界可能是圈，也可能是闭通道.特别地，还可能是非连通的闭通道之并.定理平面图各面次数之和等于边数的两倍.6第6页，课件共55页，创作于2023年2月如果用V表示多面体的顶点，用E表示棱，用F表示面数，则V-E+F=2。

定理9.1.1(欧拉公式)

如果一个平面连通图有p个顶点、q条边、f个面，则p-q+f=2。证对面数用归纳法当f=1时，G没有内部面，所以G中无圈，G是树。p-q+f=1+1=2假如对一切不超过f-1个面的平面连通图欧拉公式成立，现证f个面时的情况。7第7页，课件共55页，创作于2023年2月f≥2，G至少有一个内部面，从而G中有一个圈。这个内部面是由这个圈围成的，从这个圈上去掉一条边x，则打通了两个面。

G-x有p个顶点，q-1条边，f-1个面。由归纳假设p-(q-1)+(f-1)=2p-q+f=2因此面数是f时也成立。

uvf1f2f3f4

uvf1f2f3f48第8页，课件共55页，创作于2023年2月定理9.1.2

（欧拉公式的推广）设G是具有k(k

2)个连通分支的平面图，则n

m+r=k+1.9第9页，课件共55页，创作于2023年2月

推论9.1.1

若平面连通图G有p个顶点q条边且每个面都是由长为n的圈围成的，则q=n(p-2)/(n-2)。

证

因为G的每个面都是长为n的圈围成的，所以G的每条边都在G的两个面上。q=f

n/2f=2q/np-q+2q/n=2q=n(p-2)/(n-2)10第10页，课件共55页，创作于2023年2月最大(极大)可平面图

一个图称为最大可平面图，如果这个可平面图再加入一条边，新图必然是不可平面的。

图1再加一条边就是k5，可证k5是不可平面图。图1是最大可平面图。11第11页，课件共55页，创作于2023年2月

最大(极大)平面图的性质

uv最大(极大)平面图的主要性质：定理最大(极大)平面图是连通的.定理

n(n

3)阶最大(极大)平面图中不可能有割点和桥.

12第12页，课件共55页，创作于2023年2月

推论9.1.2

设G是一个有p个顶点q条边的最大可平面图，则G的每个面都是三角形，q=3p-6，p≥3。证若G的一个面不是三角形,

...

v1v2v3v4

1、假如有两点不相邻，则在此面中把不相邻的两顶点连接起来，不影响平面性。矛盾，因此不可能有两点不相邻。13第13页，课件共55页，创作于2023年2月2、假如圈上每两点都相邻;

...

v1v2v3v4若v1,v2和v2,v4在G中都邻接,我们可以看到这两个边不可能不相交;综合以上情况，最大平面图的每个面都是三角形。14第14页，课件共55页，创作于2023年2月

推论9.1.3

设G是一个(p,q)可平面连通图，而且G的每个面都是一个长为4的圈围成的，则q=2p-4。

推论9.1.4若G是任一有p个顶点q条边的可平面图p≥3，则q≤3p-6。若G是2-连通的且没有三角形，则q≤2p-4。1、因为当平面图中每个面都是三角形时其边数最多，由推论9.1.2，则q≤3p-6。

2、若G是2-连通的且没有三角形,则G中任意两个顶点都在同一个圈上。已知没有三角形，所以圈的长都是4时边数最多。所以q≤2p-4。15第15页，课件共55页，创作于2023年2月推论9.1.5K5与K3,3都不是可平面图

证

如果K5是平面图，则5-10+f=2，即f=7。每个面至少三条边，7个面至少需要21条边。考虑到每条边在两个面上，2q≥3f，即20≥21。矛盾。

其实直接利用推论9.1.4，任意(p,q)平面图都满足q≤3p-6，这里p≥3。q=10≤3p-6=9，这是不成立的。所以K5不是可平面图。16第16页，课件共55页，创作于2023年2月如果K3,3是平面图，则p-q+f=2，即6-9+f=2，亦即f=5。在偶图K3,3中每个圈的长至少为4，所以2q≥4f=20，q≥10，但q=9，矛盾。

所以K3,3不是平面图。17第17页，课件共55页，创作于2023年2月

推论9.1.6每个平面图G中顶点度的最小值不超过5，即(G)≤5。如果G的每个顶点的度大于5，也就是≥6，由欧拉定理，2q≥6p，即q≥3p。仍然用推论9.1.4，q≤3p-6。那么所有顶点的度数和大于或等于6p。不满足推论9.1.4，q≤3p-6。因此，每个平面图G中顶点度的最小值不超过5，即(G)≤5。18第18页，课件共55页，创作于2023年2月例9.1.1顶点数p≥4的最大平面图，(G)≥3。证

设G是最大平面图，其最小度顶点为v。设G-v也是一个平面图，v在G-v的一个面内。在这个面内，边界上至少有三个顶点。由极大性，v必然与这些顶点都相连。因此，

(G)≥3。

v19第19页，课件共55页，创作于2023年2月

定理9.2.1

设G=(V,E)是一个(p,q)平面哈密顿图,C是G的哈密顿圈，令fi为C的内部由i条边围成的面的个数，gi为C的外部i条边围成的面的个数，则9.2非哈密顿平面图(1)1f3+2f4+3f5+...+(p-2)fp=(2)1g3+2g4+3g5+...+(p-2)gp=(3)1(f3-g3)+2(f4-g4)+3(f5-g5)+...=

v1v2v3v4v5v6v7v8有哈密顿圈v1v2v3v4v8v7v6v5v1圈内有3条边围成的面2个圈内有4条边围成的面2个圈外有8条边围成的面1个20第20页，课件共55页，创作于2023年2月

证

因为C是G的哈密顿圈，所以G的所有顶点都在圈C上。因此C的内部与外部不再含有G的顶点。

C的内部的每个面都是由C上的某边及C上两顶点间的“连线”围成的区域。

v1v2v3v4v5v6v7v8设q

是C的内部(不含C)边的条数，这些边之集记为E

。先把C内部的边都去掉，这时C里只有一个面。把E

的一条边加入C中。就把C分成两个面。再加入E的另一条边就把这两个面之一分为两个面，如此进行，直到把E的边都加入为止。这样，C的内部就有q+1个面。21第21页，课件共55页，创作于2023年2月f1+f2+f3+...=其次，由j条边围成面共fj个，这些面上的边的总数为jfj，所以，C内部的q+1个面上的边数共有。其中C上的每条边在每个内部面上至多出现一次且不是两个内部面的公共边，所以在上述计数中C上每条边各计数一次。但E

中的每条边是两个面之公共边，所以每条边计数两次，因此。

v1v2v3v4v5v6v7v822第22页，课件共55页，创作于2023年2月从(2)式两边分别减去(1)式两边的两倍便得到f1+f2+f3+...=(1)(2)用同样的方法可得:(3)(4)(3)式两边分别减去(4)式的两边得23第23页，课件共55页，创作于2023年2月

例9.2.2

下图是一个哈密顿图，证明：任一哈密顿圈上如果包含边x，那么这个哈密顿圈上就一定不包含边y。

xy证右图G是哈密顿平面图，它的面或由4条边围成，或由5条边围成，由定理9.2.1有:2(f4-g4)+3(f5-g5)=0所以f4-g4能被3整除，即五个由4条边围成的面中有四个面在G的哈密顿圈C外，一个在C内；或相反即一个在C外，四个在C的内部。123456724第24页，课件共55页，创作于2023年2月同样，以y为公共边的两侧的四条边围成的两个面中，必一个在C的内部，另一个在C的外部。这就得到矛盾，故C不能同时含边x与y。

xy因此，C的内部与C的外部均至少有两个四条边围成的面。假如C既含边x又含边y，则以x为公共边的两侧的四条边围成的两面中必有一个在C的内部，另一个在C的外部。25第25页，课件共55页，创作于2023年2月K5和K3,3不是平面图。9.3库拉托斯基定理、对偶图平面图的每个子图都是平面图，因此，平面图中不含子图K5和K3,3。

定义9.3.1

设x=uv是图G=(V,E)的一条边，w不是G的顶点，则当用边uw和wv代替边x时，就称x被细分。如果G的某些边被细分，产生的图称为G的细分图。

uv图Gx

uvwG的细分图26第26页，课件共55页，创作于2023年2月

定义9.3.2

两个图称为同胚的，如果它们都可以从同一个图通过一系列的边细分得到。下面几个图是同胚的。

uv图Gx

uvwG的细分图

图与图之间同胚27第27页，课件共55页，创作于2023年2月定义9.3.1

所定义的的细分也称为插入2度顶点。与之相对应的还有一种方法：消去2度顶点。补充(1)消去2度顶点v，见下图中，由(1)到(2)；(2)插入2度顶点v，见下图中，从(2)到(1).定义若G1

G2，或经过反复插入或消去2度顶点后所得G

1

G

2，则称G1与G2同胚.28第28页，课件共55页，创作于2023年2月

定理9.3.1（库拉托斯基,1930）一个图是可平面的充分必要条件是它没有同胚于K5和K3,3的子图。

例9.3.1

证明左下图不是可平面图。因为它含有与K5同胚的子图。

uv库拉托斯基定理29第29页，课件共55页，创作于2023年2月例9.3.2

证明所示图(1)与(2)均为非平面图.

(1)(2)右图(1),(2)分别为原图(1),(2)的子图与K3,3,K5同胚.

子图(1)子图(2)

30第30页，课件共55页，创作于2023年2月

定义9.3.3

一个图G的一个初等收缩由合并两个邻接的顶点u和v得到，即从G中去掉u和v，然后再加上一个新顶点w，使得w相邻所有与u或v相邻的顶点。

uv

w一个图G可收缩到图H，如果H可以从G经一系列的初等收缩得到。图G的初等收缩31第31页，课件共55页，创作于2023年2月

定理9.3.2

一个图是可平面的当且仅当它没有一个可以收缩到K5或K3,3的子图。

例9.3.1

证明左下图不是可平面图。因为它可以收缩到K5。32第32页，课件共55页，创作于2023年2月

定义9.3.4

设G=(V,E)是一个平面图，由G按如下方法构造一个图G*，G*称为G的对偶图。

3、如果某条边x仅在一个面中出现而不是两个面的公共边(是不是桥？)，则在G*中这个面对应的顶点有一个环。

1、对G的每个面f对应地有G*的一个顶点f*；

2、对G的每条边e对应地有G*的一条边e*：G*的两个顶点f*与g*由边e*联结，当且仅当G中与顶点f*与g*对应的面f与g有公共边e。平面图的对偶图33第33页，课件共55页，创作于2023年2月下面两图中，实线边图为平面图，虚线边图为其对偶图.

实例34第34页，课件共55页，创作于2023年2月对偶图的性质G的对偶图G*有以下性质：(1)G*是平面图，而且是平面嵌入.(2)G*是连通图.(3)若边e为G中的环，则G*与e对应的边e*为桥，若e为桥，则G*中与e对应的边e*为环.(4)在多数情况下，G*为多重图(含平行边的图).(5)同构的平面图(平面嵌入)的对偶图不一定是同构的.35第35页，课件共55页，创作于2023年2月(6)设G*是连通平面图G的对偶图，n*,m*,r*和n,m,r分别为G*和G的顶点数、边数和面数，则1)n*=r；2)m*=m；3)r*=n；4)设G*的顶点v*i位于G的面Ri中，则

degG*(v*i)=面Ri的次数.对偶图的性质只证明(3)r*=n。由图G与G*都是连通平面图，所以n*-m*+r*=2得r*=m*-n*+2=m-r+2n-m+r=2可得n=m-r+2因此r*=n。36第36页，课件共55页，创作于2023年2月9.4图的顶点着色

定义9.4.1

图的一种(顶点)着色是指对图的每个顶点指定一种颜色，使得没有两个相邻的顶点有同一颜色。若图G=(V,E)的顶点已着色，则着同一颜色的那些顶点之集称为G的一个色组。同一色组内的各顶点不相邻，这样的顶点集合称为G的一个顶点独立集。如果G有一个n着色，则G的顶点集V被这种n着色划分为n个色组。图G的一个n着色是用n种颜色对G的顶点着色。

12123212137第37页，课件共55页，创作于2023年2月

定义9.4.2

图G的色数是使G为n着色的数的最小值，图G的色数记为

(G)。若

(G)n，则称G是n可着色的。若

(G)=n，则称G是n色的。

(Kp)=p

(Kpc)=1

(Km,n)=2,

图G的色数的概念38第38页，课件共55页，创作于2023年2月

定理9.4.1

一个图是可双色的当且仅当它没有奇数长的圈。一个图是可双色的当且仅当是偶图。偶图的充分必要条件是它的圈的长度都是偶数。若G是偶数个顶点的圈C2n，则

(C2n)=2。若G是奇数个顶点的圈C2n+1，则

(C2n+1)=3。

121232121

1212212139第39页，课件共55页，创作于2023年2月

定理9.4.2

设

=(G)为图G的顶点度的最大值，则G是(+1)—可着色的。证

对顶点数p用归纳法。当p=1时，结论成立。假设对顶点数为p-1的图定理成立，今设G是一个有p个顶点的图。从G中去掉一个顶点v，则G-v有p-1个顶点，

(G-v)≤(G)由归纳假设G-v是(+1)—可着色的。但在G中与v相邻的顶点最多有个，与v相邻的顶点最多用去种颜色，剩下一种给顶点v着色即可。40第40页，课件共55页，创作于2023年2月

定理9.4.3

如果G是一个连通图且不是完全图也不是奇数长的圈，则G是

(G)—可着色的。41第41页，课件共55页，创作于2023年2月定理9.4.4

每个平面图都是6可着色的。如果顶点数小于7，显然是6—可着色的。证

对平面图的顶点数p用归纳法。设G是一个有p个顶点的平面图，由推论9.1.6知G有顶点v，degv≤5，G-v是一个p-1个顶点的平面图。假设对p-1个顶点的平面图是6—可着色的，只需证对有p个顶点的平面图也是6—可着色的即可。由归纳假设，G-v是6—可着色的,与v相邻的顶点至多5个，所以与v相邻的顶点着色时至多用了5种色。用另一种未用的颜色对v着色即得G的一个6—着色。因此,G是6可着色的。42第42页，课件共55页，创作于2023年2月定理9.4.5

每个可平面图是5—可着色的证对可平面图的顶点数进行归纳证明。当p≤5时。定理显然成立。假设所有p个顶点的可平面图都是5—可着色的，需证所有p+1个顶点的可平面图也是5—可着色的。设G是一个有p+1个顶点可平面图，由推论9.1.6知G中有一个顶点v使degv≤5。于是，G-v是一个有p个顶点的可平面图，由归纳假设，G-v是5可着色的。

1、如果degv≤4,则必有一种颜色，在G-v的一种5-着色时，对与v相邻的顶点着色中未用此色，于是，用此色对顶点v着色便得到G的5-着色。43第43页，课件共55页，创作于2023年2月

2、degv=5且对G-v的5-着色中，与v相邻的5个顶点v1,v2,v3,v4,v5分别着5种颜色c1,c2,c3,c4,c5。

v1vv2v3v4v5令G13为G-v的一个子图，其顶点为着c1色或c3色的顶点之集V13,G13就是V13导出的子图。(1)若v1和v3在G13的不同支中，则在含v1的支中交换两种色，即原着c1色顶点改着c3色，原着c3色的顶点改着c1色。

c3c1c3c1

c3c1c3c1

c1c3c1c3

c3然后用c1给顶点v着色，于是得到G的一种5—着色。44第44页，课件共55页，创作于2023年2月

(2)若v1和v3在G13的同一个支中，则在G13中有一条从v1到v3的路，于是，在G中v1vv3与这条路合起来形成一个圈。

v1vv2v3v4v5

3131这个圈或把v2圈在圈内或把v4和v5圈在内。若令G24表示G-v的由着c2或c4色的顶点导出的子图，则v2与v4属于G24的不同支里。

4

2

4

2

4

2交换G24的含v2支中着c2色顶点与着c4色顶点的颜色，然后，用c2色为v着色得到G的一个5着色。任何情况下，不存在联结v2和v4的路且路上各顶点或着c2或着c4色。45第45页，课件共55页，创作于2023年2月4色猜想每个可平面图是4—可着色的。定理9.4.6

每个可平面图是4—可着色的。

1852年，刚从伦敦大学毕业的哥斯尼从事地图染色工作，他发现在一幅正规地图中，最多只用四种颜色着色，就能把这些国家区别开来。如果国家用图的顶点来表示，两个顶点相邻当且仅当两个国家相邻，就形成一个平面图。46第46页，课件共55页，创作于2023年2月9.5图的边着色

定义9.5.1

图G的一个k—边着色是对G的每条边指定k种色之一，使得任何两条相邻的边被指定色是不同的。如果图G是k—边着色的，但不(k-1)—边着色的，则称G的边色数为k，G的边色数记为

(G)。

12314234如果=(G)是图G的顶点的最大度数，则显然有

(G)≥。右图存在一个4—边着色不存在3—边着色

(G)=447第47页，课件共55页，创作于2023年2月对某些特殊类型的图，我们能容易确定它的边色数。例如：偶数长的圈C2n的边色数是

(C2n)=2。

121232121

12122121对奇数长的圈C2n+1有

(C2n+1)=3。48第48页，课件共55页，创作于2023年2月

定理9.5.1

如果p是不为1的奇数，则

(Kp)=p。如果p是偶数，则

(Kp)=p-1。证

设p是奇数，把Kp的p个顶点安放在正p边形的顶点上，对正p边形的p个边分别着p个不同色。而平行于p边形的对角线的边着与这条边同一颜色，这就得到Kp的一个p—边着色。

1、证明当p是奇数时，Kp是p边着色的。49第49页，课件共55页，创作于2023年2月Kp最多有(p-1)

(Kp)/2条边;(p-1)/2条平行边已关联了(p-1)个顶点，所以在Kp的边着色中至多有(p-1)/2条同