图论平面图与图的着色.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）= 2Th4.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着色(两次不同着色，是指至少一个点的着色不同)数目。ijijeGGijoGoVoEoVoEijGijoGTh4.6.5:设i，j是简单图G不相邻的两个结点，则f(G,t）= f( ,t)+f( , t )。ijoGijG作业： P87 1, 2, 3 , 4 1) ,6 1),7
