离散数学课件-第6章-2.ppt

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

1、1离散数学Discrete Mathematics Chapter 6Graph Algorithms 32023/1/236.1 最短路径问题及算法最短路径问题及算法6.2 图的遍历、划分与关键路径图的遍历、划分与关键路径6.3 网网络流流图问题及算法及算法6.4 匹配理匹配理论及算法及算法42023/1/236.2 图的遍的遍历、划分与关、划分与关键路路径径 1.图的遍历图的遍历图的遍历图的遍历：从图的某顶点出发，访问图中所有：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。顶点，并且每个顶点仅访问一次。图的遍历算法：图的遍历算法：l深度优先搜索（深度优先搜索（Depth-Fi

2、rst Search）DFSl广度优先搜索（广度优先搜索（Breadth-First Search）BFS深度优先搜索（深度优先搜索（DFS）DFS（Depth-First Search）算法是图）算法是图论中最重要的算法之一，它的思路可以用论中最重要的算法之一，它的思路可以用迷迷宫法则宫法则来表述。下图是来表述。下图是1690年独裁者威廉王年独裁者威廉王修筑的迷宫示意图，现遗址在奥地利。修筑的迷宫示意图，现遗址在奥地利。xbdefclghijak一、迷宫法则一、迷宫法则 任务是从事先未知结构的迷宫入口出发，每个走任务是从事先未知结构的迷宫入口出发，每个走廊都要搜索，再从入口退出。廊都要搜索，

3、再从入口退出。为了不兜圈子尽快退出，要记住哪些走廊已经走为了不兜圈子尽快退出，要记住哪些走廊已经走过，沿着未走过的走廊尽可能地走下去，走到已无过，沿着未走过的走廊尽可能地走下去，走到已无未走过的走廊可走时，沿来路返回，到某一路口，未走过的走廊可走时，沿来路返回，到某一路口，发现可通往一条未走过的走廊时，沿此走廊搜索，发现可通往一条未走过的走廊时，沿此走廊搜索，依次类推，直至完成任务。依次类推，直至完成任务。迷宫法则迷宫法则一直往前走一直往前走碰壁就回头换条路走碰壁就回头换条路走沿途要记录走过的路线沿途要记录走过的路线老鼠走迷宫老鼠走迷宫dfs 1973年，用上述迷宫思想，年，用上述迷宫思想，H

4、opcroft和和Tarjan设计了下设计了下面有效的面有效的DFS算法。算法。dfs(v0)从从v0出发深度遍历出发深度遍历1、访问、访问v0visit(v0)；2、依次从、依次从v0未被访问未被访问的邻接点出发深度遍历。的邻接点出发深度遍历。容易看出，容易看出，dfs遍历遍历是一个递归搜索的过程是一个递归搜索的过程深度优先搜索过程：深度优先搜索过程：例例v0v1v3v5v4v2v6v7搜索回溯dfs(v0)v0v1v3v5v4v2v7v6序列：序列：v0-v1-v3-v5-v4-v2 v6-v7序列序列2：v0-v1-v4-v5-v3-v2-v7-v6由于没有规定由于没有规定访问邻接点的顺

5、序，访问邻接点的顺序，深度优先序列不是唯一的深度优先序列不是唯一的 左图所示的是左图所示的是DFS执行的示意图，标了执行的示意图，标了箭头的是箭头的是父子边父子边(以父以父为尾，子为头的搜索为尾，子为头的搜索边边)，它们导出的是生，它们导出的是生成树，称为成树，称为DFS生成生成树树。v0v1v3v5v4v2v6v7v0v1v3v5v4v2v7v6v0v1v3v5v4v2v6v7v0v1v3v5v4v2v7v6DFS生成树 可以看出，用可以看出，用dfs对迷宫进行搜对迷宫进行搜索，可以找出穿过索，可以找出穿过迷宫的路，但是不迷宫的路，但是不一定是最短的。如一定是最短的。如果要找出最短的，果要找

6、出最短的，则对迷宫进行则对迷宫进行bfs搜索。搜索。二、对搜索树进行二、对搜索树进行dfs搜索搜索N皇后问题：皇后问题：nn的棋盘上放置的棋盘上放置n个皇后，使之相互不能攻击。个皇后，使之相互不能攻击。现以现以4皇后问题为例。皇后问题为例。例例 为求解为求解n皇后问题，可采用穷举法，即把皇后问题，可采用穷举法，即把所有放置情况都列出来，然后搜索符合要所有放置情况都列出来，然后搜索符合要求的解。求的解。解解 12解解oooooxooooooxooxoooooxoooxoooxoxooxooooooo若不进行剪枝，则若不进行剪枝，则时间呈指数增长时间呈指数增长DFS算法举例算法举例背包问题：设有背

