平面图及着色.ppt

《平面图及着色.ppt》由会员分享，可在线阅读，更多相关《平面图及着色.ppt（57页珍藏版）》请在优知文库上搜索。

1、第四章第四章 平面图平面图第一节 平面图定义1 如果图G能示画在曲面S上且使得它的边仅在端点处相交，则称G可嵌入曲面S。如果G可嵌入平面上，则称G是是可平面图可平面图，已经嵌入平面上的图 称为G G的平面表示的平面表示。 可平面图G与G的平面表示 同构，都简称为平面图。(球极投影)GG定理定理1 1 图图G G可嵌入球面可嵌入球面图图G G可嵌入平面。可嵌入平面。例例1 Q1 Q3 3是否可平面性？是否可平面性？定义定义2 (2 (平面图的面平面图的面, ,边界和度数边界和度数). ). 设设G G是一个平面图，由是一个平面图，由G G中的边所包围的区域，中的边所包围的区域，在区域内既不包含在

2、区域内既不包含G G的结点，也不包含的结点，也不包含G G的边，的边，这样的区域称为这样的区域称为G G的一个面的一个面。有界区域称为有界区域称为内内部面部面，无界区域称为，无界区域称为外部面外部面。包围面的长度最。包围面的长度最短的闭链称为短的闭链称为该面的边界该面的边界。面的边界的长度称。面的边界的长度称为为该面的度数该面的度数。例例2 2 指出下图所示平面图的面、面的边界及指出下图所示平面图的面、面的边界及面的度数。面的度数。e61234567e1e2e3e4e5e7e8e10e9f1f4f3f2f5解解: :面面f f1 1, ,其边界其边界1e1e1 15e5e2 24e4e4 43

3、e3e7 72e2e10101,d(f1,d(f1 1)=5.)=5. 面面f f2 2, ,其边界其边界1e1e10102e2e8 87e7e9 91,d(f1,d(f2 2)=3.)=3. 面面f f3 3, ,其边界其边界2e2e7 73e3e6 67e7e8 82,d(f2,d(f3 3)=3.)=3. 面面f f4 4, ,其边界其边界3e3e4 44e4e5 57e7e6 63,d(f3,d(f4 4)=3.)=3. 外部面外部面f f5 5, , 其边界其边界1e1e1 15e5e2 24e4e3 36e6e3 34 e4 e5 57e7e9 91,d(f1,d(f5 5)=6.

4、)=6.定理定理2 2 对任何平面图对任何平面图G G，面的度数之和面的度数之和是是边数的二倍边数的二倍。证明证明: :对内部面而言对内部面而言, ,因为其任何一条非因为其任何一条非割割边同时在两边同时在两个面中个面中, ,故每增加一条边图的度数必增加故每增加一条边图的度数必增加2.2.对外部面的对外部面的边界边界, ,若某条边不同时在两个面中若某条边不同时在两个面中, , 边必为割边边必为割边, ,由于由于边界是闭链边界是闭链, ,则该边也为图的度数贡献则该边也为图的度数贡献2.2.从而结论成立从而结论成立. .定理定理3 3 设设G G是带是带v v个顶点，个顶点，e e条边，条边，r r

5、个面的连通的平个面的连通的平面图，则面图，则 v-e+rv-e+r=2=2。（欧拉公式）。（欧拉公式）证明证明:(1):(1)当当n=e=1n=e=1时时, ,如下图如下图, ,结论显然成立结论显然成立. .v=2,e=1,r=1v=1,e=1,r=2(2)下用数学归纳法证明下用数学归纳法证明. 假设公式对假设公式对n条边的图成立条边的图成立.设设G有有n+1条边条边.若若G不含不含圈圈,任取一点任取一点x,从结点从结点x开始沿路行走开始沿路行走.因因G不含圈不含圈,所以所以每次沿一边总能达到一个新结点每次沿一边总能达到一个新结点,最后会达到一个度数最后会达到一个度数为为1的结点的结点,不妨设

