第8章 图论 Topics in Graph Theory11月25日周二.doc

第8章 图论 Topics in Graph Theory §8.6 染色图Coloring Graphs 平面图planar graph a graph can be drawn in a plane so that no edges cross except at vertices K5, K3,3 不是平面图 平面图的面：内部面，外部面， 有限面，无限面。 面的边界：包围这个面的回路（不一定是简单回路）。 面的次数次数deg(R)=边界的长度。 非连通平面图有一个公共外面，边界由k个回路组成，k＝p(G). 平面图每条边都是两个面的交线。 一条边处于一个内部面中或一个外部面中，面的次数要计算两次。 定理1. 平面图的所有面的次数之和等于边数的两倍： 极大平面图：简单平面图，增加一边就不是平面图。 极小非平面图：简单非平面图，减少一边就是平面图。 定理2. n阶极大平面图的性质： 连通。 n≥3时，每个面Ri，deg(Ri)=3. n≥4时，每个顶点v：D(v)≥3。 定理3. 欧拉定理：满足n－m＋r＝2， 任意连通平面图G，满足n－m＋r＝2， 即，顶点数－边数＋面数＝2。 证明. 对边数归纳： m＝0，1，2，3显然。 增加一边：增加一个顶点，不增加面。 不增加顶点，增加一面。 推论4. 任意连通度为k的平面图G，满足n－m＋r＝k＋1。 不满足欧拉公式的简单图不是平面图。 请验证K5，K3,3，不是欧拉图。 定理5. 设G是连通平面图，每个面的次数至少l，（l≥3），则m≤ 。 证明. 2m≥lr， n－m＋r＝2， ln－lm＋2m≥ ln－lm＋lr＝2l， lm－2m≤ln－2l m≤。 定理6. 简单连通平面图G中至少有一点v， D(v)≤5. 证明. 假设任意顶点v，D(v)≥6. 6n≤2m，3r≤2m 3n≤m n－m＋r＝2 6＝3n－3m＋3r≤m－3m＋2m＝0 这不可能。 定理7.（库拉图斯基定理） 一个图G是平面图当且仅当G没有可以收缩到K5或K3,3的子图。 每个凸多面体都可以映射到平面图。 定理8. 正多面体只有正4，6，8，12，20面体五种。 证明. 设G是一个正多面体， n个顶点，m条边，r个面， 每个顶点d度，每个面l次。 由定理6，3≤d≤5。 l≥3。 dn＝2m，lr=2m＝dn. n－m＋r=2， 2ln－2lm＋2lr=4l， 2ln－dln＋2dn=4l， n=4 l /(2l－dl＋2d)， 1）d＝3. n=4l/(6－l) l=3, n=4, m=6, r=4. 正四面体 l＝4，n＝8，m=12, r=6, 正六面体. l＝5，n＝20，m=30, r=12, 正12面体 2）d＝4. n=2 l /(4－ l). l =3, n=6, m=12, r=8, 正八面体。 3）d＝5. n=4 l /(10－3l). l＝3，n＝12， m＝30，r＝20 正20面体。 对偶图： 设G＝(T,V)是平面图， （1）G的每个面Ri中取一点vi*， V*={v1*，v2*，……，vr*} （2）若两个面Ri，Rj有公共边界ek，连接vi*，vj*，得到边ek*， E*={ e1*，e2*，……，em*} 则得到G*=(V*,E*)称为G的对偶图。 G和G*边数相同，m*＝m; G的面数等于G*的顶点数，n*=r; G连通，则G的顶点数等于G*的面数, r*=n. G不连通，则G的顶点数等于G*的面数, r*=n－p(G)＋1. G和G*不同构，同构图的对偶图不一定同构。G**不一定同构于G。 不连通图的对偶图连通，连通图的对偶图连通。 若G(G*，就称G是自对偶的图。 染色图colouring Graph 一个图用彩色将每个顶点着色，相邻顶点染不同颜色。 一个平面图用彩色将每个面着色，相邻面染不同颜色。只要换成其对偶图即可。 平面图G最少用k种颜色染色，就称为k色图。 k称为chromatic number of G. 记做χ(G) 四色定理：任何一个平面图都是四色图。 染色多项式chromatic polynomial 用n种颜色染一个图，有多少不同的方法,记做PG(n). PG是一个多项式函数，称为chromatic polynomial of G. 例4. 设L4是4个顶点的一条线。用x种颜色，第一点，x种方法着色，第二点x－1种方法着色。第三第四点都是x－1。 PL4(x)=x(x-1)3. χ