(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 ，有 对于中间点，有