离散数学-第七章-图论.pptx-淘文阁

资源描述

《离散数学-第七章-图论.pptx》由会员分享，可在线阅读，更多相关《离散数学-第七章-图论.pptx（179页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2/17/2023 4:41 AM1图论的起源问题：能否从河岸或小岛出发，不重复地经过所有的桥回到原地。Konigsberg(哥尼斯堡)七桥问题第1页/共179页2/17/2023 4:41 AM2 Euler将河岸和小岛作为图的结点，七座桥为边，构成一个无向重图，问题化为图论中简单道路的问题。Euler(欧拉)1736年对这个问题给出了否定的回答。第2页/共179页2/17/2023 4:41 AM3一、图的基本概念洛杉矶旧金山芝加哥丹佛华盛顿底特律纽约第3页/共179页2/17/2023 4:41 AM4设A A、B B是两个集合，称 A&B=a,b|aA&B=a,b|a A,bA,b B

2、B为A A与B B的无序积。为方便起见，常将无序对a,ba,b记为(a,b)(a,b)定义1.1 1.1 一个无向图是一个有序的二元组，记为G G，其中（1 1）称为结点集，元素称为结点或顶点；（2 2）称为边集，它是无序积V&VV&V的多重子集，其元素称为无向边，简称为边。常把无向图记为G=G=第4页/共179页2/17/2023 4:41 AM5例1 1、G G1 1=V Vvv0 0,v,v1 1,v,v2 2,v,v3 3 E E(v(v0 0,v,v2 2),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v3 3),(v),(v2 2

3、，v v3 3)v0v3v2v1G1第5页/共179页2/17/2023 4:41 AM6G2v0v1v2v3例2 2、G G2 2=V Vvv0 0,v,v1 1,v,v2 2,v,v3 3 E E(v(v0 0,v,v3 3),(v),(v1 1,v,v3 3),(v),(v1 1,v,v3 3),(v),(v2 2，v v3 3),(v),(v0 0,v,v0 0)平行边环G 简单图（不含平行边也不含环）多重图第6页/共179页2/17/2023 4:41 AM7洛杉矶旧金山芝加哥丹佛华盛顿底特律纽约第7页/共179页2/17/2023 4:41 AM8定义1.2 1.2 一个有向图是一

4、个有序的二元组，记为D D，其中（1 1）同无向图；（2 2）称为边集，它是笛卡尔积VVVV的多重子集，其元素称为有向边，简称为边。v0v1v2DD=Vv0,v1,v2，E,第8页/共179页2/17/2023 4:41 AM9例3、D=,其中V=v1，v2，v3，v4 E=,v1v2v3v4平行边第9页/共179页2/17/2023 4:41 AM10有时用G泛指图（有向的或无向的）|V(G)|表示G的结点数|E(G)|表示G的边数有限图|V(G)|和|E(G)|均有限n阶图|V(G)|=n零图 E(G)=洛杉矶旧金山芝加哥丹佛华盛顿底特律纽约平凡图1阶零图空图 V(G)=第10页/共179

5、页2/17/2023 4:41 AM11标定图非标定图在无向图G=中，若ek=（vi，vj），则称vi，vj 为边ek的端点,ek与vi或ek与vj是彼此关联的；关联次数邻接点、邻接边v1v2v3v4v5 孤立点 e1e0e4e3e2e5(v3，v4)第11页/共179页2/17/2023 4:41 AM12在有向图D=中，若ek=，则称vi为ek 的起点，vj 为ek的终点；并称vi邻接到vj，vj邻接于vi。v1v2v3v4第12页/共179页2/17/2023 4:41 AM13定义1.3 1.3 在图G=G=中，与结点v v（v v V V）关联的边数称为结点v v的度数，简称度，记为

6、deg(v)deg(v)。(结点上的环关联次数为2)2)e2v1v2v3v4e4e3e5e1v2e3v4v1v3e1e2e4e5设D=为有向图，以结点v（v V）作为始点的边数称为v的出度，记作deg+(v)；以v作为终点的边数称为v的入度，记作deg-(v)称deg+(v)+deg-(v)为v的度数，记作deg(v)deg(v1)=deg(v4)=2 deg(v2)=deg(v3)=3 deg+(v1)=3 deg+(v2)=deg+(v4)=1 deg+(v3)=0 deg-(v1)=deg-(v2)=deg-(v4)=1 deg-(v3)=2 第13页/共179页2/17/2023 4:

8、和为10一个具有10个顶点，每个结点的度都为6的图，有多少条边？第15页/共179页2/17/2023 4:41 AM16定理1.2 设D=为有向图，|V(D)|=n，|E(D)|=m，则v2e3v4v1v3e1e2e4e5n=4m=5结点入度之和为5结点出度之和为5第16页/共179页2/17/2023 4:41 AM17推论无向图中度数为奇数的结点个数是偶数。证明：设V1和V2分别是偶度结点和奇度结点的集合,则偶数偶数偶数因此|V2|为偶数任何图e2v1v2v3v4e4e3e1第17页/共179页2/17/2023 4:41 AM18例4、已知无向图G中结点数n与边数m相等，2度结点与3

9、度结点各2个，其余结点的度数均为1，试求G的边数m。=2 2+3 2+1(n-4)=n+62m=n+6m=n m=6解：由握手定理第18页/共179页2/17/2023 4:41 AM19定义1.4 设G为n阶无向简单图，若G中每一对结点之间都有边，则称G为n阶无向完全图，简称n阶完全图，记作Kn(n1)k1k2k3k4k5第19页/共179页2/17/2023 4:41 AM20定义1.4 设D为n阶有向简单图，若D中每个结点都邻接到其余的n-1个结点，又邻接于其余的n-1个结点，则称D为n阶有向完全图。k1k3k2第20页/共179页2/17/2023 4:41 AM21定义1.5 1.5

10、设为n n阶无向简单图，以V V为结点集，以所有使G G成为完全图K Kn n的添加边组成的集合为边集的图，称为的相对于完全图的补图，记作k4G定理1.3 n阶无向完全图Kn的边数为n(n-1)/2；n阶有向完全图的边数为？。n(n-1)第21页/共179页2/17/2023 4:41 AM22图 K5图 Gedcba图 G1图 G3第22页/共179页2/17/2023 4:41 AM23k4G第23页/共179页2/17/2023 4:41 AM24定义1.6 设G=，G=为两个图，若V V且E E，则称为的子图，G G为G G的母图，记作；又若V V或E E，则称为的真子图。若V=V

11、，则称为的生成子图k4G2G1第24页/共179页2/17/2023 4:41 AM25在下图中，G1，G2，G3均是G的真子图，其中G2、G是G的生成子图。e3e2e1e4e5e7e6abdeGe3e2e1e4abdG1cce3e4e6abdeG2ce4e5adeG3第25页/共179页2/17/2023 4:41 AM26定义1.7 1.7 设G=G=是的子图，若给定另外一个图，使得=E-E=E-E，且中仅包含的边所关联的结点，则称为是子图相对于图G G的补图。GdbaecdbecGdbaeGdbaeG第26页/共179页2/17/2023 4:41 AM27定义1.8 1.8 设G G

