第1章-图和子图优秀PPT.ppt

《第1章-图和子图优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第1章-图和子图优秀PPT.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 图的基本概念v1.1 图的概念v1.2 同构v1.3 图的矩阵和顶点的度v1.4 子图v1.5 路和连通性 v1.6 圈v1.7 最短路问题 1.1 图的概念lKnigsberg七桥问题l电网络 l四色猜想图图 G=(V(G),E(G)，其中 V(G)=V-顶点集，-顶点数 E(G)=E-边集，-边数例如，下图中，V=a,b,f,E=k,p,q,ae,af,ce,cf defG=(V,E)p q abc k v留意，留意，右图仅仅是图右图仅仅是图G的的一个几何实现一个几何实现（geometric realization,代表代表representation），），它们有无穷多个，随顶点

2、它们有无穷多个，随顶点位置及边的形态而不同。位置及边的形态而不同。真正的图真正的图G是上面所给出是上面所给出式子，它与顶点的位置、式子，它与顶点的位置、边的形态等无关。不过今边的形态等无关。不过今后对图后对图G及其几何实现将及其几何实现将常常不加以区分。常常不加以区分。defG=(V,E)p q abc k v称 边 ad 与顶点a(及d)相关联(incident)。也称顶点 b(及 f)与边 bf 相关联。v称顶点a与e 相邻(adjacent)。也称有公共端点的一些边，例如v p与af彼此相邻。v称一条边的两个顶点为它的两个端点v环（loop，selfloop）：如边 k，它的两个端点相同

3、。v棱（link）：如边ae，它的两个端点不相同。v重边：如边p及边q。v简洁图：（simple graph）无环，无重边v平凡图：仅有一个顶点的图。v留意：任何一图都有 V 。v记号：（,）defG=(V,E)p q abc k 例题例题1.1 若若G为简洁图，则为简洁图，则 。1.2 若一群人中，凡相识的两人都无公共若一群人中，凡相识的两人都无公共挚友，凡不相识的两人都恰有两个公共挚挚友，凡不相识的两人都恰有两个公共挚友，则每人的挚友数相等。友，则每人的挚友数相等。1.2 同构例如在下图中，称 图G恒等恒等于图H(记为 G=H)VG)=V(H),E(G)=E(H)。a y zx wb c

4、d e G=(V,E)x d w a b c y e z F=(V,E)x w b c d e a yz H=(V,E)图G同构同构于图F （记为 G F）V(G)与V(F),E(G)与E(F)之间各各存在一 一映射，及且这二映射保持关联关联关系，即：a y zx wb c d e G=(V,E)x w b c d e a yz H=(V,E)x d w a b c y e z F=(V,E)注注 两个图同构是指”它们有相同的结构”，仅在顶点及边的标号上或两个图的画法上有 所不同而已。往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。注注 判定两个图是否同构是个未解决的困难问题（o

5、pen problem）。a y zx wb c d e G=(V,E)x w b c d e a yz H=(V,E)x d w a b c y e z F=(V,E)v完全图完全图(complete graph)Knv空图空图（empty g.）E=。V(V)为独立集独立集 V中任二顶点都互不相邻。v二部图二部图（偶图偶图，bipartite g.）G=(X,Y;E)存在 V(G)的一个 2-划分划分(X,Y)（即V(G)=X Y，且XY=），使X与Y 都是独立集。K1K2K3K4K5v完全二部图完全二部图 Km,n 二部图G=(X,Y;E)，其中X和Y之间的每对顶点都相邻，且 X=m,Y

6、=n。v类似地可定义，完全三部图完全三部图（例如，Km,n,p），完完全全 n-部部 图图等。二部图K3,3K1,5K2,2,2v例。用标号法判定二部图。用红蓝两种颜色进行顶点标号如下：任取一顶点v 标以红色。再将v的全部相邻顶点都标以兰色。这时称v为已扫描顶点。若尚存在一已标号未扫描顶点u，将它的全部相邻顶点，（若不出现冲突）都标以（其相异色）红色，并称u为已扫描顶点。如此接着下去，直到或者全部顶点都已标号，从而该图为一二部图；或者在标号过程中出现冲突，该图为非二部图。习题1.2.1 G H (G)=(H),(G)=(H)。并证明其逆命题不成立。1.2.2 证明下面两个图不同构：v1.2.3