7、包问题：设有n个物品，其重量分别为：个物品，其重量分别为：w1，w2，w3，wn，所有物品的重量之和大于等于，所有物品的重量之和大于等于背包所能放置的重量背包所能放置的重量S。设计算法从中找出若干。设计算法从中找出若干物品放入背包，使其重量之和正好等于物品放入背包，使其重量之和正好等于S。在杂货店比赛中你获得了第一名，奖品是一车免在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有费杂货。店中有n 种不同的货物。规则规定从每种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为种货物中最多只能拿一件，车子的容量为C，物，物品品i 需占用需占用wi 的空间，价值为的空间，价值为pi。

8、试探法求解背包问题，可能会有下面三种情况：试探法求解背包问题，可能会有下面三种情况：（1）放置后正好符合条件，则输出；）放置后正好符合条件，则输出；（2）放置后，背包中重量）放置后，背包中重量S，则继续放置；，则继续放置；（3）放置后，背包中重量）放置后，背包中重量S，则将包里的物品依，则将包里的物品依次取出，换一种方案试探。次取出，换一种方案试探。现有现有5个不同重量的物品，重量分别为个不同重量的物品，重量分别为1，2，3，4，5kg，把物品放入能装，把物品放入能装6kg的背包里，保证背包为最满，的背包里，保证背包为最满，有几种放置方法？有几种放置方法？1234515141312132123

9、25242321广度优先搜索（广度优先搜索（BFS）BFS（Breadth-First Search）算法的描述）算法的描述bfs(v0)从从v0出发广度遍历出发广度遍历 1、访问、访问v0visit(v0)；2、依次访问、依次访问v0未被访问未被访问的邻接点；的邻接点；3、假设这一层访问的结点次序为、假设这一层访问的结点次序为vk1，vk2，vkm，依次访问，依次访问vk1，vk2，vkm未被访问未被访问的邻接的邻接点。点。广度优先搜索过程：广度优先搜索过程：v0v1v3v5v4v2v6v7bfs(v0)v0v1v3v5v4v2v7v6例例序列：序列：v0-v1-v2-v3-v4-v6-v7

10、-v5由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，广度优先序列不是唯一的广度优先序列不是唯一的搜索序列序列2：v0-v2-v1-v4-v3-v7-v6-v5BFS搜索过程记录的边构成搜索过程记录的边构成BFS生成树：生成树：v0v1v3v5v4v2v6v7bfs(v0)v0v1v3v5v4v2v7v6注注BFS算法的一个显著特点是：算法的一个显著特点是：层次性层次性。所以可以用来求两点间最短路径。所以可以用来求两点间最短路径。01入口入口出口出口0112.图的划分图的划分 划分的定义划分的定义：图：图G中，若顶点中，若顶点v G，将，将v及和及和v相关联相关联的边去掉，图的边去

11、掉，图G的连通分量数增加，则的连通分量数增加，则v称为图称为图G的的切割切割点点或者或者关节点关节点。1236543 定义定义：具有和切割点相同性质的边称为图：具有和切割点相同性质的边称为图G的的桥桥（割边）（割边）。1236547切割切割点点v的性质：的性质：先找出图先找出图G的的DFS生成树生成树（1）若）若v是根，则是根，则v的孩子数目的孩子数目2；（2）若）若v是非根，则是非根，则v的后代结点的后代结点不存在不存在到到v的祖先的后退边。的祖先的后退边。123654123654 num(v)表示表示dfs生成树中生成树中v的访问序号；的访问序号；low(v)表示表示v的后退边回到的顶点序

12、号；的后退边回到的顶点序号；low(v)的计算步骤：的计算步骤：(1)第一次访问第一次访问v，low(v)=num(v)；(2)遇到后退边遇到后退边(v,w)时，时，low(v)=minlow(v),num(w)(3)从从w回溯到回溯到v时，时，low(v)=minlow(v),low(w)这样，对图这样，对图G的的DFS生成树的所有顶点检查一生成树的所有顶点检查一次后，满足：次后，满足：low（w）num（v）的的v是切割点（充要条件）。是切割点（充要条件）。这里，这里，w是是v的的“儿子儿子”。（。（v非根）非根）求下图的切割点。求下图的切割点。例例v2v6v5v1v3v4假设从假设从v1

