《图论复习题》PPT课件

第一章图和子图,图的基本概念；常见的特殊图类；二部图及其性质；图的同构；关联矩阵与邻接矩阵；路、圈与连通图；最短路问题。,K-方体图是其顶点为0与1的有序k元组,当且仅当它们的一个坐标不相同时,此两个顶点相连以边。证明k-方体图是有2k个顶点k2k-1条边的2-部图。,导出子图和图的运算,G2,G1,G2,G1,由定理1.2可知图(a)所示的图不是二分图，因为它包含一个长为3的圈,图(b)所示的图是一个二分图，它不含长为奇数的圈.,定理一个图是二部图当且仅当它不含奇圈。,证明：设P=v0v1vk是G的最长路。因为d(v0)3，所以存在两个与v1相异的顶点v,v与v0相邻。v,v必都在路P上，否则会得到比P更长的路。无妨设v=vi,v=vj,(i1时，找一个不连通的单图G使得,证：（a）若G不连通，可分为两个顶点数分别为,v1，v2的互不连通子图G1，G2。,（b）G=Kv-1+K1即为所求的单图。,课后习题：证明在任何两个或两个以上人的组内,存在两个人在组内有相同个数的朋友。,证：令上述组内人的集合为图G的顶点集合，若两人互相是朋友，则其间连以一边，所得之图G是组内人员的朋友关系图。显然G是单图，图中顶点的度恰表示该人在组内朋友的个数，利用图G，上述问题就抽象成如下的图论问题：在一个单图G中，若v（G）2，则在G中存在度相等的两个顶点。,用反证法，设G中各点的度均不相等。必有最大度v-1。若=v-1，必有1，从而-+1v-1,又与G是单图矛盾。,树及其基本性质；最小生成树。,第二章,定理下列命题等价：（1）G是树；（2）G中无环边且任二顶点之间有且仅有一条路；（3）G中无圈且=1；（4）G连通且=1;（5）G连通且对任何eE(G)，Ge不连通；（6）G无圈且对任何eE(G)，G+e恰有一个圈。,证明：（1）（2）G是树G连通u,vV(G)，存在路P(u,v)。,逆定理的成立见习题2.1.1,若还存在一条路P(u,v)P(u,v)，则必存在w，w是路P与P除了v之外最后一个公共顶点。,P的(w,v)段与P的(w,v)段构成圈，这与G是树矛盾。故只存在唯一的(u,v)路。,=1时，=0，结论真。假设k时结论真，我们来证明当=k+1时，也有=1成立。当=k+1时，任取u,vV(G)。考虑图G=Guv，因G中u、v间只有一条路，即边uv，故G不,（2）（3）若G有圈，则此圈上任二顶点间有两条不同的路，与前提条件矛盾。下面用归纳法证明=1。,连通且只有两个连通分支，设为G1,G2。注意到G1,G2分别都连通且任二顶点间只有一条路，由归纳法假设，,因此,归纳法完成。,（3）（4）用反证法。若G不连通，设G1,G2,Gw是其连通分支（w2），则（因Gi是连通无圈图，由已证明的(1)和(2)知，对每个Gi，(3)成立）。这样，这与矛盾。,（4）（5）(Ge)=(G)1=2，但每个连通图必满足1（见下列命题），故图Ge不连通。,=1,2时，1显然成立。假设k的连通图都1。对于=k+1的连通图H，任取vV(H)，考虑Hv。,若Hv连通，则由归纳假设，,(Hv)(Hv)1=k1，而,命题若图H连通，则(H)(H)1。,证明：对做数学归纳法。,(H)(Hv)+1(k1)+1=(k+1)1=(H)1。,若Hv不连通，设H1,H2,Hw是其连通分支,由归纳假设，故,而(H)(Hv)+w(kw)+w=(k+1)1,归纳法完成。,（w2）。,=(H)1。,（5）（6）先证G中无圈：若G中有圈，删去圈上任一边仍连通，矛盾。,再证G+e恰含一个圈：因G连通且已证G无圈，故G是树。由（2），任二顶点间仅有一条路相连，故G+e中必有一个含有e的圈；另一方面，若G+e中有两个圈含有e，则G+ee=G中仍含有一个圈，矛盾。,（6）（1）只需证G连通。任取u,vV(G)，若u、v相邻，则u与v连通。否则，G+uv恰含一个圈，故u与v在G中连通。由u、v的任意性，图G连通。定理证毕。,证明：设T是一个非平凡树。因T连通，故对每个顶点,vi，都有。若对所有vi都有，则,另一方面，,这两方面矛盾。故T至少有一个1度顶点，设为u。除此之外，其余1个顶点的度数之和为23。,若这些点的度都大于或等于2，则其度数之和2(1),推论2.2非平凡树至少含两个1度顶点（叶子）。,=22。这与23矛盾。故除u之外T还至少有一个度为1的顶点。证毕。,定义对图G，若V(G)的子集使得，则称为图G的一个顶点割集。含有k个顶点的顶点割集称为k-顶点割集。,注：（1）割点是1顶点割集。（2）完全图没有顶点割集。,第三章,图的连通性；割点、割边和块；边连通与点连通；连通度。,完全图的连通度定义为(K)=1。空图的连通度定义为0。,连通度：(G)=min|是G的顶点割集。,注：(1)使得的顶点割集称为G的最小顶点割集。,(2)若(G)k，则称G为k连通的。,(3)若G不连通，则(G)=0。,(4)若G是平凡图，则(G)=0。,(5)所有非平凡连通图都是1连通的。,例,1、分别找G1和G2两个顶点割；2、给出它们的连通度。,例,在2.2中为图G的一个边割集。含有k条边的边割集称为k-边割集。,注：(1)对非平凡图G，若是一个边割集，则GE不连通。,使得是G的一个边割集，其中。,(2)一条割边构成一个1边割集。,边连通度：,完全图的连通度定义为。空图的连通度定义为0。,注：(1)对平凡图或不连通图G，。(2)若图G是含有割边的连通图，则。(3)若，则称G为k边连通的。(4)所有非平凡连通图都是1边连通的。(5)使得的边割集称为G的最小边割集。,确定下列给定图类的点连通度和边连通度.,由定义我们可以确定对于图的任一点和任意一条边，有下列性质成立,定理3.1,证明：先证。,若G不连通，则。若G是完全图，则。,下设G连通但不是完全图。则G有边割集含有条边。设这个边割集为。对中每条边，选取一个端点，去掉这些端点（至多个）后，G便成为不连通图，故这些端点构成一个点割集，。因此。,再证。设d(v)=。删去与v关联的条边后，G变成不连通图，故这条边构成G的一个边割集。因此。证毕。,例,1、分别找G1和G2两个边割；2、给出它们的边连通度。,2,3,4,例,3.2块（block）,定义：无割点的连通图称为块。,图的块：若满足下列三条：（1）H是图G的子图；（2）H本身是一个块；（3）H是具有此性质的极大子图。则称H是图G的一个块。,例,注：至少有三个顶点的图是块当且仅当它是2连通图。,若只有两个顶点，则有反例，例如K2是个块，但不是2连通的。,定理3.2(Whitney,1932)3的图G是2连通图（块）当且仅当G中任二顶点共圈。,课后习题（a）证明：若G是单图，且,则,(b)找一个单图G,满足,解：（a）证：当,时，,若,不相邻，,则对任意第三点,都有,这时，,对任意v-3个顶点的子集V,均有G-V仍连通。,故,当,时，,故,（b）对,作,易知：v=4时，,v4时，Kv-4中的v-4个顶点构成G的顶点割集，故,再由定理3.1即得,课后习题证明：若G为满足,的单图，,证：在G中除去任意的k1个顶点，所得之图记为G1。则,由练习15知，G1连通，,从而知G是k-连通。,则G是k-连通的。,注:按定义,从而对k=v时，,的情况，即G是Kv的情况，,要相应地把结论中的v-连通换成(v-1)连通。,课后习题若G是3-正则单图，则,证：,从而至少存在一个分支仅一条边和v相,所以,所以,关联。显然这边为G的割边，故,故v1是G-e2的割点,且,G1=G-v1连通。则,v2是G1的割点且,类似与知,在G1中存在一割边e2(关联于v2),于是类似于知，,在G-e2中存在一割边e1,即,由于,(注：值得注意，在证明过程中仅用到3这条件，,从而对于3的单图成立,结论成立。,第四章,欧拉图与哈密尔顿图。欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。,定理4.1一个非空连通图是Euler图当且仅当它没有奇度顶点。,Euler图的判定,推论4.1一个连通图有Euler迹当且仅当它最多有两个奇度顶点。,给定一个由16条线段构成的图形(见图)。证明：不能引一条折线与每一线段恰好相交一次。(折线可以是不封闭的和自由相交的，但它的顶点不在给定的线段上，而边也不通过线段的公共端点，即不允许折线从图的缺口处穿过。),例,证明：我们先来建立一个图G。图G中的顶点xi代表这个图形的区域Xi(i=1,2,3,4,5,6)。顶点xi与xj之间连接的边数等于区域Xi与Xj公共线段的数目(如图所示),这样建立的图G中的每一条边对应这个图形的一条线段。存在满足条件的折线当且仅当G中存在一条Euler环游或Euler通路。由于G中有四个奇点，故G不存在Euler环游及Euler通路，也即证明了在图形中不能引一条满足要求的折线。,*经过图G的每个顶点恰一次的路称为G的Hamilton路。*经过图G的每个顶点恰一次的圈称为G的Hamilton圈。Hamilton图的研究起源于十二面体的游戏（1856）,与Euler图不同，目前为止尚没有找到判别一个图是否是Hamilton图的有效充要条件。这是图论中未解决的重要难题之一。,给出一些经典的充分条件和必要条件。,定理4.3若G是H图，则对V(G)的每个非空真子集S，均有w(GS)|S|。,证明：设C是G的H圈，则对V(G)的每个非空真子集S，均有w(CS)|S|由于CS是GS的生成子图，故w(GS)W(CS)|S|。证毕。,利用定理4.3可判断下图不是H图。,但定理4.3不能来判断下列Petersen图不是H图。,Petersen图,（1）度型条件定理4.4(Dirac,1952)若G是简单图，且3，v/2，则G是Hamilton图。,令A=G|G的顶点数为3，/2，且G是非Hamilton图。,取A中边最多的一个G。因3，故不是完全图（否则G是Hamilton图）。设u和v是G的不相邻顶点。,充分条件,证明:用反证法：假定定理不真。,于是G中存在以u为起点v为终点的Hamilton路v1v2v。这里v1=u，v=v，令,和,由于,故,并且,由G的选择，Guv是Hamilton图。因G是非Hamilton图，故Guv的H圈必经过e=uv。,（因为若，则G将包含H圈，矛盾）。,故d(u)+d(v)=|S|+|T|=|ST|+|ST|，这与/2的前提矛盾。证毕。,引理4.5（Bondy(2)P的每一后向弧都是非零流弧（）；则称P是网络D的关于可行流f的一条增广链。简称增广链。,增广链P：,定理11.3：设f是网络D上的一个可行流，则f是一个最大流当且仅当网络D不存在f的增广链。,增广链P：,算例：求下面网络的最大流.,(1)给网络赋一个初始0流f0；给vs标号(-,);,(-,),(a)对弧(vi,vk),若,则给vk标号(+vi,l(vk),其中(b)对弧(vk,vi),若,则给vk标号(-vi,l(vk),其中,标号过程1,(+vs,8),(+vs,2),(+v1,5),(+v3,2),(+v2,5),找到流f0的增广链P0=vsv1v2vt，,(-,),调整过程1,(+vs,8),(+vs,2),(+v1,5),(+v3,2),(+v2,5),找到流f0的增广链P0=vsv1v2vt，,2.调整流量,调整量,=5.,5,5,5,调整流值得流值为5的新可行流f1.,给vs标号(-,);,(-,),(a)对弧(vi,vk),若,则给vk标号(+vi,l(vk),其中(b)对弧(vk,vi),若,则给vk标号(-vi,l(vk),其中,标号过程2,(+vs,3),(+vs,2),(+v3,2),(+v3,2),(+v2,2),找到流f1的增广链P1=vsv3v2vt，,得新可行流f1，,重新进入标号过程.,(-,),调整过程2,(+vs,3),(+vs,2),(+v3,2),(+v3,2),(+v2,2),找到流f1的增广链P1=vsv3v2vt，,2.调整流量,调整量,=2.,2,调整流值得流值为7的新可行流f2.,2,7,给vs标号(-,);,(-,),(a)对弧(vi,vk),若,则给vk标号(+vi,l(vk),其中(b)对弧(vk,vi),若,则给vk标号(-vi,l(vk),其中,标号过程3,(+vs,3),(+v1,3),(+v3,3),(+v3,3),(+v4,3),找到流f2的增广链P2=vsv1v3v4vt