12、1 1=V=,G,G2 2=V=为两个无向图，若存在一一映射 g g：V V1 1 V V2 2 对于 v vi i,v,vj j V V1 1，(v(vi i,v,vj j)E E1 1 当且仅当 (g(v(g(vi i),g(v),g(vj j)E E2 2,并且(v(vi i,v,vj j)与(g(v(g(vi i),g(v),g(vj j)的重数相同，则称G G1 1与G G2 2是同构的，记作G G1 1 G G2 2怎样定义有向图的同构？第27页/共179页2/17/2023 4:41 AM28例7、(d)第28页/共179页2/17/2023 4:41 AM29彼得松图(pete

13、rsen)1234567891012345689710第29页/共179页2/17/2023 4:41 AM30第30页/共179页2/17/2023 4:41 AM31两个图同构必有：（1）结点数相同；（2）边数相同；（3）度数列相同但不是充分条件（满足这三个条件的两图不一定同构）第31页/共179页2/17/2023 4:41 AM32例8、画出K4的所有非同构的生成子图。解：K4的所有非同构的生成子图如下图所示。第32页/共179页2/17/2023 4:41 AM33二、路与回路定义2.1 设为无向标定图，G G中结点与边的交替序列=v vi0i0e ej1j1v vi1i1e ej2

14、j2e ejljlv vilil称为v vi0i0到v vilil的路。v vi0i0，v vilil分别称为的始点和终点，中边的条数称为它的长度。当v vi0i0=v=vilil时，该路称为回路。e2v1v2v3v4e4e3e5e1第33页/共179页2/17/2023 4:41 AM34 若路中没有重复的边，则称为迹。若路中没有重复的点，则称为通路。闭的通路称为圈。e2v1v2v3v4e4e3e5e1第34页/共179页2/17/2023 4:41 AM35（5，1，2，3，4）是迹，不是通路，因为（，）中，均出现了两次。（c，d，b，c）是圈。有向图中，路、回路等概念与无向图类似第35

15、页/共179页2/17/2023 4:41 AM36 定理2.1 2.1 在n n阶图中，若从结点v vi i到v vj j（v vi i v vj j）存在一条路，则从v vi i到v vj j存在长度不大于n-1n-1的路。推论在n n阶图中，若从结点vi到vj（vivj）存在一条路，则从vi到vj存在长度小于n的通路。第36页/共179页2/17/2023 4:41 AM37定义2.2 2.2 设无向图，u,v，若u,v之间存在路，则称u,v是连通的，记作u v。定义2.3 设无向图是平凡图或G中任何两个结点都是连通的，则称G为连通图，否则称G为非连通图或分离图。任意一个连通无向图的任

16、两个不同结点都存在一条通路。第37页/共179页2/17/2023 4:41 AM38k4W（G）=1W（G）=2 非连通图可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为的连通分支,G,G的连通分支数记为W W（G G）。第38页/共179页2/17/2023 4:41 AM39设G=为无向图(1)设e E，用G-e表示从G中去掉边e，称为删除边e；又设E E，用G-E表示从G中删除E中的所有边，称为删除E。(2)设v V，用G-v表示从G中去掉v及所关联的一切边，称为删除结点v；又设V V，用G-V表示从G中删除V中所有结点，称为删除V。e第39页/共179页2/17/20

17、23 4:41 AM40定义2.4 2.4 设无向图为连通图，若存在V1 V，且V1，使得W(G-V1)1，而对于任意的V2 V1，均有W(G-V2)=1，则称V1是G的点割集，若是V1=v，则称v为割点。W(G)W(G)第40页/共179页2/17/2023 4:41 AM41定义2.5 2.5 设无向图，若存在E E，且E，使得W(G-E)W(G)，而对于任意的E E，均有W(G-E)=W(G)，则称E是G的边割集，若是E=e，则称e为割边或桥。第41页/共179页2/17/2023 4:41 AM42定义2.6 2.6 设为非完全的无向连通图，称(G)=min|V|V为G的点割集为G的点

18、连通度（或连通度）设为无向连通图，称(G)=min|E|E为G的边割集为G的边连通度。为了产生一个不连通图需要删去的最少的点数易见：非连通图的点连通度为0，边连通度也为0。完全图Kn的点连通度为n-1。第42页/共179页2/17/2023 4:41 AM43定理2.2 对于任何无向图G，有 (G)(G)(G)证明：若G不连通，则 (G)=(G)=0(G)若G连通 1）证(G)(G)若G是平凡图，则(G)=0(G)若G不是平凡图，则因每个结点的所有关联的边必含一个边割集，所以(G)(G)第43页/共179页2/17/2023 4:41 AM442）证(G)(G)设(G)=1，即有一割边，则(G

19、)=1 设(G)2，第44页/共179页2/17/2023 4:41 AM45定理2.3 一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u和w，使得结点u和w的每一条路都通过v。第45页/共179页2/17/2023 4:41 AM46定义2.7 2.7 设D=D=为有向图，vi，vj V V，若从vi到vj存在路，则称vi可达vj ，记作vivj，规定vivi ，如果vivj，且vjvi，则称vj与vi是互相可达的，记作vi vj 定义2.8 2.8 设D为有向图，vi，vj ，若vivj，称vi到vj长度最短的路称为vi 到vj的短程线，短程线的长度称为vi 到vj的距离，记

20、作d。易见 d 0 d+d d 如果从vi到vi不可达，则记为d=第46页/共179页2/17/2023 4:41 AM47定义2.9 2.9 设D=D=为简单有向图，若 vi，vj V V，vivj与vjvi至少有一个成立，则称D D是单侧连通图。若对 vi，vj V V，均有vi vj，则称D为强连通图。若在D D中略去边的方向，将它看成无向图后是连通图，则称为弱连通图。第47页/共179页2/17/2023 4:41 AM48定理2.4 2.4 设D D为有向图，D D是强连通图当且仅当D D中存在经过每个结点至少一次的回路。D D是单向连通图当且仅当D D中存在经过每个结点至少一次的路

21、。第48页/共179页2/17/2023 4:41 AM49定义2.10 2.10 在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图。定理2.5 2.5 在有向图D D中，它的每个结点位于且只位于一个强分图中。第49页/共179页2/17/2023 4:41 AM50三、图的矩阵表示图G的三种表示方法：（1）集合表示（2）图形表示（3）矩阵表示 1、邻接矩阵表示 2、关联矩阵表示第50页/共179页2/17/2023 4:41 AM51定义3.1 设无向图G=是简单图，V=v1,v2,vn,称(aij)nn为G

22、的邻接矩阵，记作A(G)，其中v1v2v3v40 1 1 01 0 1 11 1 0 10 1 1 0A(G)=此矩阵有何特征？对称aij=1 （vi，vj）E0 （vi，vj）E 或i=j第i行上1的个数等于结点vi的度数第51页/共179页2/17/2023 4:41 AM52定义3.1 设有向图D=，V=v1,v2,vn,E=e1,e2,em,令aij为顶点vi邻接到顶点vj的边的条数，则称(aij)nn为D的邻接矩阵，记作A(D)。v1v2v3v4V1V2V3v4 v1 v2 v3 v4 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0此矩阵有何特征？A(D)=第i行上1

23、的个数等于结点vi的出度，第j行上1的个数等于结点vj的入度第52页/共179页2/17/2023 4:41 AM53v1v2v3v4 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0A(D)=计算(A(D)2，(A(D)3v1v2v3v4对无向图G，计算(A(G)2，(A(G)3第53页/共179页2/17/2023 4:41 AM54定理3.1 设A为图G的邻接矩阵，V=v1,v2,vn为G的结点集，则A的k次幂Ak(k1)中元素aij(k)为G中vi到vj长度为k的路数，其中aii(k)为到自身长度为k的回路数，而 aij(k)i=1 j=1n n为G中长度为k的路的总数，

24、aii(k)i=1n其中为G中长度为k的回路总数。第54页/共179页2/17/2023 4:41 AM55定义3.2 设简单有向图D=，V=v1,v2,vn,令pij=1 vi可达 vj0 否则则称(pij)nn为D的可达矩阵，记作P(D)。v1v2v3v4e1e2e3e4e5V1V2V3v4 v1 v2 v3 v4 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1P(D)=第55页/共179页2/17/2023 4:41 AM56无向简单图G定义3.3 设无向图G=，V=v1,v2,vn,E=e1,e2,em,令mij为结点vi与边ej的关联次数，则称(mij)nm为G的关联

25、矩阵，记作M(G)。v1v2v3v4e1e4e3e2e510 0 0 11 1 1 0 00 0 1 1 10 1 0 1 0M(G)=此矩阵有何特征？第56页/共179页2/17/2023 4:41 AM57有向简单图D定义3.3 设有向图D=，V=v1,v2,vn,E=e1,e2,em,令则称(mij)nm为D的关联矩阵，记作M(D)。1 vi为ej的始点 0 vi与ej不关联-1 vi为ej的终点 mij=第57页/共179页2/17/2023 4:41 AM58v1v2v3v4e1e2e3e4e5V1V2V3v4e1 e2 e3 e4 e5 1 0 1 -1 1 0 0 0 1 -1

26、0 -1 -1 0 0-1 1 0 0 0M(D)=第58页/共179页2/17/2023 4:41 AM59 【例证明在n（n2）个人的团体中，总有两个人在此团体中恰好有相同个数的朋友。解以结点代表人，二人如果是朋友，则在代表他们的结点间连上一条边，这样可得无向简单图G，每个人的朋友数即图中代表它的结点的度数，于是问题转化为：n阶无向简单图G中必有两个结点的度数相同。用反证法，设G中各顶点的结数均不相同，则度数列为0，1，2，n-1，说明图中有孤立结点，这与有n-1度结点相矛盾（因为是简单图），所以必有两个结点的度数相同。第59页/共179页2/17/2023 4:41 AM60 【例一个

27、人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？第60页/共179页2/17/2023 4:41 AM61 解这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。集合f，w，s，h中能平安在一起的子集有：f，w，s，h，f，w，s，f，s，h，f，w，h，f，w，f，s，f，h，w，h，f，w，s，h。用顶点表示渡河过程中的状态，状态是二元组：第一元素是集合f，w，s，h在渡河过程中留在原岸的子集，第二元素是在彼岸的子集，将一次渡河后代表状态变化的顶点间连边，得图。

28、容易看出，一条路径就是一种渡河方案。第61页/共179页2/17/2023 4:41 AM62 图第62页/共179页2/17/2023 4:41 AM63 【例在一次国际会议中，由七人组成的小组a,b,c,d,e,f,g中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？第63页/共179页2/17/2023 4:41 AM64 解用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到图。问题归结为：在这个图中，任何两个顶点间是

29、否都存在着通路？由于图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。在连通图中，如果删去一些顶点或边，则可能会影响图的连通性。所谓从图中删去某个顶点v，就是将顶点v和与v关联的所有的边均删去，我们用G-v记之，并用G-V表示从G中删去V的子集V。用G-e表示删去边e，用G-E表示从G中删去E的子集E。第64页/共179页2/17/2023 4:41 AM65【例判断下列各命题是否是真命题。（1）任何有相同顶点数和边数的无向图都同构。（2）图中的初级回路均是简单回路。（3）任一图G的最大度数（G）必小于G的顶点数。（4）在n（n2）个人中，不认识另外奇数个人的有偶数个人。第6

30、5页/共179页2/17/2023 4:41 AM66 解答与分析（1）假命题。两个图有相同顶点数和边数是二图同构的必要条件，而非充分条件。（2）真命题。由初级回路和简单回路的定义可知。（3）假命题。当G非简单图时，（G）可大于顶点数。（4）真命题。将n个人抽象成n个顶点，若两个人不认识，则在他们的对应顶点之间画一条边，得到无向图G。G中每个顶点的度数就是该顶点所对应的人不认识的其他人的个数，由握手定理的推论可知，G中奇度数的顶点必有偶数个。故在n个人中，不认识另外奇数个人的有偶数个人。第66页/共179页2/17/2023 4:41 AM67 【例在六个人的团体中，至少有三个人彼此认识或彼此

31、不认识。分析将六个人抽象成六个顶点，若两个人认识，则在他们的对应顶点之间画一条边，得到无向图G，则G是6阶无向简单图，中的边则表示他们关联的两个顶点代表的人彼此不认识，本题即：证明G或它的补图中存在3个顶点彼此邻接。第67页/共179页2/17/2023 4:41 AM68图第68页/共179页2/17/2023 4:41 AM69 解因为K6是5-正则图，所以vV（G）（v（），d（v）在G中或在中大于等于3。不妨设在G中d（v）3，则v在G中至少关联三个顶点设为a、b、c（见图），若此三顶点在G中彼此不邻接，则必有三边（a，b）、（a，c）、（b，c）均在中（图中虚线），亦即a

32、、b、c三点在中彼此邻接，否则三顶点至少有两个在G中邻接，不妨设（a，b）E（G），则v、a、b为在G中彼此邻接的三顶点，故在G或中存在3个顶点彼此邻接。第69页/共179页2/17/2023 4:41 AM70 【例证明无向图G与其补图至少有一个是连通图。分析是G的补图，即G是一个无向完全图。对G中任一边e，若eE（G），则eE（）；反之若eE（），则eE（G）。又G与有相同的顶点集，故只需考虑G中的任意二顶点。若G是连通图，则命题已成立，所以不妨设G不是连通图。第70页/共179页2/17/2023 4:41 AM71 解假设G不是连通图，则G至少有两个连通分支，不妨设为G1、

33、G2。对于G中的任意二顶点u、v，设uG1，此时若vG2，则必有边（u，v），所以u、v在中连通。此时若vG2，即vG1,则必存在顶点wG2，使得（u，w）且（v，w），所以u、v仍在中连通。故是连通图。所以，G与其补图至少有一个是连通图。第71页/共179页2/17/2023 4:41 AM72习题八 3设图G有n个顶点，n+1条边，证明G中至少有一个顶点的度数大于等于3。4在简单图中若顶点数大于等于2，则至少有两个顶点的度数相同。第72页/共179页2/17/2023 4:41 AM73 6G是n阶无向简单图，n2为奇数，则G与G所含的奇度数顶点数相等。7证明图8.1中，图（a

34、）与（b）同构，图（c）与（d）不同构。8画出4阶无向完全图K4的所有非同构的子图，并指出哪些是生成子图和生成子图的互补情况。9画出3阶有向完全图的所有非同构的生成子图，指出每个图的补图和生成子图的互补情况。第73页/共179页2/17/2023 4:41 AM74 图 8.1 第74页/共179页2/17/2023 4:41 AM75 10如果一个图G同构于自己的补图G，则称该图为自补图。（1）有几个非同构的4阶和5阶的自补图？（2）是否有3阶和6阶的自补图？11G是n（n3）阶连通图，G没有桥，当且仅当对G的每一对顶点和每一条边，有一条连接这两个顶点而不含这条边的通路。12一个连通无向图G

35、中的顶点(是割点的充分必要条件是存在两个顶点u和w，使得顶点u和w之间的每一条路都通过v。第75页/共179页2/17/2023 4:41 AM76 13试求图8.2中有向图的所有强分图、单分图和弱分图。第76页/共179页2/17/2023 4:41 AM77图 8.2 第77页/共179页2/17/2023 4:41 AM78 15证明：图的每一个顶点和每一条边都只包含在一个弱分图中。16有向图G如图8.3所示，计算G的邻接矩阵的前4次幂，回答下列问题。（1）G中v1到v4的长度为4的通路有几条？（2）G中v1到v1的长度为4的回路有几条？第78页/共179页2/17/2023 4:41

36、AM79 （3）G中长度为4的通路总数是多少？其中有多少条是回路？（4）G中长度小于等于4的通路有几条？其中有多少条是回路？（5）写出G的可达矩阵。第79页/共179页2/17/2023 4:41 AM80图 8.3 第80页/共179页2/17/2023 4:41 AM81Konigsberg(Konigsberg(哥尼斯堡)七桥问题问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。离散数学第十五章欧拉图与哈密顿图四、欧拉图与哈密顿图欧拉图第81页/共179页2/17/2023 4:41 AM82 Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛

37、作为图的结点，七座桥为边，构成一个无向重图，问题化为图论中迹的问题。定义4.14.1 通过图中所有边一次且仅一次的路称为欧拉路。通过图中所有边一次且仅一次的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉路而无欧拉回路的图称为半欧拉图。离散数学第十五章欧拉图与哈密顿图第82页/共179页2/17/2023 4:41 AM83离散数学第十五章欧拉图与哈密顿图 e2v1v2v3v4e4e3e5e1第83页/共179页2/17/2023 4:41 AM84定理4.14.1 无向图G G是欧拉图当且仅当G G是连通的，且G G中没有奇度结点。定理4.24.2 无向图G G是半欧拉图当且仅当

38、G G是连通的，且G G中恰有两个奇度结点。离散数学第十五章欧拉图与哈密顿图哥尼斯堡七桥问题，由于四个结点都是奇度结点，不可能有欧拉回路。e2v1v2v3v4e4e3e5e1第84页/共179页2/17/2023 4:41 AM85如下图中（a）是欧拉图，图（b）是半欧拉图，图（c）既非欧拉图也非半欧拉图。第85页/共179页2/17/2023 4:41 AM86离散数学第十五章欧拉图与哈密顿图定义4.14.1 通过图中所有边一次且仅一次的单向路称为单向欧拉路。通过图中所有边一次且仅一次的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有单向欧拉路而无欧拉回路的图称为半欧拉图。第86页

39、/共179页2/17/2023 4:41 AM87离散数学第十五章欧拉图与哈密顿图定理4.34.3 有向图D D是欧拉图当且仅当D D是强连通的且每个结点的入度都等于出度。定理4.44.4 有向图D D是半欧拉图当且仅当D D是单向连通的，且D D中恰有两个奇度结点，其中一个的入度比出度大1 1，另一个的出度比入度大1 1，其余结点的入度都等于出度。第87页/共179页2/17/2023 4:41 AM88 当给定了一个欧拉图后，如何找出它的一条欧拉回路？下面的Fleury（于1921年提出）算法解决了这个问题，这个算法的实质是“避桥”。设G是欧拉图。（1）任选G的一个结点v0为起点，并设

40、零条边的路为l0=v0。（2）设已选好的迹为li=v0e1v1e2v2eivi，则按下述方法从E-e1，e2，ei中选取边ei+1：ei+1与vi关联；除非没有别的边可选择，否则ei+1不是Gi=G-e1，e2，ei的割边（桥）。（3）当第(2)步不能继续进行时（所有的边已走遍），算法终止。第88页/共179页2/17/2023 4:41 AM89 例找出下图的一条欧拉回路。解从v0出发，先找到l3=v0e1v1e2v4e3v5，因为此时在G3=G-e1，e2，e3中，关联v5的边e9和e10均是割边，所以只能选取e4，继续下去，最后可得一条欧拉回路：e1 0e1e9e3e4e2e5e6e

41、7e8105432v0e1v1e2v4e3v5e4v2e5v4e6v3e7v2e8v1e9v5e10v0第89页/共179页2/17/2023 4:41 AM90离散数学第十五章欧拉图与哈密顿图 v1v2v3v4v5v6v7v8v9e1e2e3e4e5e6e8e7e9e10e11e12e13e14v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2能不能走出欧拉回路？e10第90页/共179页2/17/2023 4:41 AM91应用与推广：一笔画问题离散数学第十五章欧拉图与哈密顿图第91页/共179页2/17/2023 4:41 AM92中国邮递员问题 (欧拉回路的应用)

42、()(带权图)问题:邮递员从邮局出发，走遍投递区域的所有街道，送完邮件后回到邮局，怎样使所走的路线全程最短。若街道图（街道的交叉口为结点）存在欧拉回路，显然此路是全程最短。离散数学第十五章欧拉图与哈密顿图第92页/共179页2/17/2023 4:41 AM93哈密顿图哈密顿图的概念源于1859年爱尔兰数学家威廉哈密顿爵士（SirWillianHamilton）提出的一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个结点看成是地球上的二十个城市，棱线看成连接城市的道路，要求游戏者沿着棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路，如图（a）所示。也就是在图（b）中找一条包

43、含所有结点的圈。第93页/共179页2/17/2023 4:41 AM94定义4.2 4.2 经过图中所有结点一次且仅一次的路称为哈密顿路，经过图中所有结点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图,具有哈密顿路但不具有哈密顿回路的图称为半哈密顿图。离散数学第十五章欧拉图与哈密顿图图不存在欧拉路，但有哈密顿路。图存在欧拉路，不存在哈密顿路。第94页/共179页2/17/2023 4:41 AM95乍一看，哈密顿图与欧拉图有某种对偶性,但实际上，前者的存在性问题比后者难得多。迄今为止，寻找到一个判断哈密顿图的切实可用的充分必要条件仍是图论中尚未解决的主要问题之一。人们

44、只是分别给出了一些必要条件和充分条件。第95页/共179页2/17/2023 4:41 AM96离散数学第十五章欧拉图与哈密顿图定理4.5 若无向图具有哈密顿回路，对于任意V1 V且V1，均有 W(G-V1)|V1|其中W(G-V1)是G-V1中连通分支数。abcdef第96页/共179页2/17/2023 4:41 AM97 证明设C是图G中的一条哈密顿回路，V1是V的任意非空子集，a1 V1，C-a1是一条通路，若再删去a2 V1，则当a1、a2邻接时，W（C-a1，a2）=12；而当a1、a2不邻接时，W（C-a1，a2）=2，即 W（C-a1，a2）2=|a1，a2|如此做下去，

45、归纳可证 W（C-V1）|V1|因为C-V1是G-V1的生成子图，所以 W（G-V1）P（C-V1）|V1|。第97页/共179页2/17/2023 4:41 AM98 这个定理给出的只是一个无向图是哈密顿图的必要条件，亦即哈密顿图必满足这个条件，满足这个条件的不一定是哈密顿图。例如，著名的彼得森（Petersen）图不是哈密顿图，但对任意的S V，S，均满足 W(C-S)|S|然而，不满足这个条件的必定不是哈密顿图。第98页/共179页2/17/2023 4:41 AM99定理4.6 设是阶无向简单图，如果对于G中任意不相邻的结点vi,vj，均有 d(vi)+d(vj)则中存在哈密顿路。离散

46、数学第十五章欧拉图与哈密顿图推论1 1 设是n n（）阶无向简单图，如果对于G中任意不相邻的结点vi,vj，均有 d(vi)+d(vj)则中存在哈密顿回路。推论2 设G是n（n3）阶无向简单图，若（G）n/2，则G是哈密顿图。推论3 完全图Kn（n3）均是哈密顿图。第99页/共179页2/17/2023 4:41 AM100 例、设n2，有2n个人参加宴会，每个人至少认识其中的n个人，怎样安排座位，使大家围坐在一起时，每个人的两旁坐着的均是与他相识的人？解：每个人用一个结点表示，若二人相识，则在其所表的结点间连边。这样得到一个2n阶的无向图，因为（G）n，所以u，vV（G），d（u）+d（

47、v）2n，故图中存在一条哈密顿回路，这条回路恰好对应一个座位的适当安排。第100页/共179页2/17/2023 4:41 AM101 货郎担问题与哈密顿图密切相关的是货郎担问题。设有n个村镇，已知每两个村镇之间的距离。一个货郎自某个村镇出发巡回售货，问这个货郎应该如何选择路线，使每个村镇经过一次且仅一次，并且总的行程最短。即在一个带权完全图中，找一个权最小的哈密顿图。第101页/共179页2/17/2023 4:41 AM102离散数学第十五章欧拉图与哈密顿图带权图 42820925167530321512第102页/共179页2/17/2023 4:41 AM103应用问题：旅行商问

48、题（TSPTSP）问题：从某地出发，恰好一次经过个城市回到原地，寻找最短的道路。实质：无向简单带权图，寻找最短的哈密顿回路。说明：（1 1）不一定存在，若无向图是完全图则存在。（2 2）图是连通的,两个城市间总有路,若以两城市间交通费用作为边的权,则是无向图的哈密顿回路。第103页/共179页2/17/2023 4:41 AM104无向加权完全图的最近邻域算法：从任一顶点出发，记为1 1，找一个与1 1最近的结点2 2，（1 1，2 2）为两个结点的迹。若找出有个结点的迹（1 1，2 2，p p），在迹外找一个离p p最近的结点，记为p+1p+1，将其加入则得到具有P+1P+1个结点的迹。

49、若，转，否则转。闭合哈密顿回路：增加一条边（n n，1 1），则（1 1，2 2，n n，1 1）为一条最短回路。第104页/共179页2/17/2023 4:41 AM105最近邻域法所求为：（，）总长为最短回路：（，）总长为。第105页/共179页2/17/2023 4:41 AM106 (2)以关联ei的两个结点v1,v2分别作为起点，用最近邻域法求最短H回路。(3)再比较这两条回路的长度，以确定最短的一条。如上例:（，）边长为，最短。以为起点：（，）总长为以作起点：（，）总长为改进:(1)找一条最短的边ei。第106页/共179页2/17/2023 4:41 AM107五、平面图定义

50、5.1 设G=为无向图，若能将V分成V1和V2(V1 V2=V，V1 V2=)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图(二分图)，称V1和V2为互补结点子集。若G是简单二部图，V1中每个结点均与V2中所有结点相邻，则称G为完全二部图，记为Kr,s，其中r=|V1|，s=|V2|n阶零图为二部图第107页/共179页2/17/2023 4:41 AM108V1V2第108页/共179页2/17/2023 4:41 AM109K3,3K2,3第109页/共179页2/17/2023 4:41 AM110定理5.1 一个无向图G=是二部图当且仅当G中无奇数长度的回

展开阅读全文