13、出发，求得的出发，求得的DFS生成树如下：生成树如下：v2v6v5v1v3v4解解num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)=6假设从假设从v1出发，检查所有顶点过程如下：出发，检查所有顶点过程如下：v2v6v5v1v3v4解解(1)low(v1)=num(v1)low(v1)=1num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)=6low(v3)=num(v3)low(v2)=2low(v2)=num(v2)low(v3)=3(2)DFS搜索搜索后退边后退边回溯回溯假设从假设从

14、v1出发，检查所有顶点过程如下：出发，检查所有顶点过程如下：v2v6v5v1v3v4解解(1)low(v1)=1num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)=6low(v3)=minnum(v1),low(v3)low(v2)=2low(v3)=3(2)(3)low(v3)=1DFS搜索搜索后退边后退边回溯回溯假设从假设从v1出发，检查所有顶点过程如下：出发，检查所有顶点过程如下：v2v6v5v1v3v4解解(1)low(v1)=1num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)

15、=6low(v4)=num(v4)low(v2)=2low(v3)=1(2)(3)(4)low(v4)=4low(v4)=minnum(v1),low(v4)low(v4)=1(5)low(v4)=minnum(v2),low(v4)(6)DFS搜索搜索后退边后退边回溯回溯low(v2)=2low(v3)=minlow(v3),low(v4)假设从假设从v1出发，检查所有顶点过程如下：出发，检查所有顶点过程如下：v2v6v5v1v3v4解解(1)low(v1)=1num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)=6low(v3)=1(2)

16、(3)(4)low(v4)=1(5)low(v2)=minlow(v2),low(v3)(6)DFS搜索搜索后退边后退边回溯回溯(7)(8)(9)low(v1)=minlow(v2),low(v1)low(v2)=1假设从假设从v1出发，检查所有顶点过程如下：出发，检查所有顶点过程如下：v2v6v5v1v3v4解解(1)low(v1)=1num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)=6low(v2)=1low(v3)=1(2)(3)(4)low(v4)=1(5)(6)DFS搜索搜索后退边后退边回溯回溯(7)(8)(9)(10)(11)

17、low(v5)=5low(v6)=6low(v5)=num(v5)low(v6)=num(v6)假设从假设从v1出发，检查所有顶点过程如下：出发，检查所有顶点过程如下：v2v6v5v1v3v4解解(1)low(v1)=1num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)=6low(v2)=1low(v3)=1(2)(3)(4)low(v4)=1(5)(6)DFS搜索搜索后退边后退边回溯回溯(7)(8)(9)(10)(11)low(v5)=5low(v6)=6low(v6)=minnum(v1),low(v6)(12)low(v6)=1假设从

18、假设从v1出发，检查所有顶点过程如下：出发，检查所有顶点过程如下：v2v6v5v1v3v4解解(1)low(v1)=1num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)=6low(v2)=1low(v3)=1(2)(3)(4)low(v4)=1(5)(6)DFS搜索搜索后退边后退边回溯回溯(7)(8)(9)(10)(11)low(v5)=5low(v6)=1low(v5)=minlow(v5),low(v6)(12)(13)(14)low(v1)=minlow(v1),low(v5)low(v5)=1求得各顶点的求得各顶点的low和和num

19、值如下：值如下：v2v6v5v1v3v4解解low(v1)=1num(v1)=1num(v2)=2num(v3)=3num(v4)=4num(v5)=5num(v6)=6low(v2)=1low(v3)=1low(v4)=1low(v5)=5low(v6)=1low(v5)=1lowlowlowlow（w w w w）numnumnumnum（v v v v）3.关键路径关键路径 按照软件生命周期，软件开发项目通常分为需求分析、总体设计、详细设计、实现、单元测试、集成测试、验收测试等各个阶段，而且当软件规模比较大的时候，又会分成几个子系统，每个子系统都有这些阶段，从而各个子系统的各阶段之间存在

20、复杂的时间约束关系，软件项目经理通常需要找出其中的关键步骤，从而控制软件开发的进度。我们先引入一些概念来对这种与关键路径有关问题进行建模。PERT图图定义：定义：PERT图是一个有向连通图图是一个有向连通图G=(V,E)，且：且：(1)每条边表示一个作业（工序），边的非负实数权表示完成该作每条边表示一个作业（工序），边的非负实数权表示完成该作业所需的时间；业所需的时间；(2)每个顶点表示以该顶点为起点的作业的开始，也表示以该顶点每个顶点表示以该顶点为起点的作业的开始，也表示以该顶点为终点的作业结束；为终点的作业结束；(3)作业开始条件作业开始条件：某条有向边：某条有向边e=所代表的作业可以开始

