图的基本概念lly.pptx

《图的基本概念lly.pptx》由会员分享，可在线阅读，更多相关《图的基本概念lly.pptx（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1859年：哈密尔顿提出环游世界1920世纪：迷宫、棋盘上马的行走线路1852年：格色里(Guthrie)提出四色猜想第1页/共80页在工程科学中的应用：现实世界中，许多状态都可用图来描述，例如交通运输、城市规划、电 路网络、工作调配等都可以 用点和边连结的图来模拟。在计算机学科中，计算机网络、操作系统 数据库，数据结构等等都与图论 有重要的联系。第2页/共80页计计计计算算算算机机机机科科科科学学学学广广广广泛泛泛泛应应应应用用用用于于于于运运运运筹筹筹筹学学学学，信信信信息息息息论论论论，控控控控制制制制论论论论，网网网网络络络络理理理理论论论论，化化化化学学学学生生生生物物物物学学学学，

2、物物物物理理理理学学学学。原原原原因因因因在在在在于于于于这这这这些些些些学学学学科科科科的的的的许许许许多多多多实实实实际际际际问问问问题题题题和理论问题可以概括为图论。和理论问题可以概括为图论。和理论问题可以概括为图论。和理论问题可以概括为图论。第第第第七七七七、八八八八、九九九九章章章章介介介介绍绍绍绍与与与与计计计计算算算算机机机机科科科科学学学学关关关关系密切的图论内容及其在实际中的应用。系密切的图论内容及其在实际中的应用。系密切的图论内容及其在实际中的应用。系密切的图论内容及其在实际中的应用。第3页/共80页一、基本图类及相关概念8.1 8.1 无向图及有向图无向图及有向图 如右图

3、，这是不同于几何图形的另一数学结构。adcb 我们不关心边的长短与形状。但边可以是有方向的，有方向的边称为有向边，没有方向的边称为无向边。第4页/共80页称a,b|aAbB 为A与B的无序积，记作：A&B。习惯上，无序对a,b改记成(a,b)有序对(a,b)均用无序积无序积：设A，B为二集合，=(b,a)1.无向图第5页/共80页无向图：无向图G是一个二元组，其中(1)V是一个非空集 顶点集V(G)，每个元素为顶点或结点顶点或结点；(2)E是无序积V&V的可重子集可重子集(?元素可重复出现)，E 边集E(G)，E中元素称为无向边无向边。通常记：V=v1,v2,vn E=e1,e2,em 其中：

4、其中：ek=(vi,vj)第6页/共80页 实际中，图的画法：用小圆圈表示V中的每一个元素，如果(vi,vj)E，则在顶点vi与vj之间连线段。如(1)：G=，V=v1,v2,v3,v4，E=(v1,v2),(v1,v2),(v2,v3),(v2,v3),(v3,v4),(v2,v4),(v1,v4)v1v4v3v2e1e7e2e3e4e5e6(1)v4e1e2e3e4e5e6v1v2v3v5(2)如(2)：G=，V=v1,v2,v3,v4,v5，E=(v2,v2),(v1,v2),(v2,v3),(v1,v3),(v1,v3),(v1,v4)第7页/共80页有向图有向图：有向图D是一个二元组