7、 证明下面图证明下面图1与图与图2是同构的；是同构的；而图而图1与图与图3是不同构的：是不同构的：v1.2.4 证明两个简洁图证明两个简洁图G和和H 同构同构 存在一存在一 一一映射映射 f:V(G)V(H)，使，使 v 得得 uv E(G)当且仅当当且仅当 f(u)f(v)E(H)。图1 图2 图3 v1.2.5 证明：证明：(a).(Km,n)=mn;v (b).对简洁二部图有对简洁二部图有 2/4.v1.2.6 记记Tm,n为这样的一个完全为这样的一个完全m-部图：其顶点部图：其顶点数为数为n，每个部分的顶点数为，每个部分的顶点数为n/m v 或或n/m个。证明：个。证明：v (a).(

8、Tm,n)=其中其中 k=n/m.v (b)*.对随意的对随意的n顶点完全顶点完全m-部图部图G，确定有，确定有(G)(Tm,n)，且仅当，且仅当G Tm,n v 时等式才成立。时等式才成立。v1.2.7 所谓所谓k-方体是这样的图：其顶点是由方体是这样的图：其顶点是由0与与1组成的有序组成的有序k-元组，其二顶点相元组，其二顶点相 v邻当且仅当它们恰有一个坐标不同。证明邻当且仅当它们恰有一个坐标不同。证明k-方体方体有有2k个顶点，个顶点，k*2 k-1条边，且是一偶图。条边，且是一偶图。v1.2.8 简洁图简洁图G的补图的补图G c 是指和是指和G有相同顶点集有相同顶点集V的一个简洁图，在

9、的一个简洁图，在G c中两个中两个v 顶点相邻当且仅当它们在顶点相邻当且仅当它们在G中不相邻。中不相邻。v (a).画出画出Kcn和和 Kcm,n。v (b).假如假如G G c则称简洁图则称简洁图G为自补的。证为自补的。证明：若明：若G是自补的，则是自补的，则 v 0,1(mod 4)。v1.2.9 设设 ，且，且v ，则则H确确定是个完全二部图。定是个完全二部图。v1.2.10若若 的简洁图的简洁图 中如下性质成立中如下性质成立v 则则G确定是个确定是个完全（某）完全（某）m部图。部图。1.3 图的矩阵和顶点的度M(G)=mi,j,(关联矩阵)mi,j=顶点vi与边ej 的关联次数=0,1

10、,2.e1e2e3e4e5e6v1v2v3v4G=(V,E)e7A(G)=ai,j,ai,j=连接顶点vi 与 vj 的边数。（邻接矩阵）v顶点 v的 度度 dG(v)=G中与顶点v 相关联边数。（每一环记为2）v记号：最大、最小度最大、最小度 ，。（(G),(G)）v奇点奇点：度为奇数的顶点；v偶点偶点：度为偶数的顶点；v孤立点孤立点：度为0的顶点；v悬挂点悬挂点：度为1的顶点；v悬挂边悬挂边：悬挂点的关联边。v定理定理1.3.1(hand shaking lemma)任一图中，v推论推论1.1 任一 图中，度为奇数顶点的个数为偶数。例：任一多面体中，边数为奇数的外表面的数目为偶数。（提示：

