第七章 图与网络模型.ppt

1 第七章图与网络模型 1图与网络的基本概念 2最小生成树问题 3最短路问题 4最大流问题 2 1图与网络的基本概念 图论中图是由点和边构成 可以反映一些对象之间的关系 例如 在一个人群中 对相互认识这个关系我们可以用图来表示 下图就是一个表示这种关系的图 3 1图与网络的基本概念 当然图论不仅仅是要描述对象之间关系 还要研究特定关系之间的内在规律 一般情况下图中点的相对位置如何 点与点之间联线的长短曲直 对于反映对象之间的关系并不是重要的 如对赵等七人的相互认识关系我们也可以用图来表示 可见图论中的图与几何图 工程图是不一样的 4 1图与网络的基本概念 一 图的三要素顶点无序的图为无向图 顶点有序的图为有向图 二 链一个由点和边的交替序列 三 回路 圈 若链的第一个点和最后一个点相同 则该路为回路 圈 5 1图与网络的基本概念 四 连通图对无向图G 若任何两个不同的点之间 至少存在一条链 则G为连通图 五 子图及生成子图1 子图设无向图G V E 若2 生成子图 6 1图与网络的基本概念 六 赋权图对一个无向图G的每一条边 Vi Vj 相应地有一个数Cij 则称图G为赋权图 Cij称为边 Vi Vj 上的权 七 网络在赋权的有向图D中指定一点 称为发点 指定另一点称为收点 其它点称为中间点 并把D中的每一条弧的赋权数称为弧的容量 D就称为网络 7 2最小生成树问题 一 树的概念树一个无圈的连通图称为树 树的性质 1在图中任意两点之间必有一条而且只有一条通路 2在图中划去一条边 则图不连通 3在图中不相邻的两个顶点之间加一条边 可得一个且仅得一个圈 4图中边数有Ne V 1 V为顶点数 生成树 若T是无向图G的生成子图 且T又是树 称T为G的生成树 8 2最小生成树问题 最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树 并使得这个生成树的所有边的权数之和为最小 9 2最小生成树问题 二 求解最小生成树的破圈算法算法步骤 1 在给定的赋权的连通图上任找一个圈 2 在所找的圈中去掉一个权数最大的边 如果有两条或两条以上的边都是权数最大的边 则任意去掉其中一条 3 如果所余下的图已不包含圈 则计算结束 所余下的图即为最小生成树 否则返回第2步 10 2最小生成树问题 例 某大学准备对其所属的7个学院办公室计算机联网 这个网络的可能联通的途径如下图 图中v1 v7表示7个学院办公室 请设计一个网络能联通7个学院办公室 并使总的线路长度为最短 单位 百米 解 此问题实际上是求图的最小生成树 也即按照图的 f 设计 可使此网络的总的线路长度为最短 为19百米 管理运筹学软件 有专门的子程序可以解决最小生成树问题 11 2最小生成树问题 例用破圈算法求图 a 中的一个最小生成树 12 作业 求下列各图的最小树 13 3最短路问题 最短路问题 对一个赋权的有向图D 或无向图 中指定的两个点Vs和Vt找到一条从Vs到Vt的路 使得这条路上所有弧 或边 的权数的总和最小 这条路被称之为从Vs到Vt的最短路 这条路上所有弧 或边 的权数的总和被称为从Vs到Vt的最短距离 14 3最短路问题 例1电信公司准备在甲 乙两地沿路架设一条光缆线 问如何架设使其光缆线路最短 下图给出了甲乙两地间的交通图 权数表示两地间公路的长度 单位 公里 15 3最短路问题 16 3最短路问题 2 算法 从起点标号 标号有两个内容 aj bj aj表示从起点到该点的最小距离 bj表示此最小距离链的紧前一个顶点的足标 起点的标号为 0 0 从已标号的顶点出发 找出与这些已标号的顶点紧邻的所有顶点的距离 并选最小值进行标号 直到所有顶点都标号完为止 17 3最短路问题 例2 求V 至各点的最短路 18 3最短路问题 例3 上例中 求V3至各点的最短路 例4 求V 至各点的最短路 6 19 3最短路问题 例5 20 3最短路问题 二 逐次逼近法 适用某些Cij 0 解决指定点到任意点的最短路或两指定点间最短路 算法 1 先赋予起点标号 0 0 及与起点邻近点的标号 Cij 1 其它标号为 1 2 检查各顶点标号是否得到最小值 否则 逐个调整 21 例6 求V 至各点的最短路 3最短路问题 22 3最短路问题 例7 求V 至各点的最短路 23 3最短路问题 循环 路长单调下降而趋向 无结果 回路上的权值之和为正数或零 可求得结果 回路上的权值之和为负数时 此法失效 24 V7 V1 30 30 25 20 V2 15 V6 15 18 V4 3最短路问题 例8已知某地区的交通网络如下图所示 其中点代表居民小区 边表示公路 问区中心医院应建在哪个小区 可使离医院最远的小区居民就诊时所走的路程最近 V5 60 20 V3 25 3最短路问题 26 4最大流问题 在交通运输 物资供应中 经常会遇到人流 车流 信息流 物流 现金流 称 网络流理论 二十世纪中叶以后 Ford和Fulkerson建立了网络流理论 最大流问题 给一个带收发点的网络 其每条弧的赋权称之为容量 在不超过每条弧的容量的前提下 求出从发点到收点的最大流量 一 最大流的数学模型 27 4最大流问题 例1某石油公司拥有一个管道网络 使用这个网络可以把石油从采地运送到一些销售点 这个网络的一部分如下图所示 由于管道的直径的变化 它的各段管道 vi vj 的流量cij 容量 也是不一样的 cij的单位为万加仑 小时 如果使用这个网络系统从采地v1向销地v7运送石油 问每小时能运送多少加仑石油 v5 28 4最大流问题 我们可以为此例题建立线性规划数学模型 设弧 vi vj 上流量为fij 网络上的总的流量为F 则有 29 4最大流问题 在这个线性规划模型中 其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件 发点的流出量必须等于收点的总流入量 其余的点称之为中间点 它的总流入量必须等于总流出量 其后面几个约束条件表示对每一条弧 vi vj 的流量fij要满足流量的可行条件 应小于等于弧 vi vj 的容量cij 并大于等于零 即0 fij cij 我们把满足守恒条件及流量可行条件的一组网络流 fij 称之为可行流 即线性规划的可行解 可行流中一组流量最大 也即发出点总流出量最大 的称之为最大流 即线性规划的最优解 30 4最大流问题 Ford Fulkerson算法二 概念及原理1 可行流 满足约束条件式o fij cij的fij称为一组可行流 可行流总是存在的 如取所有fij 0 31 4最大流问题 2 增值链 设fij是一组可行流 如果存在一条从V1到Vn的初等链 在这条链上所有的前向弧fij0 则称这条链是一条关于可行流fij的可扩充链 在所有前向弧上计算在所有后向弧上计算调整量 32 4最大流问题 新的可行流在V1 Vn间增加了一个流量 直至找不到可扩充链为止 就得到了最大流 3 原理 在发点和起点之间是否存在增值链 33 4最大流问题 二 计算 标号法 1 给出第1个可行流令2 寻找增值链 若无 则取得最大