08-图论-离散数学讲义-海南大学(共十一讲)

08-图论-离散数学讲义-海南大学(共十一讲)LtD8.图论TopicsinGraphTheory§8.1图GraphsG=<V,E,γ>V={v1,v2,······,vn}顶点vertex集。E={e|e=(vi,vj),vi,vj∈V,vi≠vj}无向边edge集。γ(e)={vi,vj},e的端点endpoints集。简写为G＝（V，E）。TD(vi)顶点vi的度数degree：连接到vi的边的条数。连接一个顶点的圈loop算两度。孤立点isolatedvertex：度数为0的点。两个顶点相邻adjacent：有一边相连。定理1.(握手定理)TD＝TD(vi)=2m.推论.任意图的奇数度顶点必有偶数多个。完全图completegraph：任意两点都相邻简单图。定理2.n个顶点的完全图有n(n-1)/2条边。正则图regulargraph：每个顶点都有相同的度数。E={<vi,vj>|vi,vj∈V}有向边集有向图有向边<vi,vj>，割集：G的边集，去掉后G不连通。一条边组成的割集叫桥bridge。树的每条边都是桥。基本割集：生成树T中每一条边，和G中对应于T的所有的弦，组成一个割集，叫基本割集。最小生成树：权重最小的生成树。带权的边：带边长的边。带权的图：每边都带权。Prim算法：设G=<V,E>,1.令U={v0},T={}.2.对任意u∈U,v∈V-U,(u,v)∈E,找到权最小的边(u1,v1),令U=U∪{v1},T=T∪{(u1,v1)}3.重复2，直至U=V.得到T就是最小生成树。T中共有n-1条边Kruskal克鲁斯卡尔算法G=(V,E)连通图令T=(V,{})是G的所有顶点而无边的非连通图。选择E中权值最小的边，若该边连接T的两个连通分量，将它加入T,这时T的连通分量减少1；否则选下一条权值最小的边。重复1n-1次直到T连通。T就是最小生成树§8.2欧拉路径和欧拉回路哥尼斯堡七桥问题。一笔画问题。欧拉路径Eularpath：通过图的所有边，每个边恰好一次的路径。欧拉回路Eularcircuit：构成回路的欧拉路径。定理1.G有欧拉回路当且仅当G连通且没有奇数度顶点。定理2.G有欧拉路径当且仅当G连通且至多有两个奇数度顶点。§8.3Hamilton路径和Hamilton回路周游世界问题：每个城市访问一次只经过一次。Hamilton公爵提出是否存在一条回路通过正二十边形每个顶点恰一次。一个连通图GHamilton路径:经过每个顶点恰一次的路径。Hamilton回路：经过每个顶点恰一次的回路。Hamilton图：有Hamilton回路的图。完全图Kn，n>2，是Hamilton图。归纳可证。n个顶点的连通图G有Hamilton回路，G至少有n条边。用p(G)表示图G的连通分量的个数。定理1.G＝(V,E)是Hamilton图，则对任意V1V,p(G-V1)≤|V1|.证明：设C是G的一个Hamilton回路，V1都在C上。回路C中去掉V1中顶点，至多划分成|v1|段。因此p(C-V1)≤|V1|.例1.下图不是Hamilton图。引理2.n阶简单无向图G中，l：a……vivj……b，是一条有m个顶点的路径。a，b只与l中顶点相邻，D(a)+D(b)≥m。则l中所有顶点构成回路。证明.若a，b相邻，a……vivj……b是回路。设a，b不相邻。D(a)=s,D(b)=t.s+t≥m。t≥m－s。l中存在相连顶点vi，vj，avj相邻，bvi相邻，avj……bvi……a构成一个回路。定理3.n阶简单无向图G中，n>2,任意两个不相邻顶点的度数之和大于等于n－1，则G有Hamilton路径。证明.取G中最长路径：l：a……vi……vj……b。我们证明其长度为n－1，包含G的所有顶点，否则一定可以加长。b不与l外的顶点相邻，否则l可以加长。设l的长度≤n－2，l上共有顶点少于n－1个。a,b度数和大于n－1，由引理1.l的所有顶点组成回路。这时有一顶点c不在l上，cc必与l中一点vi相邻。我们得到含有顶点c，和l中所有顶点的路径，长度比l更长。推论4.n阶简单无向图G中，n>2,任意两个不相邻顶点的度数之和大于等于n，则G有Hamilton回路。证明.由定理3，G有Hamilton路径。由引理2，这条路径可以构成一条Hamilton回路。推论5.n阶简单无向图G中，n>2,任意顶点的度数大于等于n/2，则G有Hamilton回路。定理6.G有n个顶点，m条边，如果，则G是Hamilton图。证明.任取不相邻的两个顶点u，v∈G，G中去掉u，v后导出子图G’,G’有n－2个顶点，至多条边。u，v到G’的边数有D(u)+D(v)≥n.由推论4.G是Hamilton图。§8.4运输网络TransportNetworks§8.5匹配问题MatchingProblem二部图、偶图BipartiteGraph：无向图G＝(V,E),V=V1∪V2，V1∩V2＝。V1中顶点互不相邻，V2中顶点互不相邻，任意边连接V1，V2中各一个顶点。G=(V1,V2,E).完全二部图：V1中每个顶点与V2中每个顶点都相邻。|V1|=m,|V2|=n,完全二部图记做Km,n。K2,3,K3,3定理1.二部图中没有奇数长的回路。左边两图同构是K2,3，右边都是K3,3.E*E.E*中的边互不相连，称E*为G的一个匹配。边数最大的匹配叫最大匹配。邻接V1或V2中所有顶点的匹配叫完全匹配。|V1|=|V2|时，完全匹配也叫完美匹配。定理2.（Hall定理）设G=(V1,V2,E),|V1|≤|V2|.G中有完全匹配iffV1中任意k个顶点至少与V2中任意k个顶点相邻，即，任意XV1，|X|≤|R(X)|，R(X)为与X中顶点相邻的顶点的集合。证明.是显然的。对V1中顶点个数归纳：|V1|=1是显然的。设|V1|=k时定理成立。|V1|=k＋1：1）如果V1中任意k个顶点都至少与V2中k＋1个顶点相邻，从G中去掉一条边，V1中任意k个顶点都至少与V2中k个顶点相邻，存在完美匹配。2）如果V1中存在k个顶点只与V2中k个顶点相邻，例如{a1,a2,……，ak}V1，{b1,b2,……，bk}V2，{a1,a2,……，ak}只与{b1,b2,……，bk}相邻。则V1－{a1,a2,……，ak}任意s个顶点，都与V2－{b1,b2,……，bk}中s个顶点相连。两部分都有完美匹配。推论3.二部图G＝(V1,V2,E)中如果V1中每个顶点至少与V2中t条边相邻。V2中每个顶点至多与V1中t条边相邻。则G有完美匹配。证明.V1中任意k个顶点的总度数≥kt。V2中任意k个顶点的总度数≤kt。V1中任意k个顶点至少与V2中k条边相邻。由Hall定理，G有完美匹配。推论4.正则二部图必有完美匹配。§8.6染色图ColoringGraphs平面图planargraphagraphcanbedrawninaplanesothatnoedgescrossexceptatverticesK5,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－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没有可以收缩到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。不连通图的对偶图连通，连通图的对偶图连通。若GG*，就称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如下图。eePGe(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已染色，相邻顶点颜色不同。G中染色αβ两种颜色的顶点导出子图为Gαβ.交换Gαβ中一个连通分量中染色α和β，G仍然保持相邻顶点不同颜色。证明.G中任意相邻两点a，b.bGαβ，或a，b∈Gαβ，或a∈Gαβ且bGαβ，a，b染色仍然不同。定理4（五色定理）G是任意一个平面图,则χ(G)≤5。证明.对G的顶点个数归纳。G中至少有一点a，D(a)≤5。归纳假设去掉a，导出的子图G’可以用5重颜色着色。如果a只与G’中4个点相邻，a可以用第五种颜色着色。如果a与G’中5个点相邻，但5点中有重复颜色，a可