6、为不妨设为a,在结点在结点a不能再继续前进不能再继续前进.删除结删除结点点a及其关联的边得图及其关联的边得图G,G含有含有n条边条边.由假设公式对由假设公式对G成立成立,而而G比比G多一个结点和一条边多一个结点和一条边,且且G与与G面数相面数相同同,故公式也适合于故公式也适合于G. 若若G含有圈含有圈C,设设y是圈是圈C上的一边上的一边,则边则边y一定是两个一定是两个不同面的边界的一部分不同面的边界的一部分.删除边删除边y得图得图G,则则G有有n条边条边.由假设公式对由假设公式对G成立而成立而G比比G多一边和多一面多一边和多一面,G与与G得顶点数相同得顶点数相同.故公式也成立故公式也成立.推论

7、推论1 1 设设G G是带是带v v个顶点，个顶点，e e条边的连通的平面简条边的连通的平面简单图，其中单图，其中v v 3 3，则，则e e 3 3v-6v-6。证明证明: :由于由于G G是简单图是简单图, ,则则G G中无环和无平行边中无环和无平行边. .因此因此G G的任何面的度数至少为的任何面的度数至少为3.3.故故2e=2e= d(f)d(f) 3r (1)3r (1) 其中其中r r为为G G的面数的面数. .由欧拉公式由欧拉公式v-e+r=2v-e+r=2所以所以r=2-v+e,r=2-v+e,代入代入(1)(1)中有中有: :2e2e 3(3(2-v+e2-v+e) )即即e

8、 e 3 3v-6v-6。推论推论2 2 设设G G是带是带v v个顶点，个顶点，e e条边的连通的平面简单图，其条边的连通的平面简单图，其中中v v 3 3且没有长度为且没有长度为3 3的圈，则的圈，则e e 2 2v-4v-4。证明证明: :因为图因为图G G中没有长度为中没有长度为3 3的圈的圈, ,从而从而G G的每个面的度数的每个面的度数至少为至少为4.4.因此有因此有2e=2e= d(f)d(f) 4r (1)4r (1)其中其中r r为为G G的面数的面数. .由欧拉公式由欧拉公式v-e+r=2v-e+r=2所以所以r=2-v+e,r=2-v+e,代入代入(1)(1)中有中有:

9、:2e2e 4(4(2-v+e2-v+e) )即即e e 2 2v-4v-4。例例3 K3 K5 5和和K K3.33.3都是非平面图。都是非平面图。解解: :图图K K5 5有有5 5个顶点个顶点1010条边条边, ,而而3 3* *5-6=9,5-6=9,即即109,109,由由推论推论1 1知知,K,K5 5是非平面图是非平面图. . 显然显然K K3,33,3没有长度为没有长度为3 3的圈的圈, ,且有且有6 6个顶点个顶点9 9条边条边, ,因因而而9292* *6-4,6-4,由推论由推论2 2知知K K3,33,3是非平面图是非平面图. .推论推论3 3 设设G G是带是带v v

10、个顶点，个顶点，e e条边，条边，r r个面的平面图，个面的平面图，则则 v- e+ r=1+wv- e+ r=1+w。其中。其中w w为为G G的连通分支数。的连通分支数。证明证明: :由欧拉公式有由欧拉公式有: v: vi i- e- ei i+ r+ ri i=2(i=1,2,=2(i=1,2,w),w)从而有从而有 v vi i- - e ei i+ + r ri i =2w=2w又又 v vi i=v, =v, e ei i=e, =e, r ri i =r+(w-1)(=r+(w-1)(外部面被重外部面被重复计算了复计算了w-1w-1次次. .).).所以有所以有: :V-e+r+

11、(w-1)=2wV-e+r+(w-1)=2w整理即得整理即得: v- e+ r=1+w.: v- e+ r=1+w.推论推论4 4 设设G G是任意平面简单图，则是任意平面简单图，则 （G G） 5 5。证明证明: :设设G G有有v v个顶点个顶点e e条边条边. .若若e e 6,6,结论显然成立结论显然成立; ;若若e6,e6,假设假设G G的每个顶点的度数的每个顶点的度数 6,6,则由推论则由推论1,1,有有6v 6v 2e 2e 6v-126v-12矛盾矛盾, ,所以所以 （G G） 5.5.例例4 4 平面上有平面上有n n个顶点，其中任两个点之间的距离至少个顶点，其中任两个点之间