21、所代表的作业可以开始当且仅当以当且仅当以v为终点的有向边所代表的作业全部完成；为终点的有向边所代表的作业全部完成；(4)G没有有向回路，也没有环；没有有向回路，也没有环；(5)G中有且仅有一个顶点的入度为中有且仅有一个顶点的入度为0，称该顶点为，称该顶点为源点源点；同时；同时G中中有且仅有一个顶点的出度为有且仅有一个顶点的出度为0，称该顶点为，称该顶点为汇点汇点。实际上，对于实际上，对于实际上，对于实际上，对于PERTPERTPERTPERT图，我们主要关心其关键路图，我们主要关心其关键路图，我们主要关心其关键路图，我们主要关心其关键路径，以及每个作业的最早启动时间和最晚启动时间。径，以及每个

22、作业的最早启动时间和最晚启动时间。径，以及每个作业的最早启动时间和最晚启动时间。径，以及每个作业的最早启动时间和最晚启动时间。关键路径关键路径定义：给定定义：给定PERT图图G=(V,E)，关键路径：关键路径：关键路径：关键路径：G中从源点到汇点最长带权路径称为中从源点到汇点最长带权路径称为关键路径关键路径。关键路径。关键路径的长度的长度T为完成整个任务（即包括所有作业）所必需的最少时间。为完成整个任务（即包括所有作业）所必需的最少时间。关键作业：关键作业：关键作业：关键作业：关键路径上的边所代表的作业称为关键路径上的边所代表的作业称为关键作业关键作业。最早起动时间：最早起动时间：最早起动时间

23、：最早起动时间：对于某个作业对于某个作业e=，源点到该作业起点源点到该作业起点vk的的最最长路径长度长路径长度k k称为该作业的称为该作业的最早起动时间最早起动时间。最晚启动时间：最晚启动时间：最晚启动时间：最晚启动时间：设设vk到到汇点汇点的最长路径长度为的最长路径长度为k，则该作业可最则该作业可最晚于晚于k k=T k时间启动而不影响整个任务完成的预期时间时间启动而不影响整个任务完成的预期时间T，k k称称为该作业的为该作业的最晚启动时间最晚启动时间。很显然，作业很显然，作业很显然，作业很显然，作业e=e=e=e=是关键作业当且仅当是关键作业当且仅当是关键作业当且仅当是关键作业当且仅当k

24、k k k=k k k k，因为这时因为这时因为这时因为这时e e e e是是是是处于从源点到汇点最长带权路径上。所以，我们可通过求每个作业的最早处于从源点到汇点最长带权路径上。所以，我们可通过求每个作业的最早处于从源点到汇点最长带权路径上。所以，我们可通过求每个作业的最早处于从源点到汇点最长带权路径上。所以，我们可通过求每个作业的最早启动时间和最晚启动时间而得到启动时间和最晚启动时间而得到启动时间和最晚启动时间而得到启动时间和最晚启动时间而得到PERTPERTPERTPERT图的关键路径。图的关键路径。图的关键路径。图的关键路径。定理：设定理：设PERT图图G=(V,E)的顶点编号的顶点编号

25、v1,v2,vn，使得边使得边e=E蕴涵蕴涵ij。边 的非负实数权若 E；-否则；=w(vm,vj)令：1=0 j=maxm+w(vm,vj)|1 mj 则i(1in)是作业e=的最早启动时间。这里w(vm,vj)定义为：令：n=n k=mink,m-w(vk,vm)|km n 则i(1in)是作业e=的最晚启动时间。关键路径举例关键路径举例例子：考虑下面的例子：考虑下面的PERT图，求关键路径。图，求关键路径。5232443558161432723445注意顶点可看作一种状态，在该状态，所有以它为终点的作业都已经完成，而所有以它为起点的作业准备启动。为计算每个作业（边）的最早启动时间和最晚启