5、，其中(1)V是非空集 顶点集 V(D)(2)E是笛卡尔积是笛卡尔积V V 的可重子集，的可重子集，其元素为有向边其元素为有向边 实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二元素。2.有向图第8页/共80页v1v4v3v2e1e2e3e4e5e6(a)v1v4v3v2e1e2e3e4e5e6(b)如(a)：D=，V=v1,v2,v3,v4，E=,如(b)：D=，V=v1,v2,v3,v4，E=,思考：与以前讲到的什么相似？第9页/共80页有限图：V，E均为有穷集合零 图：E 平凡图：E 且|V|=1(n,m)图：|V|=n 且|E|=m顶点与边关联：如果ek=(

6、vi,vj)E，称ek与vi关联关联，或ek与vj关联关联。3.相关概念v1v2v3v4v5v1e1e2e3e4e5e6v1v2v3v5(5,6)图v4第10页/共80页顶与顶相邻顶与顶相邻：如果如果ek=(vi,vj)E，称称vi与与vj相邻；相邻；边与边相邻边与边相邻：如果如果ek和和ei至少有一个公共顶点关联，至少有一个公共顶点关联，则称则称ek与与ei相邻相邻。若ek为有向边，则称vi邻接到vj,vj邻接于vi。ek=e1e2e3e4e5e6v1v2v3v5v4v1v4v3v2e1e2e3e4e5e6孤立点孤立点：无边关联的顶点。第11页/共80页平行边平行边：无向图中，关联一对结点的

7、无向边无向图中，关联一对结点的无向边多于一条，平行边的条数为多于一条，平行边的条数为重数重数；多重图多重图：?包含平行边的图。包含平行边的图。有向图中，关联一对顶点的有向边多于一条，且始、终点相同。简单图简单图：?既不包含平行边又不包含环的图。既不包含平行边又不包含环的图。环环：ek=中，若 vi=vj，则ek称为环。第12页/共80页例：判断多重图与简单图？v1v4v3v2e1e2e3e4e5e8e6e7v5e1e2e3e4e5v1v2v3v5v4e1e3e2e4v1v2v3v5v4第13页/共80页度：(1)在无向图G=中，与顶点v(vV)关联的边的数目 (每个环计算两次每个环计算两次)，

8、记作：d(v)。二、度e1e2e3e4e5e6v1v2v3v5v4思考：无向图中度与边的关系?第14页/共80页(2)在有向图D=中，以顶点v(vV)作为始点的边的数目，称为该顶点的出度，记作：d+(v)；出度与入度之和，称为顶点v的度：度是图的性质的重要判断依据。d(v)=d+(v)+d(v)以顶点v作为终点终点的边的数目，称为该顶点的入度入度，记作：d(v)。第15页/共80页例：v1v4v3v2e1e2e3e4e5e8e6e7v5d+(v1)=0,d-(v1)=1 d+(v2)=2,d-(v2)=2 d+(v3)=4,d-(v3)=1 d+(v4)=2,d-(v4)=4 d+(v5)=0

9、,d-(v5)=0 思考：有向图入度 ,出度及边的关系?第16页/共80页最大度最大度：(G)=max d(v)|v V最小度最小度：(G)=min d(v)|v V度与边数的关系度与边数的关系：在任何图中，顶点度数的总在任何图中，顶点度数的总和等于边数之和的两倍。和等于边数之和的两倍。握手定理的推论握手定理的推论：任何图中，度为奇数的顶任何图中，度为奇数的顶点个数一定为偶数。点个数一定为偶数。？(握手定理？)第17页/共80页出度与入度的关系出度与入度的关系：在有向图中，各顶点的出在有向图中，各顶点的出度之和等于各顶点的入度之和度之和等于各顶点的入度之和？。度数序列度数序列：设设V=v1,v

10、2,vn为图为图G的顶点集，的顶点集，称(d(v1),d(v2),d(vn)为G的度数序列。度数序列之和必为偶数(?)。第18页/共80页例例8.1 (3,3,2,3)，(1,3,3,3)能成为无向图的度数序列吗？能成为无向简单图的度数序列吗？(5,4,3,2,2)(4,4,3,3,2,2)?例例8.2 有向简单图的度数序列(3,3,3,3)，它的入度能为(1,1,1,1)吗？例8.3 已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G 中至少有多少个顶点？第19页/共80页正则图正则图：各顶点的度都相同的图为正则图；各顶点的度均为k的图为k次正则图。完全图完全图：(1)设G

11、=是n阶的无向简单图，如果G中任何一个顶点都与其余n1个顶点相邻，则G为无向完全图，记作：Kn。三、正则图与完全图思考：1)正则图与完全图关系（举例）2)n阶无向完全图中，总的边数？3)n阶无向简单图中，若 (G)=n-1,则 (G)=？第20页/共80页(2)设D=是n阶的有向简单图，如果D中任意顶点u，vV(uv)，即有有向边 ，又有有向边，则称D为n阶有向完全图。如：思考:1)n阶有向完全图中每个顶点的度数？总的边数？2)n阶有向完全图是多少次正则图。？3）完全图是简单图？1阶有向完全图？第21页/共80页四、子图与母图(1)G=，G=若VV，EE，则G是G的母图，G是G的子图，记作：G

