第八章图论第13节.ppt
《第八章图论第13节.ppt》由会员分享,可在线阅读,更多相关《第八章图论第13节.ppt(172页珍藏版)》请在三一文库上搜索。
1、第1页,第八章,图 论,第2页,第一节 图的基本知识 第二节 欧拉图与中国邮路问题 第三节 树 第四节 最短路(链)问题 第五节 网络最大流问题 第六节 最小费用流问题,第3页,1. 图论的产生,图论是运筹学应用十分广泛的一个分支。瑞士数学家欧拉(E Euler)于 1736 年发表了一篇题为“依据几何位置的解题方法”的论文,有效地解决了哥尼斯堡七桥难题(欧拉证明了每个点都只与奇数条线相关联,所以从某一点开始,不重复地走过7座桥,最后回到出发点是不可能的),这是有记载的第一篇图论论文,欧拉被公认为图论的创始人。,第4页,A,C,B,D,第5页,2. 图论的发展,1736 年 1936 年:匈牙
2、利数学家 O. Knig 于1936 年出版了名为有限图与无限图的理论,为图论研究的第一本专著。从 1736 年欧拉的第一篇论文,到这本专著的出版,前后经历 200 年之久,这一时期图论的发展是缓慢的。,第6页,1936年20世纪中期:电子计算机和离散数学问题的发展,使得作为提供离散数学模型的图论得以迅速发展。,目前图论被广泛应用到管理科学、计算机科学、信息论、控制论等各个领域,并取得了丰硕的成果。,第7页,第一节 图的基本知识,一、图的基本概念,1. 图,由一些点和一些点之间的连线所组成的二元组,称为图。,2. 顶点,图中点集 V = v i 中的元素 v i 称为顶点。,第8页,3. 边和
3、弧,图中,两顶点之间的连线为无向的(不带箭头),称为边,记为 E = ei 。一条连接顶点 vi 和 vj 的边记为 vi , vj 。,ei,vi,vj,第9页,图中,两顶点之间的连线为有向的(带箭头),称为弧,弧为 A = ai 。一条由顶点 vi 指向顶点 vj 的弧记为 ( vi , vj ) 。,ai,vj,vi,第10页,4. 有向图和无向图,由点和边所构成的图,称为无向图,记为 G= ( V, E ) ,式中 V 是无向图 G 的点集合; E 是无向图 G 的边集合。,由点和弧所构成的图,称为有向图,记为 D = ( V, A ) ,式中 V 是有向图的点集合G ; A 是有向图
4、 G 的弧集合。,第11页,无向图,有向图,第12页,5. 无向图中顶点数、边数的表示方式,顶点数:p(G),简记为p。,边 数:q(G),简记为q。,6. 有向图中顶点数、弧数的表示方式,顶点数:p(D),简记为p。,边 数:q(D),简记为q。,第13页,二、图的引申概念,1. 端点、始点、终点,无向图 G = ( V, E ) 中,边 e = u, v E,称顶点 u 和 v 是边 e 的端点,也称顶点 u 和 v 是相邻的。,e,u,v,第14页,有向图 D = ( V, A ) 中,弧 a = ( u, v ) A,称顶点 u 是弧 a 的始点,称顶点 v 是弧 a 的终点。,u,v
5、,第15页,2. 关联边(弧),无向图 G = ( V, E ) 中,边 e = u, v E,称边 e 是顶点 u 的关联边,也称边 e 是顶点 v 的关联边。,e,u,v,第16页,有向图 D = ( V, A ) 中,弧 a = ( u, v ) A,称弧 a 是始点 u 的关联弧,也称弧 a 是终点 v 的关联弧。,a,u,v,第17页,3. 多重边(弧),无向图 G = ( V, E ) 中,边 e1=u, v、e2=u, v、ek=u, vE,即两个端点 u 和 v 之间的边多于一条,称这些边为多重边。,ei,u,v,e1,ek,第18页,有向图 D = ( V, A ) 中,弧
6、a1=(u, v)、a2=(u, v)、ak=(u, v)A,即由始点 u 指向终点 v 的弧多于一条,称这些弧为多重弧。,ai,u,v,a1,ak,u,v,a1,a2,第19页,4. 环,无向图 G = ( V, E ) 中,边 e = u, u ,即边的两个端点相同,称该边为环。,u,e,第20页,有向图 D =( V, A ) 中,弧 a = (u, u) ,即弧的始点和终点相同,称该弧为环。,u,e,第21页,5. 简单图,无向图中,一个无多重边、无环的无向图,称为简单图。,有向图中,一个无多重弧、无环的有向图,称为简单图。,第22页,6. 多重图,无向图中,一个有多重边,但无环的无向
7、图,称为多重图。,有向图中,一个有多重弧,但无环的有向图,称为多重图。,第23页,简单图,多重图,例:,第24页,三、顶点的次,1. 顶点的次,在无向图中,以顶点 v 为端点的边的个数称为顶点 v 的次,记为 d(v)。 在有向图中,以顶点 v 为始点的弧数,称为顶点 v 的出次,记为 d + (v)。 在有向图中,以顶点 v 为终点的弧数,称为顶点 v 的入次,记为 d - (v)。 在有向图中,以顶点 v 的出次和入次之和,称为顶点 v 的次,记为 d(v)。,第25页,v1,v2,v3,v4,v5,v7,v6,e1,e2,e4,e5,e6,e3,e9,e8,e7,d(v1)=2,d(v2
8、)=2,d(v3)=4 d(v4)=3,d(v5)=3,d(v6)=2 d(v7)=2,第26页,注:环的顶点的次数为 2 次。,d(v1)=4,d(v2)=2, d(v2)=3,d(v4)=1,d(v5)=0,e2,e1,e3,e4,v1,v2,v3,v4,e5,v5,例:,第27页,2. 悬挂点、悬挂边、悬挂弧,次数为 1 的顶点称为悬挂点。 如上例中的顶点 v4。 无向图中,连接悬挂点的边称为悬挂边。 如上例中的边 e5。 有向图中,连接悬挂点的弧称为悬挂弧。,第28页,d(v4)=1,e2,e1,e3,e4,v1,v2,v3,v4,e5,v5,例:,第29页,3. 孤立点,次数为 0
9、的顶点称为孤立点。 如上例中的顶点 v5 。,4. 奇点,次数为奇数的顶点称为奇点。 如上例中的顶点 v3 和 v4 。,5. 偶点,次数为偶数的顶点称为偶点。 如上例中的顶点 v1 和 v2 。,第30页,d(v5)=0,e2,e1,e3,e4,v1,v2,v3,v4,e5,v5,例:,d(v3)=3,d(v4)=1,d(v1)=4,d(v2)=2,第31页,6. 三个定理,定理 1 任何图中,顶点次数的总和等于边数(弧数)的 2 倍,即,证明:计算各顶点的次数时,每条边都被它的端点各用了一次。,第32页,证明 9个工厂之间,不可能每个工厂只与其他 3 个工厂有业务联系。(P278页习题8.
10、1) 证:如果9个工厂均是与其他3个工厂有业务联系,则顶点的次数总和为27,是奇数而不是偶数,同定理1矛盾。,第33页,定理 2 任何图中,奇点的个数为偶数。,证明:设 V1 和 V2 分别是 G 中奇点和偶点的集合,由定理 1 可得,第34页,2q 和,均为偶数,2q -,为偶数,故,也为偶数,又因为 d (v)(vV1)的值为奇数,所以 d(v)(vV1)的个数为偶数。,第35页,证明 9个工厂之间,不可能只有4个工厂只与偶数个工厂有业务联系。 (P278页习题8.1) 证:如果只有4个工厂与偶数个工厂有业务联系,则另外5个工厂与奇数个工厂有业务联系。这5个工厂均为奇点,与定理2矛盾。,第
11、36页,定理 3 有向图中,所有顶点的入次之和等于所有顶点的出次之和,即,证明:计算各顶点的出次和入次时,每条弧都被它的端点各用了一次。,第37页,四、连通图,1. 链和路,第38页,在有向图 D = ( V, A )中,一个点、弧交错序列,如果满足,,则称为从,到,的一条路。,第39页,v1,v5,v2,v3,v4,a5,a4,a1,a2,a3,例:,(v1,a1,v2,a2,v3,a3,v4)不是一条路,因为弧a1(v1,v2),a3(v3,v4)。,第40页,2. 初等链和初等路,若链,中,点,均不相同,则称之为初等链。,注:初等链中点无相同的,边也无相同的。,第41页,注:初等路中点无
12、相同的,弧也无相同的。,中,点,均不相同,则称之为初等路。,若路,第42页,v1,v5,v2,v3,v4,a5,a4,a1,a2,a3,例:,(v1,a1,v2,a2,v3,a6,v1,a4,v5,a5,v4)不是一条初等路。,a6,第43页,3. 简单链和简单路,若链,中,边,均不相同,则称之为简单链。,注:简单链中边无相同的,但可有相同的点。,第44页,注:简单路中弧无相同的,但可有相同的点。,中,弧,均不相同,则称之为简单路。,若路,第45页,v1,v5,v2,v3,v4,a5,a4,a1,a2,a3,例:,(v1,a1,v2,a2,v3,a6,v1,a4,v5,a5,v4)不是一条初等
13、路,但是一条简单路。,a6,第46页,4. 圈和回路,在无向图 G = ( V, E ) 中,一个点、边交错序列,,如果满足,,且,为同一个点,则称此链为圈。,第47页,v1,v5,v2,v3,v4,a5,a4,a1,a2,a3,例:,(v1,a1,v2,a2,v3,a6,v1)是一个圈。,a6,第48页,,如果满足,,且,为同一个点,则称此路为回路。,在有向图 D = ( V, A ) 中,一个点、弧交错序列,第49页,v1,v5,v2,v3,v4,a5,a4,a1,a2,a3,(v1,a1,v2,a2,v3,a6,v1)是一个回路。,a6,例:,第50页,v1,v5,v2,v3,v4,a5
14、,a4,a1,a2,a3,(v1,a1,v2,a2,v3,a6,v1)不是一个回路。,a6,第51页,5. 初等圈和初等回路,若圈,中,点,都不相同,则称之为初等圈。,第52页,初等圈:(v1, v2, v3, v4, v1),v1,v2,v3,v4,v5,v7,v6,e1,e2,e4,e5,e6,e3,e9,e8,e7,第53页,(v4, v1, v2, v3, v5, v7, v6, v3 ,v4)不是一个初等圈。,v1,v2,v3,v4,v5,v7,v6,e1,e2,e4,e5,e6,e3,e9,e8,e7,第54页,6. 简单圈和简单回路,若圈,中,边,均不相同,则称之为简单圈。,若回
15、路,中,弧,都不相同,则称之为简单回路。,第55页,(v4, v1, v2, v3, v5, v7, v6, v3 ,v4)不是一个初等圈,但是一个简单圈。,v1,v2,v3,v4,v5,v7,v6,e1,e2,e4,e5,e6,e3,e9,e8,e7,第56页,7.连通图和不连通图,在无向图 G = (V, E) 中,若任意两个点之间,至少有一条链,则称 G 是连通图,否则称为不连通图。,第57页,在有向图 D = (V, A) 中,若任意两个点之间,至少有一条路,则称 D 是连通图,否则称为不连通图。,第58页,8. 连通图分图,若 G 或 D 是不连通图,则它的每个连通部分,称为 G 的
16、一个连通分图,简称分图。,第59页,上图中是一个不连通图,但它有两个连通分图。,例:,第60页,9. 生成(支撑)子图,给一个无向图 G = ( V, E ),如图,,使得,,则称,是 G,的一个生成(支撑)子图。,第61页,给一个无向图 D = ( V, A ),如图,,使得,,则称,是 D,的一个生成(支撑)子图。,第62页,例:,图G,图,图,为图 G 的一个生成(支撑)子图,第63页,10. G - v 图或 D - v 图,D - v:表示图 D 中去掉点 v 及 v 的关联弧后得到的一个图。,G - v:表示图 G 中去掉点 v 及 v 的关联边后得到的一个图。,第64页,例:,第
17、65页,11. 基础图,给一个有向图 D=(V, A) ,从 D 中去掉所有弧上的箭头(方向),从而得到一个无向图 G = (V , E),称之为 D 的基础图,记为 G ( D ) 。,第66页,五、图的矩阵表示,用矩阵表示图对研究图的性质及应用常常比较方便。图的矩阵表示方法主要有: 权矩阵 邻接矩阵,第67页,1. 权矩阵 网络赋权图 G=(V,E),其边 (vi,vj) 有权 wij ,构造矩阵 A=(aij)nn,其中,称矩阵 A=(aij)nn,为图 G 的权矩阵。,第68页,对角线上元素值为0,v1,v5,v4,v3,v2,7,4,2,4,3,8,5,6,9,第69页,2. 邻接矩
18、阵 对于图 G=(V,E),构造矩阵 A=(aij)mn,其中,称矩阵 A=(aij)nn,为图 G 的邻接矩阵。,第70页,v3,v1,v2,v5,v6,v4,第71页,一、欧拉图,欧拉路:连通图 G 中,若存在一条路,经过 G 中的所有边,且每边仅经过一次,则称这条路为欧拉路。 欧拉回路:连通图 G 中若存在一条回路,经过 G 中的所有边,且每边仅经过一次,则称这条回路为欧拉回路。 欧拉图:具有欧拉回路的图称为欧拉图。,第二节 欧拉图与中国邮路问题,第72页,欧拉路,经过所有边的简单路,欧拉回路,经过所有边的简单回路,第73页,定理1 无向连通图 G 是欧拉图,当且仅当 G 中无奇点。 证
19、明: (1)充分性:连通图G 为欧拉图 G 中无奇点。 因为 G 为欧拉图,则必然存在一条回路,经过 G 中 所有的边,且只经过一次。对于 G 中的任一顶点 vi ,只要回路中出现一次,必关联两条边,即一条边进入这点,再沿另一边离开这点。所以点 vi 虽然可以在回路中重复出现,但次数必为偶数。,第74页,(2)必要性:连通图G 中无奇点 G 为欧拉图。 因为连通图 G 中全部都是偶点,则从任一顶点 v1 出发,经关联边 e1 进入 v2 ,由于 v2 也是偶点,则必然可由 v2 经另外一条不同的关联边 e2 进入另外一个顶点 v3,如此进行下去,每边仅取一次。由于连通图 G 中点数是有限的,所
20、以这条路不能无休止地走下去,必然可以回到初始顶点 v1 ,从而得到一个回路 c1 。回路 c1 是否为欧拉回路只需验证 c1 是否包含连通图 G 中的所有边即可。,第75页, 若回路 c1 经过 G 的所有边,则 c1 就是欧拉回路,必要性得以证明。 若回路 c1 只经过 G 中的一部分边,则 c1 尚不是欧拉回路。 i) 从 G 中去掉 c1 后得到子图 G ,则 G 中每个顶点的次数仍为偶数。 Ii)在 G 中,重复前面 c1 的方法,得到回路 c2 。,第76页,iii)把 c1 与 c2 组合在一起,如果恰是图 G,则得到欧拉回路,否则重复上述步骤,得到回路 c3。 iv)依次类推。
21、由于图 G 中边数有限,最终可得一条经过图 G 所有边的回路,即欧拉回路。,第77页,该图无奇点,现在按照上述方法寻找欧拉回路。,c1,c2,c3,将c1、c2、c3组合起来,从而形成欧拉回路。,为欧拉图,第78页,欧拉图中欧拉回路的构造方法: 从图 G 中任一点 v1 出发,寻找一个初等回路 c1 。 从图 G 中去掉初等回路 c1 。 在剩余的图中再寻找初等回路 c2 。 从图 G 中去掉初等回路 c2 。 按此方法进行下去,直到图中所有边都包含在这些初等回路中。 把这些回路连接起来,从而得到即为欧拉回路。,第79页,A,C,B,D,d(A)=3,d(C)=5,d(B)=3,d(D)=3,
22、该连通图有4个奇点,不是欧拉图。,判断哥尼斯堡七桥难题,第80页,下图能否一笔画出?,可以一笔画出,因为该图为欧拉图。,c1,c2,c3,第81页,推论1 无向连通图 G 是欧拉图,当且仅当 G 的边集可划分为若干个初等回路。(由定理1的必要性证明过程可知。) 推论2 无向连通图 G 中存在欧拉路,当且仅当 G 中恰有两个奇点。,第82页,定理2 有向连通图 G 是欧拉图,当且仅当 G 中每个顶点的出次等于入次。 推论 有向连通图 G 有欧拉路,当且仅当这个图中除去两个顶点外,其余每一个顶点的出次等于入次,且这两个顶点中,一个顶点的入次比出次多1,另一个顶点的入次比出次少1。,第83页,二、中
23、国邮路问题,1962 年我国著名运筹数学家管梅谷教授提出中国邮路问题: 一个邮递员,负责某一地区的信件投递。每天要从邮局出发,走遍该地区所有街道再返回邮局,问应如何安排送信的路线,可以使所走的总路程最短?,第84页,中国邮路问题的图论描述: 给定一个连通图 G,每边有非负权 l(e),要求一条回路过每边至少一次,且满足总权最小。,第85页,分析: 如果 G 中没有奇点,则是一个欧拉图,按欧拉回路走就是最短路; 如果 G 中有奇点,要求连续走过每边至少一次,必然有些边不止走一次。,第86页,第三节 树,一、树的概念和性质,树是图论中结构最简单但又十分重要的一种图。,1. 定义,连通且不含圈的无向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 章图论第 13
链接地址:https://www.31doc.com/p-2981122.html