图论平面图与图的着色.ppt
第四章 平面图与图的着色,4.1 平面图4.2 极大平面图4.3非平面图4.4图的平面性检测4.5 对偶图4.6色素与色素多项式,4.1 平面图平面图：指的是画在平面上的一个图形，它的所有的边都不相交（除顶点外）。可(嵌入)平面图：如果一个图经过重画之后，可以画成平面上的一个边不相交的图形，则该图便称为平面图（可嵌入平面(embeding)）。G的一个面或域：G是一个平面图，由它的若干条边所构成的一个区域内如果不含任何结点及边，称该区域为一个面或域。,无穷面Th4.1.1：设是一个连通的平面图，n，m和d分别表示图的顶点数，边数和面数，则n-m+d=2。Cor4.1.1：设为具有n个顶点，m条边，f个面和k个分图的平面上的图，则n-m+f=k+1。Th4.1.2：设平面连通图G没有割边，且每个域的边界至少是t，则 mt(n-2)/(t-2),4.2 极大平面图Def4.2.1：设G是n3的简单平面图，如果在任意两个不相邻的结点之间加入一条边，就会破坏图的平面性，则该G为极大平面图。极大平面图的性质：1.G是连通的；2.G不存在割边；3.G的每个域的边界都是3。Th4.2.1 极大平面图G中:m=3n-6 d=2n-4Cor4.2.1简单平面图满足 m3n-6 d2n-4Th4.2.2：简单平面图G中存在度小于6的结点。,4.3非平面图Th4.3.1 k5和k3.3不是平面图。Def4.3.1 如果两个图能够从一个图G出发，通过在G的边上插入有限多个2次顶点得到，则称这两个图是同胚。Th4.2：一个图为平面图当且仅当它不含与k5或k3.3同胚的子图。,4.4 图的平面性检测预处理见书P73块：如果G中存在割点v，这时可把图G从割点处分离，构成若干个不含割点的连通子图，称为块。片：设H是G的子图，e1，e2E(G)-E(H)，若存在一条路径W，使得：1）W的首尾两条边分别是e1，e2；2）W的内点和V(H)不相交，则说e1e2。在下的每个等价类的诱导子图称为G 中H的片。DMP算法见书,4.5 对偶图对偶图(dual graph)：任意一个平面图G，如果：1）在G 的每个面Fi中选定一个点vi*作为顶点；2）对应于G的每条边e，画一条线e*，它只与e相交，而不与G的其它边相交，并且连接位于e两边的面Fi中的顶点vi*作为边。这样构成的图称为图G的对偶图，记为G*。Note:1）G中的每个悬点都产生G*的一个自环；2）G中多于一条公共边的面，便产生多重边；3）H G 但是H*G*不一定；4）G*是连通的且为可平面嵌入的。,Th4.5.1：设G为n，m和f且为平面上的连通图，其对偶图G*有n*，m*和f*n*=d，m=m*和n=d*。Th4.5.2：设G为连通平面图，则G*G。Th4.5.3：设G有对偶图G为平面图。,地图：不含桥的连通平面上的图。地图为k可面着色的：如果它的每个面都可以用k种颜色之一去着色，使得任何两个相邻的面(即有公共边的面)都有不同的颜色。Th4.5.4 每个平面图都是5可面着色的。Th4.5.5：如果每个3正规的地图是4可面着色的，则4色定理成立。,4.6色素与色素多项式Def 4.6.1:G为k可着色的：设G是一个无自环图，如果对它的每个顶点可以用k种颜色之一着色，使得没有两个相邻的顶点有相同的颜色，则称G是k可着色的。Def 4.6.2:G为k色图(k Chromatic)：设G是一个无自环图，如果G为k可着色的，但不是k-1可着色的，则称G为k色图或称G的色数(chromatic number)为k，记为：X(G)。Def 4.6.3:G是k可边着色的：如果图G的所有的边皆可用k种颜色着色，使得任何两条相邻的边均具有不同的颜色，则称G是k边着色的。Def 4.6.4:k为G的边色数：如果G为k可边着色的，但不是k-1可边着色的，则称k为G的边色数，记为：X(G)。,特别图的色素：1、G为空图 X(G）=12、G为kn完全图，则X(G）=n3、G为kn-e图，则X(G）=n-14、G为二部图，则X(G）=25、G为2n点的回路，则X(G）=26、G为2n+1点的回路，则X(G）=37、G为n（2）点的树，则X(G）=2,Th4.6.1:一个非空图：X(G）=2 G 无奇回路Th4.6.2:平面连通图G的域可2面着色 G为欧拉图。Th4.6.3:对于任意图G，X(G）do+1(do=max(d(vi)Def 4.6.5:设i，j是简单图G不相邻的两个结点。令=（，）（=V-i,j+ij，=E-(k,i)|(k,i)E-(k,j)|(k,j)E+(k,ij)|(k,i)E或(k,j)E)Th4.6.4:设i，j是简单图G不相邻的两个结点，则X(G）=min X(),X()。Def4.6.6:f(G,t)表示G的不同的k着色(两次不同着色，是指至少一个点的着色不同)数目。,Th4.6.5:设i，j是简单图G不相邻的两个结点，则f(G,t）=f(,t)+f(,t)。,作业：P87 1,2,3,4 1),6 1),7,
