《图论复习题》PPT课件

第一章 图和子图,图的基本概念；常见的特殊图类；二部图及其性质；图的同构；关联矩阵与邻接矩阵；路、圈与连通图；最短路问题。,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相邻。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 中连通，则称每个子图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 不连通，可分为两个顶点数分别为,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 连通且对任何e E(G) ，G e 不连通； （6） G 无圈且对任何e E(G) ，G + e 恰有一个圈。,证明：（1） （2） G 是树G 连通 u, v V (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, 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 （见下列命题），故图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 连通且已证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，则其度数之和 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 不连通，则 (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 的最小边割集。,确定下列给定图类的点连通度和边连通度.,由定义我们可以确定对于图的任一点和任意一条边，有下列性质成立,定理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 路 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 (2) P 的每一后向弧都是非零流弧（ ）； 则称 P 是网络 D 的关于可行流 f 的一条增广链。简称增广链。,增广链 P ：,定理11.3：设f 是网络D上的一个可行流，则 f 是一个最大流当且仅当网络D不存在 f 的增广链。,增广链 P ：,算例：求下面网络的最大流.,(1) 给网络赋一个初始0流 f 0 ；给 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),找到流 f 0 的增广链 P0 = vs v1 v2 vt，,(-,),调整过程1,(+vs,8),(+vs,2),(+v1,5),(+v3,2),(+v2,5),找到流 f 0 的增广链 P0 = vs v1 v2 vt，,2. 调整流量,调整量,=5.,5,5,5,调整流值得流值为5的新可行流 f 1 .,给 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),找到流 f 1 的增广链 P1 = vs v3 v2 vt ，,得新可行流 f 1 ，,重新进入标号过程.,(-,),调整过程2,(+vs,3),(+vs,2),(+v3,2),(+v3,2),(+v2,2),找到流 f 1 的增广链 P1 = vs v3 v2 vt ，,2. 调整流量,调整量,=2.,2,调整流值得流值为7的新可行流 f 2 .,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),找到流 f 2 的增广链 P2 = vs v1 v3 v4 vt ，,得新可行流 f 2 ，,重新进入标号过程.,(-,),调整过程3,(+vs,3),(+v1,3),(+v3,3),(+v3,3),(+v4,3),找到流 f 2 的增广链 P2 = vs v1 v3 v4 vt ，,2. 调整流量,调整量,=3.,8,调整流值得流值为10的新可行流 f 3 .,3,3,3,给 vs 标号(-,);,(-,),(a)对弧(vi , vk) ,若 , 则给 vk 标号(+ vi , l(vk) ), 其中 (b) 对弧(vk , vi) ,若 , 则给 vk 标号(- vi , l(vk) ), 其中,标号过程4,得新可行流 f 3 ，,重新进入标号过程.,标号无法进行,说明 f 3已是最大流，流值10.,