图与网络分析到最短路问题

图与网络分析 图的基本概念与模型树图和图的最小部分树最短路问题网络最大流问题最小费用最大流问题 图与网络分析 图的基本概念与模型树图和图的最小部分树最短路问题网络最大流问题最小费用最大流问题 图论是应用非常广泛的运筹学分支 它已经广泛地应用于物理学控制论 信息论 工程技术 交通运输 经济管理 电子计算机等各项领域 对于科学研究 市场和社会生活中的许多问题 可以同图论的理论和方法来加以解决 例如 各种通信线路的架设 输油管道的铺设 铁路或者公路交通网络的合理布局等问题 都可以应用图论的方法 简便 快捷地加以解决 引言 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文 解决了著名的哥尼斯堡七座桥问题 即一个漫步者如何能够走过这七座桥 并且每座桥只能走过一次 最终回到原出发地 如图1所示 引例1 欧拉将这个问题抽象成一笔画问题 即能否从某一点开始不重复地一笔画出这个图形 最终回到原点 欧拉在他的论文中证明了这是不可能的 因为这个图形中每一个顶点都与奇数条边相连接 不可能将它一笔画出 这就是古典图论中的第一个著名问题 在实际的生产和生活中 人们为了反映事物之间的关系 常常在纸上用点和线来画出各式各样的示意图 引例2 左图是我国北京 上海 重庆等十四个城市之间的铁路交通图 这里用点表示城市 用点与点之间的线表示城市之间的铁路线 诸如此类还有城市中的市政管道图 民用航空线图等等 有六支球队进行足球比赛 我们分别用点v1 v6表示这六支球队 它们之间的比赛情况 也可以用图反映出来 已知v1队战胜v2队 v2队战胜v3队 v3队战胜v5队 如此等等 这个胜负情况 可以用下图所示的有向图反映出来 引例3 图的基本概念与模型 点 研究对象 车站 国家 球队 点间连线 对象之间的特定关系 陆地间有桥 铁路线 两球队比赛及结果 对称关系 桥 道路 边界 用不带箭头的连线表示 称为边 非对称关系 甲队胜乙队 用带箭头的连线表示 称为弧 图 点及边 或弧 组成 注意 一般情况下 图中的相对位置如何 点与点之间线的长短曲直 对于反映研究对象之间的关系 显的并不重要 因此 图论中的图与几何图 工程图等本质上不同 对称关系 非对称关系 无向图 图由点和边所构成的 记作G V E V是点的集合 E是边的集合 连接点vi vj V的边记作eij vi vj 或者 vj vi 有向图 图是由点和弧所构成的 记作D V A V是点的集合 A是弧的集合 一条方向从vi指向vj的弧 记作 vi vj 图的相关概念 网络图 给图中的点和边赋予具体的含义和权数 如距离 费用 容量等 记作N 图的相关概念 若边eij vi vj E 称vi vj是eij的端点 也称vi vj是相邻的 称eij是点vi 及点vj 的关联边 若两条边有一个公共的端点 则称这两条边相邻 点与边关联 点与点相邻 边与边相邻 若某条边两个端点相同 称这条边为环 若两点之间有多于一条的边 称这些边为多重边 无环 无多重边的图称为简单图 无环 但允许有多重边的图称为多重图 注 无特别声明我们今后讨论的图都是简单图 图的相关概念 图G中以点v为端点的边的数目 称为v在G中的次 度 记为d v d v1 2d v2 3d v3 4d v4 1 次为1的点为悬挂点 悬挂点的关联边称为悬挂边 次为零的点称为孤立点 次为奇数的点称为奇点 否则称为偶点 图的相关概念 给定图G V E 若图G V E 其中V V E E 则称G 是G的子图 给定图G V E 若图G V E 其中E E 则称G 是G的一个支撑子图 部分图 点全部保留 部分图 子图与部分图 支撑子图 图的连通性 链 设图G V E 中有一个点 边交替序列 v1 e1 v2 vn 1 en 1 vn 若ei vi vi 1 即这 n 1 条边把n个顶点串连起来 我们称这个交替序列为图G中的一条链 而称点v1 vn为该链的两个端点 对于简单图链也可以仅用点的序列来表示 如果一条链的两个端点是同一个点 则称它为闭链或圈 如果一条链的各边均不相同 则称此链为简单链 更若一条链的各点 各边均不相同 则称该链为初等链 图的连通性 最短链 网络中链上权值的和称为链的长度 以点v1 vn为端点的诸链中长度最短的链称为这两点的最短链 连通图 如果图G V E 中的任意两点都是其某一条链的两个端点 则称图G是连通图 否则 称图G是不连通的 为不连通图 有两个连通分图组成 图的矩阵表示 图的矩阵表示主要方法有 权矩阵 邻接矩阵 权矩阵网络图N V E 边 vi vj 的权为wij 构造矩阵 称矩阵A为网络N的权矩阵 其权矩阵为 注 当G为无向图时 权矩阵为对称矩阵 图G V E p n 构造矩阵 称矩阵A为G的邻接矩阵 邻接矩阵 vi与vj不相邻 图的矩阵表示 其邻接矩阵为 注 当G为无向图时 邻接矩阵为对称矩阵 思考 有甲 乙 丙 丁 戊 己六名运动员报名参加A B C D E F六个项目的比赛 下表中打的是个运动员报名参加比赛的项目 问六个项目的比赛顺序应如何安排 做到每名运动员都不连续地参加两项比赛 A B C D E F 分析 点表示项目 边表示两个项目有同一名运动员参加 目的 在图中找出点序列 使得依次排列的两个点不相邻 就找到了每名运动员不连续参加两项比赛的安排方案 A C B F E D 不唯一 第八章图与网络分析 图的基本概念与模型树图和图的最小部分树最短路问题网络最大流问题最小费用最大流问题 第八章图与网络分析 图的基本概念与模型树图和图的最小部分树最短路问题网络最大流问题最小费用最大流问题 7个村庄要在他们之间架设电话线 要求任何两个村庄都可以互相通电话 允许中转 并且电话线根数最少 引例 村庄1 村庄4 村庄3 村庄6 村庄2 村庄5 村庄7 分析 用七个点代表村庄 如果在某两个村庄之间架设电话线 则相应的在两点之间连一条边 这样电话线网就可以用一个图来表示 并且满足如下要求 连通图图中有圈的话 从圈中任去掉一条边 余下的图仍连通 为什么 树 村庄1 村庄4 村庄3 村庄6 村庄2 村庄5 村庄7 如果G V E 是一个无圈的连通图 则称G为树 树中必存在次为1的点 悬挂点 树中任两点必有一条链且仅有一条链 在树的两个不相邻的点之间添加一条边 就得到一个圈 反之 去掉树的任一条边 树就成为不连通图 n个顶点的树有 n 1 条边 树是无圈连通图中边数最多的 也是最脆弱的连通图 图的部分树 支撑树 如果图G V E 的部分图G V E 是树 则称G 是G的部分树 或支撑树 村庄1 村庄4 村庄3 村庄6 村庄2 村庄5 村庄7 部分树上各树枝上权值的和称为它的长度 其中长度最短的部分树 称其为该图的最小部分树 最小支撑树 点保留边可去仍是树不唯一 思考 如何铺设电话线 使得电话线长度最少 最小部分树的求法 定理 图中任一个点i 若j是与相邻点中距离最近的 则边 i j 一定必含在该图的最小部分树内 推论 把图的所有点分成和两个集合 则两集合之间连线的最短边一定包含在最小部分树内 避圈法 破圈法 2 2 7 5 4 1 4 3 5 1 7 5 求解最小生成树的避圈算法 S A B C D E S T 2 2 1 3 1 5 求解最小生成树的破圈算法 算法的步骤 1 在给定的赋权的连通图上任找一个圈 2 在所找的圈中去掉一个权数最大的边 如果有两条或两条以上的边都是权数最大的边 则任意去掉其中一条 3 如果所余下的图已不包含圈 则计算结束 所余下的图即为最小生成树 否则返回第1步 第八章图与网络分析 图的基本概念与模型树图和图的最小部分树最短路问题网络最大流问题最小费用最大流问题 第八章图与网络分析 图的基本概念与模型树图和图的最小部分树最短路问题网络最大流问题最小费用最大流问题 什么是最短路问题 固定起点的最短路Dijkstra 狄克斯拉 荷兰 算法 标号法逐次逼近算法 Ford 美国 算法 修正标号法每对顶点之间的最短路路矩阵算法 Floyd 佛洛伊德 算法 最短路问题 最短路问题提出 在现实生活中 除公路运输网络 电讯网络等网络图以外 还有输油管线这样的图 在输油管线图中 为反映油的输送情况 两点间不仅有连线 线上往往还标有箭头 以表示油的流动方向 又如 指挥系统图 控制系统图等图中都标有指向 从这样的一类图中就可以概括为有向图的概念 有向图 由点集和V中元素的有序对的一个集合所组成的二元组称为有向图 记为D V A 其中V中的元素vi叫做顶点 A中元素aij叫做以vi为始点 尾 vj为终点 首 的弧 aij与aji作为具有不同指向的弧是不同的 有向网络与混合图 如果在图D V A 中 给每一弧赋予权值 如将弧aij vi vj 有权值wij 记为w aij wij则赋权有向图D V A 称为有向网络 在不至于混淆时 也简称网络 混合图如果一个图中既有边 也有弧 那么称这种图为混合图 它往往出现在既有单行线 又有双行线的交通图中 最短路问题引例 下图为单行线交通网 每弧旁的数字表示通过这条线所需的费用 现在某人要从v1出发 通过这个交通网到v8去 求使总费用最小的旅行路线 从v1到v8 P1 v1 v2 v5 v8 费用6 1 6 13P2 v1 v3 v4 v6 v7 v8 费用3 2 10 2 4 21P3 最短路问题中 不考虑有向环 并行弧 几个概念 路 设p是D中一个首尾相连的弧的集合 如果vs是它的第一条弧的始点 vt是它的最后一条弧的终点 则称它是以点vs为始点 以点vt为终点的一条路 路长 路p中所有弧的权值的和称为路p的长 记为 设图D V A 是一有向网络 设P是以点vs为始点 以点vt为终点的所有路的集合 如果 且 则称p0是以点vs为始点 以点vt为终点的最短路 而称其路长为点vi到点vj的距离 记为 几个概念 最短路及一点到另一点的距离 最短路问题是重要的最优化问题之一 可以直接应用于解决生产实际的许多问题 管道铺设 线路安排 厂区布局等 而且经常被作为一个基本工具来解决其他的优化问题 最短路问题求解方法 Dijkstra算法逐步逼近算法路矩阵算法 最短路问题求解方法 Dijkstra算法逐步逼近算法路矩阵算法 求解最短路问题的Dijkstra算法 条件 当所有wij 0时 用来求给定点vs到任一个点vj最短路的公认的最好方法 事实 如果P是D中从vs到vj的最短路 vi是P中的一基解个点 那么 从vs沿P到vi的路是从vs到vi的最基解短路 Dijkstra算法是Dijkstra在1959年提出的 可用于求解指定两点间的最短路问题 或从指定点到其余各点的最短路问题 由于其以标号为主要特征 又称为标号法 v5 最短路的子路是最短路 Dijkstra算法基本思想 从始点vs出发 逐步顺序地向外探寻 每向外延伸一步都要求是最短的 执行过程中 与每个点对应 记录下一个数 称为这个点的标号 1 标号P 固定标号或永久性标号 从始点vs到该标号点vj的最短路权P vj 2 标号T 临时性标号 从始点vs到该标号点vj的最短路权上界T vj j P vj j T vj 该方法的每一步就是去修改T标号 并且把某一个具T标号的点改变为具有P标号的点 从而使D中具P标号的顶点数多一个 至多经过n 1步 就可以求出始点vs到各点的最短路 前点标号 j 表示始点vs到vj的最短路上vj的前一点 Dijkstra算法步骤 第二步 考虑满足条件 的所有点 vi具有P标号 vj具有T标号 修改vj的T标号为 并将结果仍记为T vj 第一步 始点标上固定标号 其余各点标临时性标号T vj j 1 第三步 若网络图中已无T标号点 停止计算 否则 令 s为T标号点集 然后将的T标号改成P标号 转入第二步 v1 6 图上标号法 0 0 M M v1 3 M M M v1 1 v1 1 永久标号 永久标号 临时标号 v1出发到v8去 使总费用最小的旅行路线 v1 6 图上标号法 0 0 M M v1 3 M M M 0 0 v1 1 v4 11 v1 3 永久标号 临时标号 v1出发到v8去 使总费用最小的旅行路线 0 0 M v1 1 M M M 1 3 图上标号法 v4 11 v1 3 v1 6 v3 5 v3 5 永久标号 临时标号 v1出发到v8去 使总费用最小的旅行路线 0 0 M v4 11 v1 1 M M M v1 3 图上标号法 v3 5 v2 6 v2 6 永久标号 临时标号 v1出发到v8去 使总费用最小的旅行路线 0 0 M v4 11 v1 1 M M v1 3 v5 12 v5 9 v5 9 图上标号法 v3 5 v2 6 永久标号 临时标号 v5 10 v1出发到v8去 使总费用最小的旅行路线 0 0 v5 10 v1 1 M v5 12 v1 3 v5 9 v5 12 v3 5 v2 6 图上标号法 永久标号 临时标号 v5 10 v1出发到v8去 使总费用最小的旅行路线 0 0 v5 10 v1 1 M v1 3 v5 12 v3 5 v2 6 图上标号法 v5 9 永久标号 临时标号 标号结束反向追踪 v1出发到v8去 使总费用最小的旅行路线 Dijkstra算法步骤 第二步 考虑满足条件 的所有点 vi具有P标号 vj具有T标号 修改vj的T标号为 并将结果仍记为T vj 第一步 始点标上固定标号 其余各点标临时性标号T vj j 1 第三步 若网络图中已无T标号点 停止计算 否则 令 s为T标号点集 然后将的T标号改成P标号 转入第二步 例求如下交通网络中v1到各点间最短路路长 Dijkstra算法 标号法 算例 混合图 无向网络 负权弧时 无向网络中 最短路 最短链 多个点对之间最短路 Dijkstra算法失效 Dijkstra算法注意的问题 逐步逼近算法 路矩阵算法 5 7 2 7 4 6 1 2 6 3 2 0 2 6 5 7 7 10 v3 v1 v2 v4 v5 v6 v7 练习 求如下无向网络中v1到v7的最短链 Dijkstra算法求最短链 最短路问题求解方法 Dijkstra算法逐步逼近算法路矩阵算法 最短路问题求解方法 Dijkstra算法逐步逼近算法路矩阵算法 逐次逼近算法思想 该公式表明 P 1 1j中的第j个分量等于P 0 1j的分量与基本表 权矩阵 中的第j列相应元素路长的最小值 它相当于在v1与vj之间插入一个转接点 v1 v2 vn中的任一个 含点v1与vj 后所有可能路中的最短路的路长 每迭代一次 就相当与增加一个转接点 而P k 1j中的每一个分量则随着k的增加而呈不增的趋势 用于计算带有负权弧指定点v1到其余各点的最短路 逐次逼近算法基本步骤 例计算从点v1到所有其它顶点的最短路 解 初始条件为 以后按照公式进行迭代 直到得到 迭代停止 40 0 1 602 40 33 307 5 204 20 0 利用下标追踪路径 空格为无穷大 40 0 1 602 40 33 307 5 204 20 0 利用下标追踪路径 空格为无穷大 最短路问题求解方法 Dijkstra算法逐步逼近算法路矩阵算法 最短路问题求解方法 Dijkstra算法逐步逼近算法路矩阵算法 某些问题需要求网络上任意两点间的最短路 当然 它也可以用标号算法依次改变始点的办法来计算 但是比较麻烦 这里介绍Floyd在1962年提出的路矩阵法 它可直接求出网络中任意两点间的最短路 Floyd算法 路矩阵法 思想 考虑D中任意两点vi vj 如将D中vi vj以外的点都删掉 得只剩vi vj的一个子网络D0 记 wij为弧 vi vj 的权 在D0中加入v1及D中与vi vj v1相关联的弧 得D1 D1中vi到vj的最短路记为 则一定有 Floyd算法 路矩阵法 思想 再在D1中加入v2及D中与vi vj v1 v2相关联的弧 得D2 D2中vi到vj的最短路长记为 则有 Floyd算法 路矩阵法 思想 Floyd算法 路矩阵法 步骤 设有有向网络D V A 其权矩阵为A aij n n 如下构造路矩阵序列 则n阶路矩阵D n 中的元素d n ij就是vi到vj的最短路的路长 令权矩阵A为初始路矩阵D 0 即令D 0 A 2 依次计算K阶路矩阵D K d k ij n n k 1 2 n 这里 路矩阵序列的含义 K阶路矩阵D K 其中的元素表示相应两点间可能以点v1 v2 vk为转接点的所有路中路长最短的路的路长 D 0 其中的任一元素表示相应两点间无转接点时最短路路长 一阶路矩阵D 1 其中的元素表示相应两点间可能以点v1为转接点的所有路中路长最短的路的路长 为使计算程序化 转接点按顶点下标的顺序依次加入 n阶路矩阵D n 其中的元素d n ij就是vi到vj的可能以点v1 v2 vn为转接点的所有路中路长最短的路的路长 既是vi到vj的最短路的路长 例求如下交通网络中各对点间最短路路长 该图的权矩阵为 Floyd算法 路矩阵法 算例 例求如下交通网络中各对点间最短路路长 Floyd算法 路矩阵法 算例 利用公式 发现第一行 第一列元素不变 利用公式 发现第二行 第二列元素不变 利用公式 发现第三行 第三列元素不变 利用公式 发现第四行 第四列元素不变 D 5 中的元素给出相应两点间的最短路