12、 G。(2)若GG 且 V=V，则G是G的生成子图？。注：空图是有意义的，但一般求子图时，不将空图考虑其中第22页/共80页(3)设V1V，且V1，以V1为顶点集，以以两两端端点点均均在在V1中中的的全全体体边边为边集的G的子图，称为V1导出的导出子图导出的导出子图。(4)设E1E，且E1，以E1为边集，以以E1中边中边关联的顶点的全体关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图导出的导出子图。v1v4v3v2e1e2e3e4e5e8e6e7v5思考:V=v1,v2顶点集的导出子图?E=e1,e3为边集的导出子图?第23页/共80页例例8.3 列举下图的一些子图、真子图、生成子图

13、、导出子图。v3e3e1e2e4e5v4v1v2解：自己对照定义做一做！(1)子图：子图的定义？举例(2)真子图：举例(3)生成子图：定义？举例(4)导出子图：定义？举例e3e1e4v4v1v2图1图2思考：图1有多少个生成子图？第24页/共80页补图补图：给定一个图给定一个图G=，以，以V为顶点集，为顶点集，以所有能使G成为完全图的添加边组成边集的图。记作：G五、补图如:(1)(2)思考:构造补图的关键是什么？第25页/共80页相对补图相对补图：设：设G G,如果另一个图如果另一个图G=，满足满足(1)E=E E(2)V中仅包含E中的边所关联的结点。则G是子图G相对于G的补图。如：图为的子图

