图论平面图与图的着色VIP免费

第四章平面图与图的着第四章平面图与图的着色色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，则m≤t(n-2)/(t-2)4.2极大平面图Def4.2.1：设G是n≥3的简单平面图，如果在任意两个不相邻的结点之间加入一条边，就会破坏图的平面性，则该G为极大平面图。极大平面图的性质：1.G是连通的；2.G不存在割边；3.G的每个域的边界都是3。Th4.2.1极大平面图G中:m=3n-6d=2n-4Cor4.2.1简单平面图满足m≤3n-6d≤2n-4Th4.2.2：简单平面图G中存在度小于6的结点。4.3非平面图Th4.3.1k5和k3.3不是平面图。Def4.3.1如果两个图能够从一个图G出发，通过在G的边上插入有限多个2次顶点得到，则称这两个图是同胚。Th4.2：一个图为平面图当且仅当它不含与k5或k3.3同胚的子图。4.4图的平面性检测预处理见书P73块：如果G中存在割点v，这时可把图G从割点处分离，构成若干个不含割点的连通子图，称为块。片：设H是G的子图，e1，e2E(G)-E(H)，若存在一条路径W，使得：1）W的首尾两条边分别是e1，e2；2）W的内点和V(H)不相交，则说e1~e2。在~下的每个等价类的诱导子图称为G中H的片。DMP算法见书4.5对偶图对偶图(dualgraph)：任意一个平面图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色素与色素多项式Def4.6.1:G为k可着色的：设G是一个无自环图，如果对它的每个顶点可以用k种颜色之一着色，使得没有两个相邻的顶点有相同的颜色，则称G是k可着色的。Def4.6.2:G为k色图(kChromatic)：设G是一个无自环图，如果G为k可着色的，但不是k-1可着色的，则称G为k色图或称G的色数(chromaticnumber)为k，记为：X(G)。Def4.6.3:G是k可边着色的：如果图G的所有的边皆可用k种颜色着色，使得任何两条相邻的边均具有不同的颜色，则称G是k边着色的。Def4.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))Def4.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着色(两次不同着色，是指至少一个点的着色不同)数目。ijijeGGijoGoVoEoVoEijGijoGTh4.6.5:设i，j是简单图G不相邻的两个结点，则f(G,t）=f(,t)+f(,t)。ijoGijG作业：P871,2,3,41),61),7