西大数学建模赛前培训课件-图.ppt

图 GraphTheoryandNetworkAnalysis 图的基本概念与模型树最短路问题网络的最大流 近代图论的历史可追溯到18世纪的七桥问题 穿过K nigsberg城的七座桥 要求每座桥通过一次且仅通过一次 这就是著名的 哥尼斯堡7桥 难题 Euler1736年证明了不可能存在这样的路线 第一节图的基本概念与模型 K nigsberg桥对应的图 例1 有甲 乙 丙 丁 戊五个球队 它们之间比赛的情况也可以用图表示出来 一 图基本概念 优化问题中研究的图具有下列特征 强调点与点之间的关联关系 不讲究图的比例大小与形状 每条边上赋有一个权 建立网络模型 求最大值或最小值 下图可以提出很多极值问题 图的矩阵描述 邻接矩阵 关联矩阵 权矩阵等 1 邻接矩阵对于图G V E V n E m 有n n阶方矩阵A aij n n 其中 图的基本概念与模型 例6 2下图所表示的图可以构造邻接矩阵A如下 对于赋权图G V E 其中边有权 构造矩阵B bij n n其中 2 权矩阵 例6 4下图所表示的图可以构造权矩阵B如下 第二节树 树是图论中结构最简单但又十分重要的图 在自然和社会领域应用极为广泛 例6 2乒乓求单打比赛抽签后 可用图来表示相遇情况 如下图所示 运动员 例6 3某企业的组织机构图也可用树图表示 树 无圈的连通图即为树 性质1 任何树中必存在次为1的点 性质2 n个顶点的树必有n 1条边 性质3 树中任意两个顶点之间 恰有且仅有一条链 性质4 树连通 但去掉任一条边 必变为不连通 性质5 树无回圈 但不相邻的两个点之间加一条边 恰得到一个圈 图的最小部分树 支撑树 如果G2是G1的部分图 又是树图 则称G2是G1的部分树 或支撑树 树图的各条边称为树枝 一般图G1含有多个部分树 其中树枝总长最小的部分树 称为该图的最小部分树 或最小支撑树 G1 G2 例如 图4 18 a 是一个有四个顶点 n 4 的连通图 它共有nn 2 42 16个生成树 V1 V2 V3 V4 图4 18 a 赋权图中求最小树的方法 破圈法和避圈法 破圈法 任取一圈 去掉圈中最长边 直到无圈 v1 v2 v3 v4 v5 v6 4 3 5 2 1 边数 n 1 5 得到最小树 MinC T 15 避圈法 去掉G中所有边 得到n个孤立点 然后加边 加边的原则为 从最短边开始添加 加边的过程中不能形成圈 直到点点连通 即 n 1条边 v1 v2 v3 v4 v5 v6 4 3 5 2 1 MinC T 15 某一点到另一点的最短路的狄克斯屈拉 Dijkstra 法所有点对间的最短路 第三节最短路问题 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 有些问题 如选址 管道铺设时的选线 设备更新 投资 某些整数规划和动态规划的问题 也可以归结为求最短路的问题 因此这类问题在生产实际中得到广泛应用 里特城 Littletown 是一个乡村的小镇 它的消防队要为包括许多农场社区在内大片的地区提供服务 在这个地区里有很多道路 从消防站到任何一个社区都有很多条路线 因为时间是一个到达火灾发生点的主要因素 所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路 例子 里特城的消防队问题 最短路 O A B E F T19英里 一 求最短路的Dijkstra算法 1 算法的基本思想 2 有向图的狄克斯屈拉 Dijkstra 标号算法步骤 点标号 p vj 起点vs到点vj的最短路长 边标号 a i j p i lij 步骤 1 令起点的标号 p vs 0 先求有向图的最短路 设网络图的起点是vs 终点是vt 以vi为起点vj为终点的弧记为 i j 距离为lij 2 找出所有vi已标号vj未标号的弧集合Ai i j 如果这样的弧不存在或vt已标号则计算结束 3 计算集合Ai中弧的标号 a i j p i lij 4 选一个点标号返回到第 2 步 6 10 12 3 2 14 6 7 5 8 11 16 5 图5 1 9 例5 1 图5 1中的权cij表示vi到vj的距离 费用 时间 从v1修一条公路或架设一条高压线到v7 如何选择一条路线使距离最短 建立该问题的网络数学模型 解 设xij为选择弧 i j 的状态变量 选择弧 i j 时xij 1 不选择弧 i j 时xij 0 得到最短路问题的网络模型 6 10 12 3 2 14 6 7 5 8 11 16 5 图5 1 9 6 10 12 9 20 p 9 v2 18 P 6 V1 16 P 12 v1 17 P 16 v3 24 32 P 18 v3 29 P 29 v5 例5 1 用Dijkstra算法求图5 1所示v1到v7的最短路及最短路长 v1到v7的最短路为 p17 v1 v2 v3 v5 v7 最短路长为L17 29 14 P 0 V1 从上例知 只要某点已标号 说明已找到起点vs到该点的最短路线及最短距离 因此可以将每个点标号 求出vs到任意点的最短路线 如果某个点vj不能标号 说明vs不可达vj 二 所有点对间的最短路Floyd算法 1 写出图的权矩阵 步骤 输入权矩阵 对n个顶点的图G 该方法迭代n步结束 第k次迭代的矩阵Dk的元素dij k 按下式选取dij k min dij k 1 dik k 1 dkj k 1 其中 i j 1 2 3 n 但当i k或j k时 dij k dij k 1 中的元素就是 到 的最短路长 第四节网络最大流 如何制定一个运输计划使生产地到销售地的产品输送量最大 这就是一个网络最大流问题 一 基本概念 1 容量网络 对网络上的每条弧 vi vj 都给出一个最大的通过能力 称为该弧的容量 简记为cij 容量网络中通常规定一个发点 也称源点 记为s 和一个收点 也称汇点 记为t 网络中其他点称为中间点 s t 4 8 4 4 1 2 2 6 7 9 2 网络的最大流是指网络中从发点到收点之间允许通过的最大流量 3 流与可行流流是指加在