平面图与图的着色

《平面图与图的着色》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章平面图与图的着色4.1平面图定义4.1.1若能把图G画在一个平面上，使任何两条边都不相交，就称G可嵌入平面，或称G是可平面图。可平面图在平面的一个嵌入称为平面图。如果G是可平面图，那么它的任何导出子图也是可平面图。平面图定义4.1.2设G是一个平面图，由它的若干条边所构成的一个区域内如果不含任何结点及边，就称该区域为G的一个面或域。包围这个域的诸边称为该域的边界。为了讨论方便，我们把平面图G外边的无限区域称为无限域，其他的域都叫做内部域。如果两个域有共同的边界，就说它们是相邻的，否则是不相邻的。如果e不是割边

2、，它一定是某两个域的共同边界。平面图定理4.1.1设G是平面连通图，则G的域的数目是d=m–n+2。证明：G是连通图，有支撑树T，它包含n-1条边，不产生回路，因此对T来说只有一个无限域。由于G是平面图，每加入一条余树边，它一定不与其他边相交，也就是说一定是跨在某个域内部，把该区域分成两部分。这样，加入G的m-n+1条余树边，就生成了m-n+2个域。平面图推论4.1.1若平面图G有k个连通支，则n–m+d=k+1。推论4.1.2对一般平面图G，恒有n–m+d>=2。平面图定理4.1.2设平面连通图G没有割边，且每个

3、域的边界数至少是t，则m≤t×(n-2)/(t–2)证明：设G有d个区域，每个域的边界数至少是t，且每条边都与两个不同的域相邻。因此td≤2m。代入欧拉公式：(2m/t)≥m-n+2，即，m≤t×(n-2)/(t–2)。4.2极大平面图定义4.2.1设G是n>=3的简单平面图，若在任意两个不相连节点之间加入边就会破坏图的平面性，就称G是极大平面图。性质1G是连通的。性质2G不存在割边。性质3G的每个域的边界数都是3。极大平面图定理4.2.1极大平面图G中有m=3n-6,d=2n-4。证明：由极大平面图性质4，3d=

4、2m。代入欧拉公式d=m-n+2（性质1）。推论4.2.1简单平面图满足m<=3n-6,d<=2n-4。极大平面图例4.2.1若简单平面图G有6个节点12条边，则每个域的边界数都是3。例4.2.2若简单平面图不含K3子图，则有m<=2n-4。极大平面图定理4.2.2简单平面图G中存在度数小于6的结点。例4.2.3节点数不超过11的简单平面图G一定存在度数小于5的节点。例4.2.4K7图不是平面图。4.3非平面图如果图G不能嵌入平面，满足任意两边只能在结点处相交，那么G就称为非平面图这样，按平面性质进行划分，图G分为

5、两大类：可平面图和非平面图。非平面图定理4.3.1是非平面图。证明：在中，n=5，m=10。如果它是可平面图，应该有m≤3n-6。而此时3n-6=9，矛盾。定理4.3.2是非平面图。证明：假定是可平面图，由于n=6，m=9。由欧拉公式，d=5。但G中没有子图，因此4d≤2m，亦即20≤18，矛盾。非平面图约定和分别记为和图。定义4.3.1在和图上任意任意增加一些度为2的结点之后得到的图象为型和型图，统称为型图。定理4.3.3是可平面图的充要条件是不存在型图。4.5对偶图定义4.5.1满足如下条件的图G*称为G的对偶

6、图。G中每个确定的域内设置一个结点。对域和的共同边界，有一条边并与相交一次。若处于域之内，则有一自环与相交一次。对偶图性质4.5.1如果G是平面图，G一定有对偶图G*，而且G*是唯一的。由D过程即可得证。性质4.5.2G*是连通图。在平面G里，每个域f都存在相邻的域，而且对G的任何部分域来说，都存在与它们之中某个域相邻的域。这样由对偶图的定义可知G*连通。对偶图性质4.5.3若G是平面连通图，那么性质4.5.4平面连通图G与其对偶图G*的结点，边和域之间存在如下的对应关系：m=m*，n=d*，d=n*。对偶图性质4

7、.5.5若G是平面连通图的一个初级回路，S*是G*中与C的各边对应的的集合，那么S*是G*的一个割集。证明：Ｃ把Ｇ的域分成两部分，因此　　　　把G*的结点分成不连通的两部分，由性质4.5.2，G*两部分是分别连通的，因此那么S*是G*的一个割集。对偶图定理4.5.1G有对偶图的充要条件是G为平面图。定理4.5.2每一个平面图G都是5-可着色的。ThankYou