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

2024/4/22 周一14.1 平面图定义定义4.1：若能把图若能把图G画在一个平面上，使任何两画在一个平面上，使任何两条边都不相交，就称条边都不相交，就称G可嵌入平面可嵌入平面，或称，或称G是是可平面图可平面图。可平面图可平面图在平面上在平面上的一个的一个嵌入嵌入称为称为平面图平面图。2024/4/22 周一2v1v4v2v3(a)4.1 平面图e1e2e3e4e5e6v1v4v2v3(b)e1e2e3e4e5e6v1v4v3v2(c)e1e2e3e4e5e6可平面图可平面图平面图平面图平面图平面图2024/4/22 周一34.1 平面图定义定义4.2：设设G是一个是一个平面图平面图，由，由G的一个初级回的一个初级回路围成的一个路围成的一个区域内区域内如果不含任何如果不含任何结点及边结点及边，就称为就称为G的一个的一个面面或或域域。包含这个域的各。包含这个域的各边边称称为该域的为该域的边界边界。平面图平面图G的外边的无限区域称为的外边的无限区域称为无限域无限域或或外部外部区域区域，其他的域叫，其他的域叫内部域内部域。2024/4/22 周一4v1v4v2v3(b)F1F2F3F44.1 平面图e1e2e3e4e5e6F1=v1 e1 v2 e6 v4 e4 v1边界为：边界为：e1,e6,e4 F2=v1 e5 v3 e3 v4 e4 v1边界为：边界为：e5,e3,e4 F3=v1 e1 v2 e2 v3 e5 v1边界为：边界为：e1,e2,e5 F4=v2 e2 v3 e3 v4 e6 v2边界为：边界为：e2,e3,e6 2024/4/22 周一5v1v4v2v3(c)F1F2F3F44.1 平面图e1e2e3e4e5e6F1=v1 e1 v2 e6 v4 e4 v1边界为：边界为：e1,e6,e4 F2=v1 e5 v3 e3 v4 e4 v1边界为：边界为：e5,e3,e4 F3=v2 e2 v3 e3 v4 e6 v2边界为：边界为：e2,e3,e6 F4=v1 e1 v2 e2 v3 e5 v1边界为：边界为：e1,e2,e5 2024/4/22 周一64.1 平面图 如果两个如果两个域域有有共同共同的的边界边界，则称它们是，则称它们是相邻相邻的的，否则是，否则是不相邻的不相邻的。如果边如果边e不是割边，则不是割边，则e一定是某两个域的共一定是某两个域的共同边界。同边界。2024/4/22 周一74.1 平面图e7v1v4v2v3F1F2F3F7e1e2e3e4e5e6v5v8v6v7F4F5F6e8e9e10e11e12e13F1=v1 e1 v2 e6 v4 e4 v1与与F2=v1 e5 v3 e3 v4 e4 v1相邻相邻共同边界为：共同边界为：e4，割边割边e7 只是面只是面F7的边界。的边界。2024/4/22 周一84.1 平面图定理定理4.1 设设G是有是有n个结点和个结点和m条边的平面连通图，条边的平面连通图，则则G的的面面的数目的数目d是是 dmn2 （欧拉公式）（欧拉公式）证明：设连通图证明：设连通图G的支撑树是的支撑树是T。T包含包含n1条边，条边，不包含回路，因此不包含回路，因此T只有一个只有一个无限域无限域。2024/4/22 周一94.1 平面图TF02024/4/22 周一104.1 平面图 由由G是平面图，每加入一条余树的边是平面图，每加入一条余树的边e，它一定不与，它一定不与其他边相交，即其他边相交，即e一定在某个一定在某个域域的内部，把该域分成两的内部，把该域分成两部分。部分。2024/4/22 周一114.1 平面图TF0eF1F2eeF3F4F52024/4/22 周一124.1 平面图这样，加入这样，加入G的的mn1条边，生成了条边，生成了mn1个新的域。加上无限域，共有个新的域。加上无限域，共有dmn2 个域。个域。2024/4/22 周一134.1 平面图推论推论4.1 有有n个结点和个结点和m条边的平面图条边的平面图G有有k个连通支，个连通支，则则 nm dk1。推论推论4.2 对任一平面图对任一平面图G，恒有，恒有 nm d 2。v1v4v2v3F1F2F3F7e1e2e3e4e5e6v5v8v6v7F4F5F6e7e8e9e10e11e122024/4/22 周一144.1 平面图定理定理4.2 设有设有n个结点和个结点和m条边的平面连通图条边的平面连通图G没没有割边，且每个域的边界数至少是有割边，且每个域的边界数至少是t，则，则 m t(n2)t2亦即亦即t(n2)t2m mn 22mt证明：设证明：设G 有有d个域，每个域的边界数至少是个域，每个域的边界数至少是t，且每条边都与两个不同的域相邻。因此且每条边都与两个不同的域相邻。因此td 2m。代入欧拉公式：。代入欧拉公式：2024/4/22 周一154.2 极大平面图定义定义4.3：设设G是有是有n 3个结点个结点的的简单平面图简单平面图，若在任意两个不相邻的结点若在任意两个不相邻的结点vi，vj之间加入边之间加入边(vi，vj)，就会破坏图的平面性，则称，就会破坏图的平面性，则称G是极大平是极大平面图面图。极大平面图极大平面图不是极大平面图不是极大平面图2024/4/22 周一164.2 极大平面图v1v2v3v4v52024/4/22 周一174.2 极大平面图设有设有n个结点和个结点和m条边的极大平面图条边的极大平面图G具有以下性质：具有以下性质：性质性质1.G是连通的。是连通的。性质性质2.G不存在割边。不存在割边。性质性质3.G的每个域的边界数都是的每个域的边界数都是3（极大平面图也称为（极大平面图也称为平面三角剖分）。平面三角剖分）。性质性质4.3d=2m。2024/4/22 周一184.2 极大平面图性质性质3.G的每个域的边界数都是的每个域的边界数都是3。证明：由证明：由G是简单图，没有自环和重边，因此不是简单图，没有自环和重边，因此不存在边界数为存在边界数为1和和2的域。的域。假设假设G存在边界数大于存在边界数大于3的域的域dj，不妨设，不妨设dj是是G的内部域，域的内部域，域dj的边界为：的边界为：dj=i1 e1 i2 e2 i3 e3 i4 e4 i5，这里结点这里结点i1,i2,i3,i4互不相同。互不相同。e1i4dje2e3e4i1i2i3i52024/4/22 周一194.2 极大平面图性质性质3.G的每个域的边界数都是的每个域的边界数都是3。证明：若结点证明：若结点i1和和 i3 不相邻，则在域不相邻，则在域dj内加入边内加入边(i1,i3)后仍然是平面图，与后仍然是平面图，与G是极大平面图矛是极大平面图矛盾，因此边盾，因此边(i1,i3)一定存在于域一定存在于域dj之外。之外。e1i4dje2e3e4i1i2i3i5e1i4dje2e3e4i1i2i3i52024/4/22 周一204.2 极大平面图性质性质3.G的每个域的边界数都是的每个域的边界数都是3。证明：这时，在域证明：这时，在域dj之外不可能存在边之外不可能存在边(i2,i4)。亦即亦即i2和和 i4 不相邻，但在域不相邻，但在域dj内加入边内加入边(i2,i4)并并不影响不影响G的平面性，得到矛盾。的平面性，得到矛盾。e1i4dje2e3e4i1i2i3i52024/4/22 周一214.2 极大平面图性质性质4.3d=2m。证明：由性质证明：由性质2，每条边都是两个不同域的边界，每条边都是两个不同域的边界，再由性质再由性质3即得。即得。2024/4/22 周一224.2极大平面图定理定理4.2.1对有对有n个结点和个结点和m条边的极大平面图条边的极大平面图G，有，有 m3n6，d2n4证明：由极大平面图的性质证明：由极大平面图的性质4 3d=2m代入欧拉公式代入欧拉公式 dmn2整理后即得。整理后即得。2024/4/22 周一234.2极大平面图定理定理4.2.2 简单平面图简单平面图G中存在度小于中存在度小于6的结点。的结点。证明：设简单平面图证明：设简单平面图G的每个结点的度都的每个结点的度都不不小于小于6。由由 d(vi)2m，得到，得到 6n 2m 因为因为G是简单平面图，又有是简单平面图，又有3d 2m。代入欧拉公式的。代入欧拉公式的一般形式：一般形式：nm d 2 有有 0=1/3mm 2/3m 2，得到矛盾。，得到矛盾。vi V2024/4/22 周一244.2极大平面图例例 4.2.2 7个结点的完全图个结点的完全图K7不是平面图。不是平面图。证明：因为证明：因为 7个结点的完全图个结点的完全图K7的每个结点的度的每个结点的度均为均为6。由定理。由定理4.2.2即得证。即得证。2024/4/22 周一254.3 非平面图如果对图如果对图G的任意一种平面嵌入，都至少存在两条的任意一种平面嵌入，都至少存在两条边，它们在不是结点处相交，称边，它们在不是结点处相交，称G为为非平面图非平面图。图图平面图平面图非平面图非平面图2024/4/22 周一264.3非平面图如果图如果图G不是简单图，可首先删去自环和重边，不是简单图，可首先删去自环和重边，因为它们不影响图的平面性。因此只考虑简单图。因为它们不影响图的平面性。因此只考虑简单图。考查在结点数固定情况下考查在结点数固定情况下 边数边数最少的最少的非平面图非平面图。完全图完全图K3，K4是可平面图。是可平面图。任取一条边任取一条边e，图，图K5 e也是可平面图。也是可平面图。2024/4/22 周一274.3非平面图v1v4v2v3v1v2v3K3K4v1v2v3v4v5K5 v3v5可平面图可平面图2024/4/22 周一284.3非平面图定理定理4.3.1 完全图完全图K5是是 非平面图非平面图。证明：在完全图证明：在完全图K5 中，中，n5，m10。如果。如果K5是是可平面图可平面图，应有，应有 m 3n6。而对于。而对于K5，3n6 9，得到矛盾。，得到矛盾。由此得到：由此得到：K5是结点数最少的非平面图。是结点数最少的非平面图。2024/4/22 周一294.3非平面图例例4.3.1 完全二分图完全二分图K3,3中移去任一边后是可平面中移去任一边后是可平面图。图。2024/4/22 周一304.3非平面图定理定理4.3.2完全二分图完全二分图K3,3是是 非平面图非平面图。K3,3是有是有6个结点的图中个结点的图中边数最少边数最少的的非平面图非平面图。证明：假设证明：假设K3,3是可平面图，由于是可平面图，由于n6，m9。由。由欧拉公式，欧拉公式，d5。但。但K3,3中不含三角形。因此每个中不含三角形。因此每个域的边界数至少是域的边界数至少是4，且每条边都与两个不同的域，且每条边都与两个不同的域相邻。所以相邻。所以4d 2m，即，即20 18，得到矛盾。，得到矛盾。有有6个结点的图中边数个结点的图中边数m 9的图均为的图均为平面图平面图。2024/4/22 周一314.3非平面图 K5和和K3,3分别记为分别记为K(1)和和K(2)。定义定义4.3.1：在图：在图K(1)和和K(2)上任意增加一些度为上任意增加一些度为2的结点之后得到的图称为的结点之后得到的图称为K(1)型型和和K(2)型图型图，统，统称为称为K型图型图。2024/4/22 周一324.3非平面图K型型(K(1)型和型和K(2)型型)图均为图均为非平面图非平面图。2024/4/22 周一334.3非平面图定理定理4.3.3(库拉图斯基定理库拉图斯基定理)：G是是可平面图可平面图的的充充要条件要条件是是G不存在在不存在在K型子图型子图。K(1)型子图型子图K(2)型子图型子图例例4.3.2 完全图完全图K6既含有既含有K(1)型子图，也含有型子图，也含有K(2)型子图，所以是型子图，所以是非平面图非平面图。如图：。如图：2024/4/22 周一344.4 图的平面性检验可平面性检验的预处理：可平面性检验的预处理：1.如果如果G是是非连通非连通的，则分别检验每一个连通分的，则分别检验每一个连通分支。当所有的连通分支都是支。当所有的连通分支都是可平面图可平面图时，时，G才才是是可平面图可平面图。v11v21B1B2B3v12v222024/4/22 周一352.如果如果G中存在中存在割点割点v，可把图，可把图G从割点处分离从割点处分离，构成若干个不含割点的连通子图，称为构成若干个不含割点的连通子图，称为块块。4.4 图的平面性检验2024/4/22 周一36G是是可平面图可平面图，当且仅当每个，当且仅当每个块块是是可平面图可平面图。4.4 图的平面性检验v1v2v11v21B1B2B3v12v222024/4/22 周一374.4 图的平面性检验3.移去自环。移去自环。v11B1v11B12024/4/22 周一384.4 图的平面性检验4.移去度为移去度为2的结点的结点vi及其所关联的边，同时在及其所关联的边，同时在vi的两个邻结点的两个邻结点vj,vk之间加入边之间加入边(vj,vk)。v11B1B1原图是原图是可平面图可平面图，当且仅当新图是，当且仅当新图是可平面图可平面图。2024/4/22 周一394.4 图的平面性检验5.移去重边。移去重边。B1B12024/4/22 周一404.4 图的平面性检验反复运用反复运用4和和5。最后，如果。最后，如果 a.m 9或或 n 3n-6，则，则G是是非平面的非平面的。c.不满足不满足a和和b，需要进一步检查。，需要进一步检查。2024/4/22 周一414.4 图的平面性检验例例4.4.1 判断下图的可平面性。判断下图的可平面性。v1v2G由判定规则由判定规则2，G有两个割点有两个割点v1和和v2；可分成；可分成3个块。个块。2024/4/22 周一424.4 图的平面性检验v11B1对块对块B2，n 5，所以块，所以块B2是平面图。是平面图。v21B2v12B3v22由判定规则由判定规则4处理块处理块B1和和B3，得到如下的图。，得到如下的图。2024/4/22 周一434.4 图的平面性检验B1B3v22由判定规则由判定规则5，得到如下的图。，得到如下的图。B1B3v22对块对块B3，m 9，所以块所以块B3是平面图。是平面图。2024/4/22 周一444.4 图的平面性检验由判定规则由判定规则4处理块处理块B1，得到如下的图。，得到如下的图。B1由判定规则由判定规则5，得到如下的图。，得到如下的图。B1对块对块B1，n 5，所以块，所以块B1是平面图。是平面图。2024/4/22 周一454.4 图的平面性检验例例4.4.1 判断下图的可平面性。判断下图的可平面性。v1v2G所以图所以图G是可平面图。是可平面图。2024/4/22 周一464.4 图的平面性检验图图G的平面嵌入如下：的平面嵌入如下：v1v2G2024/4/22 周一474.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相交相交一次。一次。2024/4/22 周一484.4 对偶图v1v2v3v4v5v4*v1*v2*v3*F1F2F3F4图图 G 的对偶图的对偶图G*：e1*e1e2e7*e4e2*e3*e3e4*e5e5*e6e6*e72024/4/22 周一494.4 对偶图v4*v1*v2*v3*图图 G 的对偶图的对偶图G*：e1*e7*e2*e3*e4*e5*e6*2024/4/22 周一50 F1 F2 F4 F5 v3v4e1e2e3e4e5 F0 v1v2v54.4 对偶图求图求图 G 的对偶图的对偶图G*：2024/4/22 周一51v2*4.4 对偶图 F0 F1 F2 F3 F4 F5 v1*v0*v3*v4*v5*v1v2v3v4v5e1e1*e2e3e4e5e2*e3*e4*e5*图图 G 的对偶图的对偶图G*2024/4/22 周一52v2*4.4 对偶图v1*v0*v3*v4*v5*e1*e2*e3*e4*e5*图图 G 的对偶图的对偶图G*2024/4/22 周一534.4 对偶图v1v2v3v4v5v6v1*v2*v3*求图求图 G 的对偶图的对偶图G*：2024/4/22 周一544.4 对偶图v1*v2*v3*求图求图 G 的对偶图的对偶图G*：2024/4/22 周一554.4 对偶图性质性质4.5.1 如果如果G是平面图，是平面图，G一定有对偶图一定有对偶图G*，而且而且G的对偶图的对偶图G*是唯一的。是唯一的。性质性质4.5.2 G*是连通的。是连通的。性质性质4.5.3 若若G是平面连通图，则是平面连通图，则(G*)*G。性质性质4.5.4平面连通图平面连通图G与其对偶图与其对偶图G*的结点、边的结点、边和域之间存在如下对应关系：和域之间存在如下对应关系：m*m，n*d，d*n2024/4/22 周一564.4 对偶图v1v2v3 v4v5v4*v1*v2*v3*2024/4/22 周一574.4 对偶图v1v2v3v4v5v6v1*v2*v3*2024/4/22 周一584.4 对偶图性质性质4.5.5 设设 C 是平面图是平面图G的一个初级回路，的一个初级回路，S*是是G*中与中与C的各边的各边ei对应的边对应的边ei*的集合，则的集合，则S*是是G*的一个割集。的一个割集。证明：证明：C把把G的域分成了两部分，因此的域分成了两部分，因此E(G*)S*把把G*的结点分成不连通的两部分。由的结点分成不连通的两部分。由G*是连通图，是连通图，G*被分开的两部分都是连通的，因此被分开的两部分都是连通的，因此S*是是G*的一的一个割集。个割集。2024/4/22 周一594.4 对偶图v1v2v3v4v5v4*v1*v2*v3*C v1 v2 v32024/4/22 周一604.4 对偶图v4*v1*v2*v3*C v1 v2 v3S*v2*v3*,v2*v3*,v2*v4*,2024/4/22 周一614.4 对偶图例例 4.5.3 设设 i 和和 j 是平面连通图无限域边界上的两是平面连通图无限域边界上的两个结点，求个结点，求G中分离中分离 i 和和 j 的所有割集。的所有割集。ij解：在解：在G的无限域中添入边的无限域中添入边(i,j),得到图得到图G1。G G1作作G1的对偶图的对偶图G1*。2024/4/22 周一624.4 对偶图则则G1*中除边中除边(i,j)之外的从之外的从i 到到 j 的初级道路所对应的的初级道路所对应的G的诸边都的诸边都构成构成G中分离中分离i 和和 j的割集。的割集。ijij例例 4.5.3 设设 i 和和 j 是平面连通图无限域边界上的两是平面连通图无限域边界上的两个结点，求个结点，求G中分离中分离 i 和和 j 的所有割集。的所有割集。ij解：在解：在G的无限域中添入边的无限域中添入边(i,j),得到图得到图G1。作作G1的对偶图的对偶图G1*。2024/4/22 周一634.4 对偶图例例 4.5.3 设设 i 和和 j 是平面连通图无限域边界上的两是平面连通图无限域边界上的两个结点，求个结点，求G中分离中分离 i 和和 j 的所有割集。的所有割集。解：在解：在G的无限域中添入边的无限域中添入边(i,j),得到图得到图G1。作作G1的对偶图的对偶图G1*。则则G1*中除边中除边(i,j)之外的从之外的从i 到到 j 的初级道路所对应的的初级道路所对应的G的诸边都的诸边都构成了构成了G中分离中分离i 和和 j的割集。的割集。ijij2024/4/22 周一644.4 对偶图四色猜想四色问题四色猜想四色问题 任何一张地图都可以最多用四种颜色着色，使任何一张地图都可以最多用四种颜色着色，使得具有共同边界的国家染上不同的颜色。简称为得具有共同边界的国家染上不同的颜色。简称为地图是地图是4可着色的可着色的。这里具有共同边界这里具有共同边界是指有一整段共同边界。是指有一整段共同边界。2024/4/22 周一654.4 对偶图四色猜想来自英国四色猜想来自英国,1852年由格里斯兄弟提出年由格里斯兄弟提出,1872年由数学家凯利正式向倫敦数学学会提出年由数学家凯利正式向倫敦数学学会提出,从而成为从而成为世界数学难题。世界数学难题。1976年年6月哈肯和阿佩尔在美国伊利诺斯大学用两月哈肯和阿佩尔在美国伊利诺斯大学用两台不同的电子计算机，花了台不同的电子计算机，花了1200个小时，作了个小时，作了100亿次判断，完成了亿次判断，完成了四色定理四色定理的证明。的证明。2024/4/22 周一664.4 对偶图用用1，2，3，4代表四种染色代表四种染色111222342024/4/22 周一674.4 对偶图一张地图可看成是一个平面图一张地图可看成是一个平面图G。作作G的对偶图的对偶图G*111222232024/4/22 周一684.4 对偶图对平面图地图对平面图地图G的的域域的着色可看成是的着色可看成是G的对偶图的对偶图G*的的结点结点的着色。的着色。111222232024/4/22 周一694.4 对偶图5色定理定理定理 4.5.2 每一个平面图每一个平面图G的结点是的结点是5可着色的。可着色的。证明：由于自环和重边不影响结点染色。所以可移去证明：由于自环和重边不影响结点染色。所以可移去G中的自环和重边，得到简单平面图中的自环和重边，得到简单平面图G0。2024/4/22 周一704.4 对偶图5色定理定理定理 4.5.2 每一个平面图每一个平面图G的结点是的结点是5可着色的。可着色的。证明：对证明：对G0的结点数用归纳法证明。的结点数用归纳法证明。当结点数当结点数 n 5时，结论显然成立；时，结论显然成立；设当简单平面图设当简单平面图G0 的结点数是的结点数是n1时结论成立。时结论成立。现设现设G0是有是有 n 个结点的简单平面图。个结点的简单平面图。由定理由定理4.2.2，G0中存在结点中存在结点v，d(v)6。在。在G0中移去中移去结点结点v后得到的图是后得到的图是G0，即，即G0 G0v。由归纳假设，。由归纳假设，G0 的结点是可的结点是可5可着色的。可着色的。2024/4/22 周一714.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-着着色色。2024/4/22 周一724.5 对偶图vv2024/4/22 周一732024/4/22 周一744.4 对偶图5色定理定理定理 4.5.2 每一个平面图每一个平面图G的结点是的结点是5可着色的。可着色的。证明：如果证明：如果G0中，结点中，结点v的邻点恰好用了的邻点恰好用了5种颜色，种颜色，比如比如1,2,3,4,5。2024/4/22 周一752024/4/22 周一764.4 对偶图5色定理定理定理 4.5.2 每一个平面图每一个平面图G的结点是的结点是5可着色的。可着色的。证明：设在证明：设在G0 的着色中，的着色中，G0中与结点中与结点v邻接的着邻接的着颜色颜色 i 的结点记为的结点记为vi。设设G13是是G0 G0v的由着颜色的由着颜色1和和3的结点导出的结点导出的子图。的子图。2024/4/22 周一772024/4/22 周一784.4 对偶图5色定理定理定理 4.5.2 每一个平面图每一个平面图G的结点是的结点是5可着色的。可着色的。证明：若证明：若v1和和v3分别属于分别属于G13的不同连通支，则将的不同连通支，则将v1所在的连通支的各结点着的颜色所在的连通支的各结点着的颜色1和和3对换。对换。对换后，在对换后，在G0 的结点的结点5着色着色中，中，G0 的结点的结点v 的的邻点邻点没有用到颜色没有用到颜色1，所以在，所以在G0中可用颜色中可用颜色1 给结点给结点v着色，着色，得得G0的的结点结点5-着色着色。2024/4/22 周一794.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的道路。的道路。2024/4/22 周一804.5 对偶图2024/4/22 周一814.4 对偶图5色定理定理定理 4.5.2 每一个平面图每一个平面图G的结点是的结点是5可着色的。可着色的。证明：在证明：在G0 G0v的由着颜色的由着颜色2和和4的结点导出的的结点导出的子图子图G24 中中，v2和和v4分别属于分别属于G24的不同连通支的不同连通支。则将。则将v2所在的连通支的各结点着的颜色所在的连通支的各结点着的颜色2和和4对对换。对换后，在换。对换后，在G0 的结点的结点5着色着色中，中，G0 的结的结点点v 的的邻点邻点没有用到颜色没有用到颜色2，所以在，所以在G0中可用颜中可用颜色色2 给结点给结点v着色，着色，得得G0的的结点结点5-着色着色。2024/4/22 周一824.2极大平面图推论推论4.2.1设有设有n个结点和个结点和m条边的任意简单平面图条边的任意简单平面图G满满足足 m 3n6，d 2n4证明：设证明：设G的域的边界数分别为的域的边界数分别为E1,E2,Ed，由，由G中中没有自环和重边，所以没有自环和重边，所以 Ei 3，1 i d。如果如果G中没有割边，则中没有割边，则 E1E2Ed2m，若若G有割边，则有割边，则E1E2Ed 2m。总之有总之有 2m E1E2Ed 3d。代入欧拉公式即得。代入欧拉公式即得。2024/4/22 周一834.4 图的平面性检验设设H是是G的的可平面子图可平面子图，如果在，如果在GH中存在另一中存在另一个个G的的平面子图平面子图B，且，且B与与H有有2个以上共同结点，个以上共同结点，则称则称B是是G中中H的的片片，片片B与与H的公共结点称为的公共结点称为片片B的的附着点附着点。2024/4/22 周一844.4 图的平面性检验例例4.4.2 在图在图G中，令中，令H是回路是回路(v1,v2,v3,v4)，则，则H是是G的可平面子图。的可平面子图。v1v2v3v4v5G2024/4/22 周一85 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；v1v2v3v4v4v1v2v3v1v2v3v4v5B1B2B32024/4/22 周一864.4 图的平面性检验可平面子图可平面子图H的的片片2024/4/22 周一874.4 图的平面性检验命题：命题：设设H是图是图G的一个的一个可平面子图可平面子图，H是子图是子图H的的一个平面嵌入，令一个平面嵌入，令B是是G中中H的的片片。则只有当。则只有当片片B的的所有附着点都在所有附着点都在 H 的某个面的某个面 f 的边界上时，片的边界上时，片B才才能画在能画在 H 的一个面内。的一个面内。v1v2v3v4v4v1v2v3v1v2v3v4v5B1B2B32024/4/22 周一884.4 图的平面性检验设设H是例是例4.4.2 的子图的子图H的一个平面嵌入。的一个平面嵌入。片片B1(v2,v4)画在画在 H 的内部面上，得到的子图的内部面上，得到的子图是是H1，H1的平面嵌入是的平面嵌入是 H1。v4v1v2v3B1H12024/4/22 周一894.4 图的平面性检验此时，片此时，片B2 的所有附着点都位于的所有附着点都位于 H1 的外部面的的外部面的边界上。把边界上。把B2画在画在 H1 的外部面上得到子图的外部面上得到子图 H2。H2的平面嵌入是的平面嵌入是 H2。v4v1v2v3B1H2B22024/4/22 周一904.4 图的平面性检验这时，这时，H2 里不存在一个面，它的边界包含里不存在一个面，它的边界包含B3 的的所有附着点。所有附着点。B3 不能平面嵌入到不能平面嵌入到 H2的某个面内。的某个面内。所以所以G不是可平面图不是可平面图。v4v1v2v3B1H2B2v1v2v3v4v5B3v1v2v3v4v5G2024/4/22 周一914.4 图的平面性检验片的移动片的移动2024/4/22 周一924.4 图的平面性检验用用F(B,H)表示片表示片B可平面嵌入的可平面嵌入的 H 的所有面的的所有面的集合。集合。例如例例如例4.4.2中中 F(B1,H)f1,f2v4v1v2v3B1f1f2v4v1v2v3B1f1f22024/4/22 周一934.4 图的平面性检验平面性检验的平面性检验的DMP算法：算法：1.找找G的一个回路的一个回路C。2.i 1。3.G1 C,G1 C 。4.f 2。5.EMBEDDABLE true。6.While f m n2 and EMBEDDABLE do begin2024/4/22 周一944.4 图的平面性检验 7.找找G关于关于Gi的每一个片的每一个片B。8.对每一个片对每一个片B，求，求 F(B,Gi)。9.若对某一个片若对某一个片B，F(B,Gi)。EMBEDDABLE false；G是非平面图，结束。是非平面图，结束。10.若若 EMBEDDABLE 则。则。begin2024/4/22 周一954.4 图的平面性检验11.if 对某个对某个B，|F(B,Gi)|1 then F F(B,Gi)，else 令令B是任一片且是任一片且F是满足是满足F F(B,Gi)的任一面。的任一面。2024/4/22 周一964.4 图的平面性检验 12.找一条路径找一条路径Pi B，Pi的两个端结点是的两个端结点是B在在Gi的附着的附着点。点。13.Gi1 Gi Pi。14.将将Pi画到画到Gi的面的面F内，得到内，得到Gi1的平面嵌入的平面嵌入Gi1。15.i i1。16.f f1。17.若若 f m n2，G是可平面图。是可平面图。end end2024/4/22 周一974.4 图的平面性检验2024/4/22 周一982024/4/22 周一994.4 图的平面性检验2024/4/22 周一1002024/4/22 周一1014.4 图的平面性检验2024/4/22 周一1024.4 图的平面性检验