26、动时间，我们实际上计算每个顶点的最早启动时间和最晚启动时间，也即，某顶点的最早启动时间（最晚启动时间）就是所有以该顶点为起点的作业的最早启动时间（最晚启动时间）。5232443558161432723445我们先计算每个顶点的最早启动时间。最早启动时间的计算是从源点开始计算，源点的最早启动时间为0，对于顶点vi，只有在所有以vi为终点的边的起点vj的最早启动时间都计算出来之后，才能计算vi的最早启动时间，而且vi的最早启动时间i是：i=maxj+w(vj,vi)|E 1 1=0;3 3=max1 1+w(v1,v3)=max0+5=5;2 2=max1 1+w(v1,v2),3 3+w(v3,

27、v2)=max4,5+3=8;4 4=max1 1+w(v1,v4),3 3+w(v3,v4)=max2,5+1=6;5 5=max3 3+w(v3,v5),2 2+w(v2,v5)=max5+3,8+5=13;6 6=max2 2+w(v2,v6),5 5+w(v5,v6)=max8+4,13+4=17;7 7=max4 4+w(v4,v7),5 5+w(v5,v7)=max6+2,13+2=15;8 8=max5 5+w(v5,v8),6 6+w(v6,v8),7 7+w(v7,v8)=max13+4,17+5,15+3=22;得到源点得到源点v1v1到到汇点汇点v8v8的最长的最长带权路

28、径长度带权路径长度为为2222，这也是，这也是完成整个任务完成整个任务的必需时间。的必需时间。5232443558161432723445最晚启动时间的计算是从汇点开始计算，汇点的最晚启动时间等于其最早启动时间，对于顶点vi，只有在所有以vi为起点的边的终点vj的最晚启动时间都计算出来之后，才能计算vi的最晚启动时间，而且vi的最晚启动时间i 是：i=minj-w(vi,vj)|E 8 8=8 8=22;6 6=min8 8-w(v6,v8)=min22-5=17;7 7=min8 8-w(v7,v8)=min22-3=19;5 5=min6 6-w(v5,v6),7 7-w(v5,v7),8

29、 8-w(v5,v8)=min17-4,19-2,22-4=13;2 2=min6 6-w(v2,v6),5 5-w(v2,v5)=min17-4,13-5=8;4 4=min7 7-w(v4,v7)=min19-2=17;3 3=min2 2-w(v3,v2),4 4-w(v3,v4),5 5-w(v3,v5)=min8-3,17-1,13-3=5;1 1=min2 2-w(v1,v2),3 3-w(v1,v3),4 4-w(v1,v4)=min8-4,5-5,17-2=0;5232443558161432723445各点的最早启动时间和最晚启动时间如下表所示：定点定点VV1V2V3V4V5

30、V6V7V8最早启动时间最早启动时间085617131522最晚启动时间最晚启动时间0851717131922缓冲时间缓冲时间000110040根根据据各个各个顶点的顶点的最最早早启启动动时时间间和和最最晚晚启启动动时时间间可可以以确确定定PERT图图的的关关键键路路径径，即即凡凡是是最最早早启启动动时时间间等等于于最最晚晚启启动动时时间间的顶点的顶点就就是是处处于于关关键键路路径径的顶点的顶点。对对于于上上述述PERT图图，我我们们得到的得到的关关键键路路径就径就是是：v1v3v2v5v6v8定点定点VV1V2V3V4V5V6V7V8最早启动时间最早启动时间085617131522最晚启动时

31、间最晚启动时间0851717131922缓冲时间缓冲时间000110040 处于关键路径上的作业（边）就是关键作业，这些作业的完成时间必须处于关键路径上的作业（边）就是关键作业，这些作业的完成时间必须按照预期的时间完成，否则就会影响整个任务的完成时间，而处于非关键按照预期的时间完成，否则就会影响整个任务的完成时间，而处于非关键路径上的作业路径上的作业就允许有就允许有延误时间延误时间延误时间延误时间，其可以延误的时间等于，其可以延误的时间等于j i w(vi,vj)。例如，作业例如，作业的允许延误时间就是的允许延误时间就是 4 1 w(v1,v4)=15，也就是也就是说，该作业即使比原来预计的说，该作业即使比原来预计的2个时间再晚个时间再晚15个时间也能保证整个任务在个时间也能保证整个任务在22个时间内完成（当然前提是其他作业，特别是作业个时间内完成（当然前提是其他作业，特别是作业不再延迟）。不再延迟）。而作业而作业的允许时间是的允许时间是 7 4 w(v4,v7)=19-6-2=11。有时，我们简单地讨论顶点的有时，我们简单地讨论顶点的缓冲时间缓冲时间缓冲时间缓冲时间，顶点，顶点vi的缓冲时间等于的缓冲时间等于i i，各顶点的缓冲时间如上表所示。各顶点的缓冲时间如上表所示。本节内容到此结束本节内容到此结束