14、，则图(1)(2)(3)为(1)相对于(2)的补图。第26页/共80页图同构图同构：对于对于G=，G=，如果如果存在存在 g:VV 满足：满足：(1)任意边e=(vi,vj)E，当且仅当e=(g(vi),g(vj)E(2)e与e的重数相同则说G G 1）图是表达事物之间关系的工具，在画图时，由于顶点位置不同，边的曲直不同，同一事物之间的关系可能有不同形状来表示，从而引入同构图，应此同构图可以看成同一个图。2）由于同构图顶点之间一一对应，边之间一一对应，关联关系对应相同，判断同构图的必要条件:？举例说明六、同构图第27页/共80页例例8.4 画出4个顶点3条边的所有可能非同构的无向简单图。（3）

15、例例8.5 画出3个顶点2条边的所有可能非同构的有向简单图。（4）思考：思考：3顶点顶点3边的所有可能非同构的有向简单图？边的所有可能非同构的有向简单图？第28页/共80页例例8.5 3个顶点2条边的所有可能非同构的有向简单图。解：解：3个顶点2条边的无向简单图只有一个：由这个图可派生出下列4个非同构的有向简单图：G为n阶简单图，G为G补图，若G G称自补图；问：4个顶点3条边的所有非同构的无向简单图中有几个自补图？3阶有向完全图所有非同构生成子图中有几个自补图？第29页/共80页通路与回路：给定图G=，设G中顶点与边的交替序列 =v0 e1 v1 e2 el vl 满足：vi1vi是是ei的

16、的端端点点，(G为有向图时,要求vi1,vi分别为ei的始点、终点)，i=1,2,l，则为顶点v0到vl的通路通路。中边的数目l称为 的长度。v0=vl时，称为回路。(回路中必须有边？）一、通路与回路的概念8.2 8.2 通路、回路、图的连通性通路、回路、图的连通性第30页/共80页简单通路简单通路：=v0 e1 v1 e2 ek vk为通路且边边e1 e2 ek 互不相同互不相同，又称之为迹迹，可简用v0 v1 vk 来表示。简单回路(v0=vk)又称为闭迹。初级通路初级通路：=v0 e1 v1 e2 ek vk为通路且顶点顶点v0 v1 vk 互不相同。思考：思考：顶点顶点v0 v1 vk

17、 互不相同，边会相同吗？（反之？）互不相同，边会相同吗？（反之？）初级通路、简单通路及通路关系？初级通路、简单通路及通路关系？初级回路(圈)：v0=vk。第31页/共80页例例8.6 就下图中V1到 V3初级通路多少条?简单通路?通路?，V1到 V1长度为6的初级回路?简单回路?回路?。v1v5e2e5v2v3v4e1e7e3e6e4解：7,9,?,0,4,？(不考虑同构性)第32页/共80页二、通路与回路的性质：(1)在一个n阶图中，如果从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于n1的通路。证明证明：设vi vk vj为vi到vj的长度为L的一条通路，则序列中必必

18、有有L+1个顶点个顶点。如果Ln1，则此通路的顶点数L+1n，从而必有顶点从而必有顶点vs，它在序列中不止出现一次它在序列中不止出现一次，即有序列vi vs vs vj。在上述通路中，去掉去掉vs到到vs的这些边，至少去掉一条边后的这些边，至少去掉一条边后仍是仍是vi到到vj的一条通路。的一条通路。此通路比原来通路长度至少少1。如此重复下去如此重复下去，必可得到一条从vi到vj的不多于n1条边的通路。第33页/共80页(2)在n阶图中，如果从vi到vj(vivj)存在通路，则必存在从vi到vj 的长度小于等于长度小于等于 n1的初级初级通路通路。（简单通路？）(3)在n阶图中，如果存在从vi到

19、自身的回路，则从vi 到自身存在长度小于等于长度小于等于n的回路的回路。(4)在n阶图中，如果从vi到自身存在一条简单回路，则从vi 到自身存在长度小于等于长度小于等于n的的初级回路初级回路。思考思考：在在n阶图中，若两点之间存在阶图中，若两点之间存在初级初级通路，通路，则其长度则其长度一定一定小于等于小于等于 n1？若为简单通路若为简单通路？思考：在n阶图中，如果从vi到自身存在一条初级回路，则从vi 到自身的长度一定小于等于n？（简单回路？）第34页/共80页两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。连连 通通 图图：G 中任何两个顶点是连通任何两个顶点是连通的；否则是分

20、离图分离图。三、无向图的连通性连通分支：无向图G中每个划分块称为G的一个连连通通分分支支，p(G)表示连通分支的个数。p(G)=？为连通图。第35页/共80页连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系等价关系。(1)自反性：由于规定任何顶点到自身总是连通的；证明：(2)对称性：无向图中顶点之间的连通是相互的；(3)传递性：由连通性的定义可知。第36页/共80页四、有向图的连通性：(1)如果有向图 D=中所有有向边的方向去掉所有有向边的方向去掉后所得图为后所得图为无向连通图无向连通图，则说D为弱连通图弱连通图。(2)弱连通图中，任何一对顶点之间，至少有一任何一对顶点之间，至少

21、有一顶点可达另一个顶点顶点可达另一个顶点，则 是单向连通单向连通的；(3)任何两个顶点之间互相可达，称强连通。思考：思考：弱连通、单向连通、强连通关系弱连通、单向连通、强连通关系？图1图2图3v1v1v1v2v2v2v3v3v3v4v4v4第37页/共80页有向连通图的判定有向连通图的判定：仅仅弱连通:有向连通图中至少有两个以上顶点为全入度或全出度单向连通:依次从各顶点出发,寻找到其他所有顶点的可达性.-(存在经过每点至少一次的通路)强连通的充要条件:当且仅当D中存在一条回路，它至少经过每个顶点一次.-(存在经过每点至少一次的回路)第38页/共80页有向图D强连通，当且仅当D中存在一条回路，它

22、至少经过每个顶点一次。(充充分分性性)如果D中存在回路，它经过D中的每个顶点至少一次，则D中中的的任任意意两两个个顶顶点点都都在在回回路路中，以，D中任意两个顶点都是可达，因而D是强连通。(必要性必要性)D是强连通的，则D中任何两个顶点都中任何两个顶点都是可达的是可达的。不妨设D中的顶点为v1,v2,vn，因为vi可达vi+1,i=1,2,，n1，让这些通路首尾相连，所以vi到vi+1存在通路，且vn到v1也存在通路，则得一回一回路路。显然每个顶点在回路中至少出现一次。证明：第39页/共80页点割集：无向图G=，如果存在顶点集VV 1)在G中删删除除V中中所所有有顶顶点点(包包括括与与该该顶顶

23、点点关关联联的的边边)后后所得子图G-V的连通分支数与G的连通分支数满足P(G-V)P(G)，2)而删删除除V中中任任何何真真子子集集V”后P(G-V”)=P(G)，则V是G的点割集。如果点割集中只有一个顶点，该点为割点。五、割集思考：如果点割集中顶点1，点割集中会含割点吗？第40页/共80页边割集：设无向图G=，存在边集EE 1)在G中删删除除E中中所所有有边边(不不包包括括边边关关联联的的顶顶点点)后所得子图G-E的连通分支数与G的连通分支数满足P(G-E)P(G)，2）而删删除除E中中任任何何真真子子集集E”后P(G-E”)=P(G)，则E是G的边割集。如果边割集中只有一边时，该边为割边