12、的距离至少为为1 1，证明在这，证明在这n n个点中距离恰好为个点中距离恰好为1 1的的点对数至多的的点对数至多是是3n-63n-6。证明证明: :首先建立图首先建立图G=,G=,其中其中V V就取平面上给定的就取平面上给定的n n个个点点( (位置相同位置相同),),当两个顶点之间的距离为当两个顶点之间的距离为1 1时时, ,两顶点两顶点之间用一条直线段连接之间用一条直线段连接, ,显然图显然图G G是一个是一个n n阶简单图阶简单图. . 由推论由推论1,只要证明只要证明G为一平面图时即知结论成立为一平面图时即知结论成立. 反设反设G中存在两条不同的边中存在两条不同的边a,b和和x,y相交

13、于非端点相交于非端点处处o,如下图如下图(a)所示所示,其夹角为其夹角为 (0 ). 若若 = ,这时如下图这时如下图(b),显然存在两点距离小于显然存在两点距离小于1,与已知与已知矛盾矛盾,从而从而0 .由于由于a到到b的距离为的距离为1,x到到y的距离为的距离为1,因此因此a,b,x,y中至少有两个点中至少有两个点,从交点从交点o到这两点的距离不到这两点的距离不超过超过1/2,不妨设为不妨设为a,x,则点则点a与与x之间的距离小于之间的距离小于1,与已知与已知矛盾矛盾,所以所以G中的边除端点外不再有其它交点中的边除端点外不再有其它交点,即即G为平面为平面图图.再据推论再据推论1,知结论成立

14、知结论成立.ayxbo (a)axby(b)第第2 2节节 库拉图斯基定理与极大平面库拉图斯基定理与极大平面定义定义1 1 设G是一个平面图，通过除G的一条边x、y,并增加一个新结点a和两条边x 、a与a、y（所获得的任何图也是平面图），这样的操作称为初等细分初等细分。若可以从相同的图G通过一系列初等细分来获得图G1和G2，称称G G1 1和和G G2 2是是同胚的同胚的. . 如下图G1,G2,G3是同胚的.G1G2G3定理定理1 1一个图一个图G G是非平面的，是非平面的，当且仅当当且仅当它包含一个同胚它包含一个同胚于于K K3.33.3或或K K5 5的子图。（证略）的子图。（证略）例例

15、1 1 说明彼得森图不是平面图。说明彼得森图不是平面图。解解: :删去下图删去下图(a)(a)皮得森图的结点皮得森图的结点b,b,得其子图得其子图(b)H.(b)H.而而H H胚于胚于K K3.33.3, ,所以皮得森不是平面图所以皮得森不是平面图. .fdjeihabcdefghij(a)faedighjc(b)H(c)K3,3说明说明: :库拉图斯基给出了平面图的充要条件库拉图斯基给出了平面图的充要条件, ,但用它并不能但用它并不能判别一个图是否是平面图的有效算法判别一个图是否是平面图的有效算法. .定义定义2 2设设G G是阶大于等于是阶大于等于3 3的简单可平面图，若在任意两个的简单可

16、平面图，若在任意两个不相邻的结点不相邻的结点v vi i,v,vj j之间加入边之间加入边vvi i,v,vj j ，就会破坏图的平，就会破坏图的平面性，则称面性，则称G G是极大平面图。极大平面图的平面表示称为是极大平面图。极大平面图的平面表示称为三角剖分平面图三角剖分平面图. .定理定理2.2.极大平面图的判别定理极大平面图的判别定理:v:v阶简单平面图阶简单平面图G G是极大平是极大平面图的充要条件是面图的充要条件是: :（1 1）G G中每个面的度数都是中每个面的度数都是3 3（2 2） G G中有中有e e条边条边r r个面，则个面，则3r=2e3r=2e（3 3）设）设G G带有带有v v个顶点，个顶点，e e条边，条边，r r个面则个面则 e=3v-6,r=2v-4.e=3v-6,r=2v-4.证明证明: :必要性必要性: :因因G G是简单图是简单图, ,故故G G中没有环和平行边中没有环和平行边, ,故不故不存在度数为存在度数为1 1或或2 2的面的面. .假设假设G G存在度数大于存在度数大于3 3的面的面f,f,不妨不妨设为内部面设为内部面, ,如下图如下图G,G