资源描述：
《第8章 图论 topics in graph theory11月25日周二》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第8章图论TopicsinGraphTheory§8.6染色图ColoringGraphs平面图planargraphagraphcanbedrawninaplanesothatnoedgescrossexceptatverticesK5,K3,3不是平面图平面图的面：内部面，外部面，有限面，无限面。面的边界：包围这个面的回路（不一定是简单回路）。面的次数次数deg(R)=边界的长度。非连通平面图有一个公共外面，边界由k个回路组成，k＝p(G).平面图每条边都是两个面的交线。一条边处于一个内部面中或一个外部面中
2、，面的次数要计算两次。定理1.平面图的所有面的次数之和等于边数的两倍：极大平面图：简单平面图，增加一边就不是平面图。极小非平面图：简单非平面图，减少一边就是平面图。定理2.n阶极大平面图的性质：（1）连通。（2）n≥3时，每个面Ri，deg(Ri)=3.（3）n≥4时，每个顶点v：D(v)≥3。定理3.欧拉定理：满足n－m＋r＝2，任意连通平面图G，满足n－m＋r＝2，即，顶点数－边数＋面数＝2。证明.对边数归纳：m＝0，1，2，3显然。增加一边：增加一个顶点，不增加面。不增加顶点，增加一面。推论4.任意连通度
3、为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－2lm≤。定理6.简单连通平面图G中至少有一点v，D(v)≤5.证明.假设任意顶点v，D(v)≥6.6n≤2m，3r≤2m3n≤mn－m＋r＝26＝3n－3m＋3r≤m－3m＋2m＝0这不可能。定理7.（库拉图斯基定理）一个图G是平面图当且仅当G没
4、有可以收缩到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=4l/(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=1
5、2,正12面体2）d＝4.n=2l/(4－l).l=3,n=6,m=12,r=8,正八面体。3）d＝5.n=4l/(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
6、的顶点数等于G*的面数,r*=n.G不连通，则G的顶点数等于G*的面数,r*=n－p(G)＋1.G和G*不同构，同构图的对偶图不一定同构。G**不一定同构于G。不连通图的对偶图连通，连通图的对偶图连通。若G@G*，就称G是自对偶的图。染色图colouringGraph一个图用彩色将每个顶点着色，相邻顶点染不同颜色。一个平面图用彩色将每个面着色，相邻面染不同颜色。只要换成其对偶图即可。平面图G最少用k种颜色染色，就称为k色图。k称为chromaticnumberofG.记做χ(G)四色定理：任何一个平面图都是四色
7、图。染色多项式chromaticpolynomial用n种颜色染一个图，有多少不同的方法,记做PG(n).PG是一个多项式函数，称为chromaticpolynomialofG.例4.设L4是4个顶点的一条线。用x种颜色，第一点，x种方法着色，第二点x－1种方法着色。第三第四点都是x－1。PL4(x)=x(x-1)3.χ(L4)＝2。例5．PKn(x)＝x(x-1)(x-2)……(x-n+1)=[x]n.χ(Kn)＝n。定理1.设G1，G2，……，Gm是G的连通分量，则PG(x)=PG1(x)PG2(x)……P
8、Gm(x)。χ(G)＝max{χ(G1),χ(G2),……，χ(Gm)}例6.G是两个不相连三角形，PG(x)=x2(x-1)2(x-2)2.例7.G是n个不相连顶点，PG(x)=xn。Ge是G去掉e导出的子图，Ge是将e的两端点粘合得到的图。定理2.PG(x)＝PGe(x)－PGe(x)证明.设e的端点为a，b。G着色必须将ab着不同色。Ge着色必须将ab着同色。Ge着色a，b可着同