24、(或桥)思考：如果边割集中边数1，边割集中会含割边吗？第41页/共80页1)V2,V4 是点割集？2)V6,V1,V5是点割集？V6是割点？V1？V5？3)e9,e7,e8是边割集？e9是割边？4)e8,e7是边割集？e8,e7，e1是边割集?e3e1e2e4e5v4v1v2v3v5v6v7e6e8e7e9点割集中不会含其有它点割集？边割集中不会含有其他边割集？看P 292 21(1).43第42页/共80页无向图关联矩阵：(1)设G=为(n,m)无向图,V=v1,v2,vn,E=e1,e2,em,令：mij=10称M(G)=(mij)nm为G的关联矩阵。vi 关联 ej（环?2）vi 不关联

25、 ej一、关联矩阵及其性质8.3 8.3 图的矩阵表示图的矩阵表示v4e1e2e3e4e5v1v2v3强调：顶点与边的关系，(mij)nm行n为？m为？第43页/共80页无向图的关联矩阵的性质无向图的关联矩阵的性质：(?定理)v4e1e2e3e4e5v1v2v3 1 1 1 0 0 0 1 1 1 0 1 0 0 1 2 0 0 0 0 0(?图与矩阵)第44页/共80页(2)设D=是有向图且无环无环，令：mij=10则称M(D)=(mij)nm为D的关联矩阵。1D中 vi 是 ej 的始点vi 与 ej 不关联vi 是 ej 的终点有向图关联矩阵v1v4v3v2e1e2e3e4强调：顶点与边

26、的关系，(mij)nm行n为？m为？第45页/共80页有向图的关联矩阵的性质有向图的关联矩阵的性质：孤立点孤立点？两列相同两列相同？有向图的关联矩阵所有元素之和为有向图的关联矩阵所有元素之和为？v1v4v3v2e1e2e3e4 -1 0 0 0 1 -1 0 0 0 1 -1 1 0 0 1 -1 (?图与矩阵)第46页/共80页邻接矩阵邻接矩阵：设G=是一个图，它有n个顶点，V=v1,v2,vn，令aij=x E (或(vi,vj)E 环?2)0 E(或(vi,vj)E)称A(G)=(aij)为G的邻接矩阵。二、邻接矩阵及其性质v1v4v3v2e1e2e3e4e5e6强调：顶点与顶点的关系，

