正在加载图片...
(1)破圈法 在图中任取一个圈,从圈中去掉一边,对余下的图重复这个步骤,直到图中不在包含圈为止。 在该方法中,去掉的边数为:边数点数+1。 (2)避圈法 由图的任一顶点开始,逐步生成该图的支撑树。 在该方法中,取出的边数为:点数-1。 (二)最小支撑树问题 给定图G=(八,E),对G中的每一条边vi,,相应地有一个数wj,则称这样的图G为赋权图,w称 为边ⅵ,上的权。图的所有树中权最小的树称为最小支撑树。 例第6章PPT第29-30页. 6.3最短路问题 给定一个网络图,问题:求网络中起点到其它点之间的一条最短路线。 最短路算法一Dijkstra(狄克斯拉)标号法 适用条件:所有权非负 基本思想:从1出发,逐步向外探寻最短路。算法中,与每个点对应,记录下一个数(称为这个点 的标号),它或者表示从1到该点的最短路的权(称为P(永久)标号),或者是从v1到该点最短 路的权的上界(称为T(临时)标号),方法的每 步是去修改T标号,并且把某一个具T标号的点改 变为具P标号的店 从而使图中具有P标号的顶点数多一个,这样,至多经过点数1步, 就可以求出 从v1到各点的最短路。 步骤: ①给Vs以P标号0,其它点给T标号+∞; ②从刚得到P标号的点k出发,按下式修改与其相邻的所有具有T标号的点的标号: ③从所有具有T标号点中选取一个最小值,将其改为P标号,然后重复步骤②,直至所有点都得到P 标号, 最短路问题应用举例,见第6章PPT第39-41页 6.4网络最大流问题 问题背景:如现实中的公路系统中的车辆流,供水系统中的水流,控制系统中的信息流,金融系统 中的现金流。 问题的提出:网络中存在流量限制时,求解一条线路使得从起点与终点之间可通过的流量最大。 (一)基本概念 1、设一个赋权有向图D=(八,E),在V中指定 一个发点vs和一个收点t,其它的点叫做中间点。对于D 中的每 个弧(ⅵ,∈E,都有一个非负数cj,叫做弧的容量。我们把这样的图D叫做一个容量网 络,简称网络,记做 D=(N,E,C). 网络D上的流,是指定义在弧集合E上的一个函数, 其中i,)=前叫做弧(ⅵ,上的流量。 2、称满足下列条件的流为可行流: (1)容量条件:对于每一个弧(ⅵ,0)∈E,有0≤cj】 (2)平衡条件: 对于发点vs,有 时干收点t,有 对于中间点,有(1)破圈法 在图中任取一个圈,从圈中去掉一边,对余下的图重复这个步骤,直到图中不在包含圈为止。 在该方法中,去掉的边数为:边数-点数+1 。 (2)避圈法 由图的任一顶点开始,逐步生成该图的支撑树。 在该方法中,取出的边数为:点数-1 。 (二)最小支撑树问题 给定图G=(V,E),对G中的每一条边[vi,vj],相应地有一个数wij,则称这样的图G为赋权图,wij称 为边[vi,vj]上的权。图的所有树中权最小的树称为最小支撑树。 例 第6章PPT第29-30页。 6.3 最短路问题 给定一个网络图,问题:求网络中起点到其它点之间的一条最短路线。 最短路算法—Dijkstra(狄克斯拉)标号法 适用条件:所有权非负 基本思想:从v1出发,逐步向外探寻最短路。算法中,与每个点对应,记录下一个数(称为这个点 的标号),它或者表示从 v1到该点的最短路的权(称为P(永久)标号),或者是从 v1到该点最短 路的权的上界(称为T(临时)标号),方法的每一步是去修改T标号,并且把某一个具T标号的点改 变为具P标号的点,从而使图中具有P标号的顶点数多一个,这样,至多经过点数-1步,就可以求出 从v1 到各点的最短路。 步骤: ①给vs 以P标号0,其它点给T标号+∞; ②从刚得到P标号的点vk出发,按下式修改与其相邻的所有具有T标号的点的标号; ③从所有具有T标号点中选取一个最小值,将其改为P标号,然后重复步骤②,直至所有点都得到P 标号。 最短路问题应用举例,见第6章PPT第39-41页。 6.4 网络最大流问题 问题背景:如现实中的公路系统中的车辆流,供水系统中的水流,控制系统中的信息流,金融系统 中的现金流。 问题的提出:网络中存在流量限制时,求解一条线路使得从起点与终点之间可通过的流量最大。 (一) 基本概念 1、设一个赋权有向图D=(V, E),在V中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D 中的每一个弧(vi , vj)∈E ,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网 络,简称网络,记做 D=(V,E,C)。 网络D上的流,是指定义在弧集合E上的一个函数, 其中f(vi ,vj) =fij 叫做弧(vi,vj)上的流量。 2、称满足下列条件的流为可行流: (1)容量条件:对于每一个弧(vi ,vj)∈E,有 0 fij ≤ cij 。 (2)平衡条件: 对于发点vs,有 对于收点vt ,有 对于中间点,有
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有