《图论复习题》PPT课件.ppt
《《图论复习题》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《图论复习题》PPT课件.ppt(123页珍藏版)》请在三一办公上搜索。
1、第一章 图和子图,图的基本概念;常见的特殊图类;二部图及其性质;图的同构;关联矩阵与邻接矩阵;路、圈与连通图;最短路问题。,K-方体图是其顶点为0与1的有序k元组,当且仅当它们的一个坐标不相同时,此两个顶点相连以边。证明k-方体图是有2k个顶点k2k-1条边的2-部图。,导出子图和图的运算,G2,G1,G2,G1,由定理 1.2可知图(a)所示的图不是二分图,因为它包含一个长为3的圈,图(b)所示的图是一个二分图,它不含长为奇数的圈.,定理 一个图是二部图当且仅当它不含奇圈。,证明:设 P=v0v1 v k是G 的最长路。因为d(v 0)3,所以存在两个与 v 1相异的顶点v,v 与 v 0相
2、邻。v,v必都在路P 上,否则会得到比P 更长的路。无妨设v=v i,v=v j,(i j)。若i,j 中有奇数,比如i 是奇数,则路P 上 v 0到v i的一段与边 v 0 v i 构成一个偶圈;若i,j 都是偶数,则路P 上v i到 v j的一段与边 v 0 v i 及v 0 v j构成一个偶圈。证毕。,例 设G 是简单图,若(G)3,则G 必有偶圈。,图中两点的连通:如果在图G 中u,v 两点有路相通,则称顶点u,v 在图G 中连通。连通图:图G 中任二顶点都连通。,图的连通分支:若图G 的顶点集V(G)可划分为若干非空子集V 1,V 2,V,使得两顶点属于同一子集当且仅当它们在G 中连
3、通,则称每个子图GV i 为图G 的一个连通分支(i=1,2,)。,事实上,假如G 不连通,则至少有一个连通分支的顶点数不超过n。在此连通分支中,顶点的度至多是n 1。这与(G)n 矛盾。证毕。,例 设有2n 个电话交换台,每个台与至少n 个台有直通线路,则该交换系统中任二台均可实现通话。,证明:构造图G 如下:以交换台作为顶点,两顶点间连边当且仅当对应的两台间有直通线路。,问题化为:已知图G 有2n 个顶点,且(G)n,求证G 连通。,应用:最短路问题,算法实现标号法,课后习题(a)G 是单图且,证明G 连通.,(b)v1时,找一个不连通的单图G使得,证:(a)若 G 不连通,可分为两个顶点
4、数分别为,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是单图矛盾。,树及其基本性质;最小生成树。,第二章,定理 下列命题
5、等价:(1)G 是树;(2)G 中无环边且任二顶点之间有且仅有一条路;(3)G 中无圈且=1;(4)G 连通且=1;(5)G 连通且对任何e E(G),G e 不连通;(6)G 无圈且对任何e E(G),G+e 恰有一个圈。,证明:(1)(2)G 是树G 连通 u,v V(G),存在路P(u,v)。,逆定理的成立见习题,若还存在一条路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成立。当
6、=k+1时,任取u,v V(G)。考虑图G=G uv,因G 中u、v 间只有一条路,即边uv,故G不,(2)(3)若G 有圈,则此圈上任二顶点间有两条不同的路,与前提条件矛盾。下面用归纳法证明=1。,连通且只有两个连通分支,设为 G 1,G 2。注意到 G 1,G 2分别都连通且任二顶点间只有一条路,由归纳法假设,,因此,归纳法完成。,(3)(4)用反证法。若G 不连通,设 G 1,G 2,G w是其连通分支(w 2),则(因G i是连通无圈图,由已证明的(1)和(2)知,对每个G i,(3)成立)。这样,这与 矛盾。,(4)(5)(G e)=(G)1=2,但每个连通图必满 足 1(见下列命题
7、),故图G e 不连通。,=1,2 时,1显然成立。假设 k 的连通图都 1。对于=k+1的连通图H,任取v V(H),考虑H v。,若H v 连通,则由归纳假设,,(H v)(H v)1=k 1,而,命题 若图H 连通,则(H)(H)1。,证明:对 做数学归纳法。,(H)(H v)+1(k 1)+1=(k+1)1=(H)1。,若H v 不连通,设 H 1,H 2,H w 是其连通分支,由归纳假设,故,而(H)(H v)+w(k w)+w=(k+1)1,归纳法完成。,(w 2)。,=(H)1。,(5)(6)先证G 中无圈:若G 中有圈,删去圈上任一边仍连通,矛盾。,再证G+e 恰含一个圈:因G
8、 连通且已证G 无圈,故G 是树。由(2),任二顶点间仅有一条路相连,故G+e 中必有一个含有e 的圈;另一方面,若G+e 中有两个圈含有e,则G+e e=G 中仍含有一个圈,矛盾。,(6)(1)只需证G 连通。任取u,v V(G),若u、v 相邻,则u 与v 连通。否则,G+uv 恰含一个圈,故u 与v 在G 中连通。由u、v 的任意性,图G 连通。定理证毕。,证明:设T 是一个非平凡树。因T 连通,故对每个顶点,v i,都有。若对所有v i 都有,则,另一方面,,这两方面矛盾。故T 至少有一个1 度顶点,设为u。除此之外,其余 1个顶点的度数之和为2 3。,若这些点的度都大于或等于2,则其
9、度数之和 2(1),推论2.2 非平凡树至少含两个1 度顶点(叶子)。,=2 2。这与2 3矛盾。故除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 不连通,则
10、(G)=0。,(4)若G 是平凡图,则(G)=0。,(5)所有非平凡连通图都是1 连通的。,例,1、分别找G1和G2两个顶点割;2、给出它们的连通度。,例,在2.2中 为图G 的一个边割集。含有k 条边的边割集称为k-边割集。,注:(1)对非平凡图G,若 是一个边割集,则G E 不连通。,使得 是G 的一个边割集,其中。,(2)一条割边构成一个1边割集。,边连通度:,完全图的连通度定义为。空图的连通度定义为0。,注:(1)对平凡图或不连通图G,。(2)若图G 是含有割边的连通图,则。(3)若,则称G 为k边连通的。(4)所有非平凡连通图都是1边连通的。(5)使得 的边割集 称为G 的最小边割集
11、。,确定下列给定图类的点连通度和边连通度.,由定义我们可以确定对于图的任一点和任意一条边,有下列性质成立,定理3.1,证明:先证。,若G 不连通,则。若G 是完全图,则。,下设G 连通但不是完全图。则G 有边割集含有 条边。设这个边割集为。对 中每条边,选取一个端点,去掉这些端点(至多 个)后,G 便成为不连通图,故这些端点构成一个点割集,。因此。,再证。设d(v)=。删去与v 关联的 条边后,G 变成不连通图,故这 条边构成G 的一个边割集。因此。证毕。,例,1、分别找G1和G2两个边割;2、给出它们的边连通度。,2,3,4,例,3.2 块(block),定义:无割点的连通图称为块。,图的块
12、:若满足下列三条:(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
13、-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中存在一割
14、边e1,即,由于,(注:值得注意,在证明过程中仅用到 3这条件,,从而对于3的单图成立,结论成立。,第四章,欧拉图与哈密尔顿图。欧拉图;中国邮递员问题;哈密尔顿图;旅行商问题。,定理4.1 一个非空连通图是Euler 图当且仅当它没有奇度顶点。,Euler 图的判定,推论4.1 一个连通图有Euler 迹当且仅当它最多有两个奇度顶点。,给定一个由16条线段构成的图形(见图)。证明:不能引一条折线与每一线段恰好相交一次。(折线可以是不封闭的和自由相交的,但它的顶点不在给定的线段上,而边也不通过线段的公共端点,即不允许折线从图的缺口处穿过。),例,证明:我们先来建立一个图G。图G中的顶点xi代表这
15、个图形的区域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 图不同,目前为止尚没有找到判别一个图是否是Ham
16、ilton 图的有效充要条件。这是图论中未解决的重要难题之一。,给出一些经典的充分条件和必要条件。,定理 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
17、,且G 是非Hamilton 图。,取A 中边最多的一个G。因3,故不是完全图(否则G 是Hamilton 图)。设u 和v 是G的不相邻顶点。,充分条件,证明:用反证法:假定定理不真。,于是G 中存在以u 为起点v 为终点的Hamilton 路 v1v2 v。这里v1=u,v=v,令,和,由于,故,并且,由G 的选择,Guv 是Hamilton 图。因G 是非Hamilton 图,故Guv 的H圈必经过e=uv。,(因为若,则G 将包含H圈,矛盾)。,故d(u)+d(v)=|S|+|T|=|S T|+|S T|,这与/2的前提矛盾。证毕。,引理4.5(Bondy&Chvtal,1974)设G
18、 是简单图,u 和v 是G 中不相邻的顶点,且d(u)+d(v),则G 是Hamilton 图当且仅当Guv 是Hamilton 图。,(2)闭包型条件,定理4.7 一个简单图是Hamilton 图当且仅当它的闭包是Hamilton 图。,证明:在构作闭包过程中,反复运用引理4.5 即可。,推论4.8 设G 是3的简单图。若C(G)是完全图,则G 是Hamilton 图。,例 有一个n 人的团体(n3),这n 个人中互相认识的对数(两个人认识就算作一对)至少是1/2(n-1)(n-2)+2.证明这n 个人可以围桌而坐,使每个人与他相邻座位上的2个人认识。,证明:以顶点代表人,两顶点相邻当且仅当
19、2个人互相认识,则G是至少有条边的简单图。现在证明G是Hamilton图。假若不然,则G无Hamilton回路,由Lemma 4.5知,G中存在两个不相邻的顶点 u 与 v。使,因而G中至多有n1 条边关联,Hamilton回路C。现在只需按C的顺序安排人员围桌而坐,就能使每个人与相邻座位的两个人认识。,于u 和 v。作G1=G-u,v,由于u 和v不相邻,故,定理4.9 设G 是度序列为(d1,d2,d)的简单图,这里 d1 d2 d,并且 3。若不存在小于2的m,使得dm m 和dm m,则G 是Hamilton 图。,(3)度序列条件,例 求下图的最优投递路线,A 为邮局。,解:只有两个
20、奇点,V=B,E。B 到E 的最短路为BAFE,权为13。完全赋权图 K2及相应的Euler 图G*为,易求得其Euler 环游,并得到最优回路。,应用:中国邮递员问题,课后习题 证明:若(a)G 不是 2-连通的,或(b)G 是二部圈,且它的二部划分(X,Y)有|X|Y|,则 G 是非Hamilton图。,证:,由定理 4.3 知 G 是非 Hamilton 图。,路P(u,v)中的顶点依次为,故和u,v相邻的顶点均在路上由于 G 是单图,,从而若令,课后习题 若 G 是连通单图,且v 2,则 G 中有一条长度至少为2的路。,按定义,故,所以有,l+1的圈C如下:,,,则,相矛盾。,故,一条
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论复习题 复习题 PPT 课件
链接地址:https://www.31ppt.com/p-5484774.html