27、(aij)nn行n为？v4e1e2e3e4e5v1v2v3第47页/共80页无向图邻接矩阵的特性：(1)邻接阵是对称阵；(2)同一行或者同一列的元素和为对应顶点的度数(3)矩阵中所有元素的和为边数的2倍 0 2 1 0 2 0 1 0 1 1 2 0 0 0 0 0 v4e1e2e3e4e5v1v2v3(?图与矩阵)第48页/共80页有向图邻接矩阵的特性(1)同一行的元素和为对应顶点的出度(2)同一列的元素和为对应顶点的入度(3)aij=？v1v4v3v2e1e2e3e4e5e6 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 (?图与矩阵)强调：对无向图环计2次，对有向图环计

28、1次？第49页/共80页三、应用三、应用v4v1v2v3问：1）求此图中长度为1通路总数与回路总数？2）求此图中长度为2通路总数与回路总数？3）求此图中长度为3通路总数与回路总数？4、5、n?4）求此图中长度小于4的通路总数与回路总数？第50页/共80页 1 2 1 0 0 0 1 0 0 0 0 1 0 0 1 0 v4v1v2v3A=A2=1 2 3 1 0 0 0 1 0 0 1 0 0 0 0 1 1 2 4 3 0 0 1 0 0 0 0 1 0 0 1 0 1 2 6 4 0 0 0 1 0 0 1 0 0 0 0 1 A3=A4=求此图中长度为n通路总数与回路总数？长度小于或等于

29、n通路总数与回路总数？单向连通图？第51页/共80页通路数与回路数的矩阵算法：设A是有向图D的邻接矩阵，V=v1,v2,vn，Al(l1)中元素aij(l)为为vi到到vj长度为长度为l的通路数的通路数通路总数回路数1.求通路数与回路数(1)求图中长度为n通路总数与回路总数第52页/共80页 设A是有向图D的邻接矩阵，B1=A，B2=A+A2,，Br=A+A2+Ar，则Br中元素bij(r)为D中vi到vj长度小于等于长度小于等于 r 的通的通路数路数。(2)求图中长度小于或等于r的通路总数与回路总数第53页/共80页设D=为一有向图，V=v1,v2,vn，令pij=10i jpii=1 i=

30、1,2,n 称(pij)nn 为D的可达矩阵。vi 可达 vj否则(3).求可达矩阵第54页/共80页可达矩阵的求法：由邻接矩阵A计算A2,A+A2,A+A2+A(r)=B=(bij(r)nn pij=1 bij(r)00 bij(r)=0则 i jpii=1即得可达矩阵 P(D)=(pij)nxn 说明:求通路r|v|;求回路r=|v|第55页/共80页例.求下图的可达矩阵，判断它是否为强连通图？V1V4V2V3V5解：1.写出邻接矩阵第56页/共80页2.计算 A2,A3,A4,A5.第57页/共80页3.计算 B=A+A2+A3+A4+A5,并求出思考：若是单向连通图，其可达矩阵应满足什

31、么？第58页/共80页习题若D是具有结点 V1,V2,V3,V4的有向图，它的邻接矩阵表示为：0，1，0，1 0，1，2，0 1，0，0，1 1，0，0，01)画出此图2)D是单向连通，还是强连通？说明理由3)求该图中长度小于等于3的通路与回路总数4)可达矩阵看P196 6.24第59页/共80页带权图：对于有向图或无向图的每条边附加一个非零正实数w(e)，则得带权图带权图。如果G1是带权图G的子图，称w(e)为边e上的权(当e=时，权记作wij)，记作：G=一、带权图及其最短路径问题8.4 8.4 最短路径问题最短路径问题第60页/共80页G=为带权图，且G中各边带的权均大于等于0，从顶点顶

