第8章图论TopicsinGraphTheory11月25日周二

第8章图论TopicsinGraphTheory§8.6染色图ColoringGraphs平面图planargraphagraphcanbedrawninaplanesothatnoedgescrossexceptatverticesK5,K3,3不是平面图平面图的面：内部面，外部面，有限面，无限面。面的边界：包围这个面的回路（不一定是简单回路）。面的次数次数deg(R)=边界的长度。非连通平面图有一个公共外面，边界由k个回路组成，k＝p(G).平面图每条边都是两个面的交线。一条边处于一个内部面中或一个外部面中，面的次数要计算两次。定理1.平面图的所有面的次数之和等于边数的两倍：iideg(R)2m极大平面图：简单平面图，增加一边就不是平面图。极小非平面图：简单非平面图，减少一边就是平面图。定理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.任意连通度为k的平面图G，满足n－m＋r＝k＋1。不满足欧拉公式的简单图不是平面图。请验证K5，K3,3，不是欧拉图。定理5.设G是连通平面图，每个面的次数至少l，（l≥3），则m≤(2)2lnl。证明.2m≥lr，n－m＋r＝2，ln－lm＋2m≥ln－lm＋lr＝2l，lm－2m≤ln－2lm≤(2)2lnl。定理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没有可以收缩到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=12,正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的顶点数等于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)四色定理：任何一个平面图都是四色图。染色多项式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)……PGm(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可着同色，可着不同色。PGe(x)＝PG(x)+PGe(x).例G如下图。PGe(x)=x2(x-1)2(x-2)2,PGe(x)=x(x-1)2(x-2)2,PG(x)=PGe(x)－PGe(x)=x2(x-1)2(x-2)2－x(x-1)2(x-2)2＝x(x-1)3(x-2)2,χ(G)=3,G是3色图。引理3.设G是简单图，G已染色，相邻顶点颜色不e同。G中染色αβ两种颜色的顶点导出子图为Gαβ.交换Gαβ中一个连通分量中染色α和β，G仍然保持相邻顶点不同颜色。证明.G中任意相邻两点a，b.bGαβ，或a，b∈Gαβ，或a∈Gαβ且bGαβ，a，b染色仍然不同。定理4（五色定理）G是任意一个平面图,则χ(G)≤5。证明.对G的顶点个数归纳。G中至少有一点a，D(a)≤5。归纳假设去掉a，导出的子图G’可以用5重颜色着色。如果a只与G’中4个点相邻，a可以用第五种颜色着色。如果a与G’中5个点相邻，但5点中有重复颜色，a可以用第五种颜色着色。假设a与G’中5个点相邻，5点着色各不相同，5点分别是b1，b2，……，b5。设b1着色α，b2着色β，而b1，b2，不在Gαβ的同一个连通分量中。由引理3，交换b3所在分量中颜色α和β，可以使b1，b3着色相同。这时a可着色。设b1着色α，b3着色β，而b1，b3在Gαβ的同一个连通分量中。这时b1到b2有一条着色αβ相间的链。与a形成一条回路，组成一个面。b2在这个面的内部或在外部。如果同样b2，b4；b3，b5；b3，b5；b2，b5；b1，b4都有一个这样的链，相互交叉。这时a，b1，b2，b3，b4，b5组成一个K5。与G是平面图矛盾。这是不可能的。HomeworkPP31514，18，20，22补.证明球面多边形至少有一个面的次数小于等于5。