11、作一图，其顶点对应于多面体的面，且二顶点相邻当且仅当对应的两个面相邻（即有公共边界）。）k-正则图正则图（k-regular g.)0-正则图1-正则图2-正则图3-正则图习题v1.3.1 证明：证明：2/。v1.3.2 若若 k-正则偶图正则偶图(k 0)的的2-划分为划分为(X,Y),则则 X=Y。v1.3.3 在人数在人数 1的人群中，总有二人在该人的人群中，总有二人在该人群中有相同的挚友数群中有相同的挚友数 v1.3.4 设设V(G)=，则称，则称(d(v1),d(v2),d(v)为为G的度序列。的度序列。v 证明：非负整数序列证明：非负整数序列(d1,d 2,d n)为某一为某一图的

12、度序列图的度序列 是偶数。是偶数。v v1.3.5 证明：任一证明：任一 无环图无环图G都包含一偶生成子图都包含一偶生成子图H，使得，使得 dH(v)dG(v)/2 对全部对全部v V 成立。成立。v （提示：考虑（提示：考虑G的边数最多的偶生成子图）的边数最多的偶生成子图）v1.3.6*设平面上有设平面上有n个点，其中任二点间的距离个点，其中任二点间的距离 1，证明：最多有，证明：最多有 3n对点的距离对点的距离=1。1.4 子图v子图子图(subgraph)H G V(H)V(G),E(H)E(G)。v真子图真子图 H G H G 且且HG。母图（。母图（super graph）。）。v生

13、成子图（生成子图（spanning subg.）H H G 且且V(H)=V(G)。v生成母图。生成母图。v基础简洁图基础简洁图（underlying simple g.）：从一图中去掉其全部）：从一图中去掉其全部重边及环后所得的剩余（简洁图）图称之为其基础简洁图。重边及环后所得的剩余（简洁图）图称之为其基础简洁图。v导出子图（导出子图（induced subgraph.）GV，(非空非空 V V)v 以以V为顶点集，以为顶点集，以G中两端都在中两端都在V上的边全体为边集构上的边全体为边集构成的成的G的子图的子图 v边导出子图边导出子图 GE (非空非空E E)v 以以E为边集，以为边集，以E

14、中全部边的端点为顶点集的的子图。中全部边的端点为顶点集的的子图。GV,GE 两种子图对应于取子图的两种基本运算。下面是取子图的另两种基本运算：vG-V 去掉V及与V相关联的一切边所得的剩余子图。即 GV VvG-E 从中去掉E 后所得的生成生成子图 fea bc dghG=(V,E)x wvyuGu,w,x Gu,w,x,y Gc,d,eGf,c v例。G-b,d,g,(=GE b,d,g )v G-b,c,d,g,(GE b,c,d,g )v G-a,e,f,g.(GE a,e,f,g )v留意 GE E 与G-E v虽有相同的边集，但两者不确定相等：后者确定是生成子图，而前者则不然。fea

15、 bc dghG=(V,E)x wvyubc dhx wvyufeac hxwvyuxfeahwvyuv上述四种运算是最基本的取子图运算，今后常常会遇到，确定要细致驾驭好。关于子图的另一些定义还有：v G+E 往G上加新边集E 所得的（G的）母图。v 为简洁计，今后将v G e 简记为 G e；v G-v 简记为 G-v。v 设 G1,G2 G，称G1与G2为v 不相交的（disjiont）V(G1)V(G2)=v (E(G1)E(G2)=)v 边不相交（edge-distjiont，边不重的）v E(G1)E(G2)=。v（但这时G1与G2仍可能为相交的）。v 并图 G1G2,当不相交时可简

16、记为 G1+G2.v 交图 G1 G2.习题v1.4.1 证明：完全图的每个导出子图是完全证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。图；偶图的每个导出子图是偶图。v1.4.2*设设G为一为一 简洁简洁 图，图，1 n -1。证。证明：若明：若 4，且，且G中每个中每个n顶点的导出子图顶点的导出子图均有相同的边数，则均有相同的边数，则 G K 或或 Kc 。1.5 路和连通性路和连通性v途径途径（walk）例如图G的(u,x)-途径 W=ueyfvgyhwbvgydxdydx (有限非空序列)=uyvywvyxyx (简写法-当不引起混淆时)uvyxweabdhcfgv起点（

17、起点（origin）u 。v终点（终点（terminus）x。v内部顶点（内部顶点（internal vertex）y,v,w,x。v （留意，中间出现的（留意，中间出现的x也叫内部顶点。）也叫内部顶点。）v长长 边数（重复计算）。边数（重复计算）。v节（段，节（段，section）。）。例如例如W的的(y,w)-节节=yvw。vW-1（逆途径）（逆途径）,vWW（两条途径（两条途径W与与W相连接。要求：相连接。要求：W的终点的终点=W的起点）。的起点）。v迹迹(trail)边各不相同的途径（顶点可重复出现）。边各不相同的途径（顶点可重复出现）。例如，例如，yvwyx。v路路(path)顶点各

18、不相同的途径。（边也确定不顶点各不相同的途径。（边也确定不重复出现。路可当作一个图或子图）。例如，重复出现。路可当作一个图或子图）。例如，yvwx。v距离距离 dG(u,v)=图图G中顶点中顶点u与与v之间最短路的长。之间最短路的长。uyvywvyxyx定理1.5.1 G中存在(u,v)-途径 G中存在(u,v)-路。证明：是明显的；：设G中存在 -途径 其中 若W中的顶点互不相同，则W就是(u,v)-路；不然，设其中有 （），则 也是一条 -途径，长度比W短。若其中仍有重复顶点出现，则接着上述过程。由于W 长度的有限性，上述过程必停止于一(u,v)-路。图 G 图的连通性：称G中顶点u与v为

19、连通的(connected)G中存在(u,v)-路 (G中存在(u,v)-途径。)简洁验证，V上的连通性是V上的等价关系，它将 V划分为一些等价类：V1，V使每个Vi中的任二顶点都连通（即存在(u,v)-路）；而不同Vi与Vj之间的任二顶点都不连通。v称每个 GVi i=1,2,.为G的一个分支分支（component）;称(G)为G的分支数分支数。v称 G为连通图连通图 (G)=1 G中任两点间都有一 条路相连。v称 G为非连通图非连通图 (G)1。v记号：记号：对任一非空 SV，令 =VS,记 S,=G中两端分别在S及 中的一切边的集合。（后文中将称为边割边割）简洁证明：定理1.5.2 G

20、连通 对任 S V 都有 S,例1.5 简洁图G中，k G中有长 k 的路。（留意到，G中任一最长路P的起点（终点）的全部邻接点全在P上。）习题v1.5.1 证明：证明：G中长为中长为k的的 途径的数目途径的数目,就是就是A k 中的中的(I,j)元素，其中元素，其中A为为G的的 v 邻接矩阵。邻接矩阵。v1.5.2 证明：对简洁图证明：对简洁图G有，有，G连通。连通。v 对于对于 1，试给出，试给出 的不连通简洁图。的不连通简洁图。v1.5.3 证明简洁图证明简洁图G中，中，/2-1 G连通。连通。当当 是偶数时，试是偶数时，试 给给 出出v 一个不连通的一个不连通的(/2-1)正则简洁图。

21、正则简洁图。v1.5.4 G不连通不连通 Gc 连通。连通。v1.5.5 对随意图对随意图G的任一边的任一边e，有，有 (G)(G-e)(G)+1 。v1.5.6 G连通，且连通，且 d(v)=偶数，偶数，v V (G-v)d(v)/2,v V.v1.5.7 连通图中，任二最长路必有公共顶点。连通图中，任二最长路必有公共顶点。v1.5.8 对任一图的任三个顶点对任一图的任三个顶点 u,v,w 都有都有 v d(u,v)+d(v,w)d(u,w)。v1.5.9 任一的简洁、连通、非完全图中，确定有任一的简洁、连通、非完全图中，确定有三个顶点三个顶点 u,v,w，v 使得使得uv,vw E 而而

22、uw E。v1.5.10若图若图G 中恰有两个奇点中恰有两个奇点u与与v，则，则G中确中确定有一定有一(u,v)路。路。1.6 圈v闭途径闭途径（closed walk）起点=终点 且长长 0 的途径。v闭迹闭迹(closed trail)边各不相同的闭途径。v圈圈（cycle）顶点各不相同的闭迹。（可当作一图或子图。）例：v闭途径：uyvyu;uywxywvu；uyuyu。v闭迹：uyxwyvu。v圈：yfvgy;uywvu。vk-圈圈（k-cycle）长为k的圈。v奇圈奇圈(odd cycle)。v偶圈偶圈(even cycle)。uvyxweabdhcfg例：v1-圈（即一条环环），v2

23、-圈(由两条重边组成)，v3-圈（又称三角形）。三角形）。定理定理1.2 G 为二部图 G不含奇圈。证明：设G的2-划分为（X,Y），由G的定义，G的任一圈中，X和Y的顶点确定交织出现，从而其长必为偶数。：不妨设G为 连通的。任取一顶点u,令 X=xV d(u,x)=偶数,Y=yV d(u,y)=奇数。易见，(X,Y)为V的2-划分，所以只要再证X（和Y）都是G的独立集（即X（或 Y）中任二顶点v，w都不相邻）即可。令P与Q分别为最短(u,v)-路与最短(u,w)-路。设u为P与Q的最终一个公共顶点；而 P与Q分别为P的(u,v)-节与Q的(u,w)-节。则P与Q只有一公共顶点。又，由于P与Q

24、的(u,u)-节的长相等，P与Q的长有相同的奇偶性，因此v与w不能相邻，不然，v(P)1 Qwv 将是一奇圈，冲突。PQuP Quvw简洁证明：命题1 图G中 2 G中含圈。命题2 简洁图G，2 G含长 +1 的圈。（提示：以上两例中可考虑其最长路）命题3 任一图G中 G含圈。证明：反证，假设结论不成立，而G为其最小反例。则首先G是连通的，且 。再由以上第一例知，G中存在一顶点u，。于是，且明显G-u中也不含圈，从而G-u也是个反例，但顶点数比G少，冲突。习题v 若边e在G的一闭迹中，则e在G的一圈中。v1.6.2 证明：(a).G含圈。(b)*.+4 G含两个边不重的圈。v 证明：任一连通偶

25、图G=(X,Y)的2-划分 (X,Y)是唯一的。（提示：不然，必有二顶点u,v，原属同一部（例如，）X，而在另一种2-划 分 则不然。）v1.6.4证明或反证：证明或反证：v(1).G中有两个不同的中有两个不同的(u,v)路，则路，则G中含一圈。中含一圈。v(2).G中有一闭途径，在则中有一闭途径，在则G中含一圈。中含一圈。v(3).G中有一长为奇数的闭途径，在则中有一长为奇数的闭途径，在则G中含一中含一奇圈。奇圈。v1.6.5 设图设图G 的顶点可用两种颜色进行着色，使的顶点可用两种颜色进行着色，使每个顶点都至少与两个异色顶点邻，则每个顶点都至少与两个异色顶点邻，则G中确定中确定包含偶圈。包

26、含偶圈。v1.6.6座位的教室中，不行能让每个学生座位的教室中，不行能让每个学生都作一上下左右移动，使每个人都换了座位。都作一上下左右移动，使每个人都换了座位。（提示：（提示：“座位图座位图”是是 一二部图）一二部图）1.7 最短路问题v赋权图赋权图（weighted graph）G (注：权 1 时即为上文中所提的图。)v权权(weight)w(e)0.记号：w(H)=,H G.v路路P的长的长=w(P)v顶点u与v的 距离距离 d(u,v)=最短(u,v)-路的长。v问题问题 求最短求最短(u0,v0)-路。路。v转转 求最短求最短(u0,v)-路路,v V u0.v简化简化 只考虑简洁图

27、，且只考虑简洁图，且w(e)0 e E.v （w(uv)=0 时，时，可合并可合并u与与v为一为一 顶点）。顶点）。v原理原理 逐步求出顶点序列 u1,u2,.使 d(u 0,u1)d(u 0,u2).记 S0=u0,Sk=u 0,u1,u k，=V S 。Pi 为最短(u0,ui)-路 i=1,2，(1).求u1：u1是使 w(u0 u1)=min w(u0v)v u 0 者.得 S1=S0 u1,P1=u 0u1.(2).若已求得Sk-1;d(u0,u1)，d(u0,uk-1);及最短(u0,ui)路 Pi ，i=1.2,.,k-1。求uk：明显，d(u0,uk)=min d(u0,v)v

28、 =d(u0,uj)+w(u ju k)某 j 1,2,，k-1 =min d(u0,u)+w(uu k)u S k-1 =mind(u0,u)+w(uv)u S k-1，v =min l(v)v 其中，l(v)=min d(uo,u)+w(uv)u S k-1 (l(uk)=d(u0,uk)Sk=Sk-1 uk ,Pk=Pj ujuk 某 j 1,2，k-1 。update 进行下一 步时，只要更新 l(v)即可：l(v)min l(v),l(uk)+w(ukv)对 v Dijkstra算法算法v(1).作为起先：l(u0)0;l(v);v u0;v S0 u0;k 0.v(2).（这时已有

29、Sk=u0,u1，uk）v l(v)min l(v),l(uk)+w(ukv)v v 再计算 min l(v)，设其最小值点为 uk+1，令v Sk+1 =Sk uk+1。v(3).若 k=-1,停止；不然，令kk+1,并回到(2)。v计算困难性v 加法：(-1)/2v 比较：(-1)/2 2v v ：(-1)2v+)_v 共 O(2)凡是困难性为 p(,)的算法(p(.,.)为一多项式)称为“好算法”(“good algorithm”-J.Edmonds)。这是相对于指数型算法而言的：在10-6秒/步运算速度下：由上表可见，两种算法有天壤之别。注注1.若只关切求若只关切求d(u0,v0),则

30、算法进行到则算法进行到v0Sk时停止。时停止。2.计算过程中，每步所得子图都是一计算过程中，每步所得子图都是一 棵树棵树（？：每步都是往其上增加一条边及一（？：每步都是往其上增加一条边及一 个顶点）。因此该过程称为个顶点）。因此该过程称为 tree growing procedure。在该树中的。在该树中的(u0,v0)-路，路，是中最短是中最短(u0,v0)-路路。3.若要计录若要计录u0到每个顶点到每个顶点u的最短路，只要的最短路，只要记录该路中记录该路中u的前一个顶点（即该树中的前一个顶点（即该树中u的的父亲）即可。父亲）即可。72213217353444866u0停例精品课件精品课件！精品课件精品课件！习题v 描述一个算法以确定 (a).一图的各个分支；(b).一图的围长围长（即最短圈的长）；并说明你的算法好到什么程度。