32、点u到顶点到顶点v的所有通路中求带权最小的通的所有通路中求带权最小的通路问题路问题，称为最短路径问题（最短路径问题（一般为简单图一般为简单图）。最短路径问题：如果如果v1v2 vn1vn是是v1到到vn的最短路径，则的最短路径，则v1v2 vn1也必然是也必然是v1从到从到vn1的最短路径的最短路径。求最短路径的戴克斯德拉(Dijkstra)算法基本思想：思考：从始点到终点的最短路径，必然是始点到该路径上各点的 最短路径？也必然是该路径上各点到终点 的 最短路径？最短路径 唯一？第61页/共80页G=,V=v1,v2,.vn,W=(wij)nxn是距离矩阵是距离矩阵二、求最短路径的戴克斯德拉(

33、DijkstraDijkstra)算法求v1点到其他各点的距离的Dijkstra算法：l(vi)表示vi点到v1的最短距离，A V(1)初始化：A=v1，=Vv1，l(v1)=0，l(vi)=，i为2,3,n。i=0(2)若 为空集，打印A，否则转（3）(3)对vi 所有点计算：vjAl(vi)=minl(vi),l(vj)+w ji(4)令l(vi+1)=min l(v)，A=Avi+1，=vi+1 i=i+1，转（2）v第62页/共80页算法解释：求v1点到其他各点的距离的Dijkstra算法：距离矩阵：相同点0，相邻点距离为权，否则A=v1,=V-v1；=则打印A，否则继续；在 中找与A

34、相邻的所有点，计算计算它们到v1的最短距离；在 中选择选择各点最短距离的最短点，将其加入到A中，同时删除 此点，转第2 步。第63页/共80页例8.7 求下图中顶点v0与v5之间的最短路径v0v2v1v4v3v5121475326第64页/共80页例:求下图中顶点v0与v5之间的最短路径v1v31v0v2v4v512145126第65页/共80页Dijkstra算法（又称标号）说明：(1)可求任何顶点Vs到其它任一顶点之间的最短路径，只是算法的“开始”步中,顶点Vs加入A，然后算法往下计算。(2)若已经求出从vi到vj的最短路径，则从vi到此路径上其余各顶点的最短路径也都求出了。第66页/共8

35、0页关键路径问题关键路径问题 实施一个工程计划时，若将整个工程分成若干个工序，有些工序可同时实施，有些工序必须在完成另外一些工序后才能实施，工序之间的次序可用有向图表示，该图称为PERT图（计划评审图），特点：有向连通图；简单图；无回路；一个顶点入度为0（发点），一个顶点出度为0（收点）带权（非负）图。记权为 wij，一般表示时间第67页/共80页设D=为有向图，vV，称 D+（v）=x|xV E 为v的后继元素；D-（v）=x|xV E 为v的先驱元素。关键路径关键路径就是指从发点到收点的的一条最长路径就是指从发点到收点的的一条最长路径。求项目工程完成的最早时间问题就是关键路径问题，关键路径

36、问题，因为关键路径上任何点时间的耽误，就是整个工程的因为关键路径上任何点时间的耽误，就是整个工程的耽误。耽误。第68页/共80页vj D-(vi)TE(vi)=max (TE(vj)+wji)i=2,3nvi点最早完成时间TE(vi)：自发点（记v1）开始沿最长路径到vi点所需的时间。TE(v1)=0vj D+(vi)TL(vi)=min (TL(vj)-wij)i=1,2,n-1vi点最晚完成时间TL(vi)：在保证收点vn最早完成时间不变的条件下，自v1最迟到vi点所需的时间。TL(vn)=TE(vn)vi点缓冲时间 TS(vi)=TL(vi)-TE(vi)：。因为关键路径上任何点时间的耽

37、误因为关键路径上任何点时间的耽误t t，就是整个工程的，就是整个工程的耽误耽误t t ，所以，所以关键关键路径上各点路径上各点缓冲时间 为0第69页/共80页例8.8 求下图各顶点最早、最晚完成时间及关键路径v1v3v2v4v5124343112v6v7v80446注意：求vi最早完成时间前必须求出其所有先驱点的最早完成时间，故从发点开始求；求vi最晚完成时间必须求出其所有后继点的最迟完成时间，故从收点开始求；收点的最早完成时间等于最晚完成时间。第70页/共80页如果存在一条通路，它经过G的每条每条边一次且仅一次边一次且仅一次，并且行遍图中并且行遍图中每每个个顶点顶点，则称该通路为欧拉通路欧拉

38、通路；具有欧拉回路的图 欧拉图。欧拉图：给定无孤立顶点的图G，存在一条回路，它经过G每条边一次且仅一次，并且行遍图中每个顶点，则此回路为欧拉回路。如果8.5 8.5 欧拉图与哈密尔顿图欧拉图与哈密尔顿图思考：欧拉通路是简单通路？反之呢？欧拉通路是初级通路？欧拉图是否一定存在欧拉通路？有向欧拉图是强连通图？反之呢？第71页/共80页例8.8 下列图哪些为欧拉图？哪些存在欧拉通道？：(1)(2)(3)(4)第72页/共80页欧拉图的判定定理（必须掌握！说明理由）(1)无向图G具有一条欧拉回路，当且仅当G是连连通通的，并且所有顶点的度度数数全全为偶数为偶数；(2)有向图D具有单向欧拉回路，当且仅当D

39、是连连通通的，并且每个顶点的入入度度等等于出度于出度。证明较复杂(略)，反证思维理解！第73页/共80页(1)无向图G有欧拉通路，当且仅当它连通连通且有零个或两个零个或两个奇数度顶点；(2)有向图D有欧拉通路，当且仅当它连通连通且除除两个除顶点外两个除顶点外，各顶点的入度均等于出度入度均等于出度，或者各顶点的入度均等于出度入度均等于出度。此两个特殊顶点中，一个顶点的入度比出度大1，而另一个顶点的出度比大入度1;欧拉通路的判定定理：（必须掌握！说明理由）证明较复杂(略)，反证思维理解！第74页/共80页哈密尔顿图：给定图G，如果存在一条经过G的每个每个顶点一次且恰好一次顶点一次且恰好一次的通路(

40、回路)，则称该通路(回路)为哈为哈密尔顿通路密尔顿通路(回路回路)。具有哈密尔顿回路的图称为哈密尔顿图。哈密尔顿图是否一定是初级回路？反之呢？哈密尔顿图是否一定存在哈密尔顿通路？有向哈密尔顿图是强连通图？反之呢？哈密尔顿图的充分必要条件至今仍未解决。第75页/共80页例8.8 下列图哪些为哈密尔顿图？哪些存在哈密尔顿通道？：(1)(2)(3)(4)思考：哈密尔顿图与欧拉图有联系吗？第76页/共80页小结与学习要求小结与学习要求1.本本章章围围绕绕图图中中元元素素间间的的邻邻接接与与关关联联关关系系讨讨论论了了图图论论中中几几个个基基本本问问题题：图图的的连连通通性性问问题题，道路问题，可达性问

41、题，最短路径问题。道路问题，可达性问题，最短路径问题。2.要要仔仔细细领领会会和和掌掌握握下下列列基基本本概概念念和和相相关关结结论论：子子图图、度度、通通路路、回回路路、支支、割割点点，割割边，独立点，权，补图，同构图等。边，独立点，权，补图，同构图等。3.熟练掌握标号法。熟练掌握标号法。第77页/共80页例：v1v4v3v2e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5v4第78页/共80页例：v1v4v3v2e1e2e3e4e5e8e6e7v5d+(v1)=0,d-(v1)=1 d+(v2)=2,d-(v2)=2 d+(v3)=4,d-(v3)=1 d+(v4)=2,d-(v4)=4 d+(v5)=0,d-(v5)=0 第79页/共80页感谢您的观看。第80页/共80页