运筹学第八章图与网络分析

第八章图与网络分析 主要内容 8 1图与网络的基本知识 8 2最短路问题 8 3最大流问题 8 4最小费用流问题 8 1图与网络基本知识 一 引言1 产生哥尼斯堡七桥难题 例8 1 哥尼斯堡七桥问题 哥尼斯堡 现名加里宁格勒 是欧洲一个城市 Pregei河把该城分成两部分 河中有两个小岛 十八世纪时 河两边及小岛之间共有七座桥 当时人们提出这样的问题 有没有办法从某处 如A 出发 经过各桥一次且仅一次最后回到原地呢 数学家Euler在1736年解决 8 1图与网络基本知识 二 图与网络的基本概念 8 1图与网络基本知识 图论是专门研究图的理论的一门数学分支 主要研究点和线之间的几何关系 图论是离散数学的范畴 8 1图与网络基本知识 一 图的有关概念 表示为 G V E V 点集合E 边集合 简称图 由点和边组成 无向图 带箭头的联线 表示不对称关系 弧 不带箭头的联线 表示对称关系 边 反映对象之间关系的一种工具 图 表示两个对象之间的某种特定关系 连线 表示研究对象 点 8 1图与网络基本知识 二 无向图的有关概念 无环 允许有多重边的图 多重图 无环 无多重边的图 简单图 两点之间多于一条边 多重边 若u v e是环 环 e是点u v的关联边 关联边 e u v E 则u v是e的端点 称u v相邻 端点 8 1图与网络基本知识 二 无向图的有关概念 次为偶数的点 偶点 次为奇数的点 奇点 次为0的点 孤立点 悬挂点的关联边 悬挂边 次为1的点 悬挂点 例 如图示d v1 4 d v4 4 以点v为端点的边数称为v的次 表示为 d v 次 8 1图与网络基本知识 二 无向图的有关概念 定理8 2 在任意一个图中 奇顶点的个数必为偶数 定理8 1 在一个图中 所有顶点次的和等于边的两倍 圈中边均不相同 简单圈 链中边均不相同 简单链 圈中无重复的点和边 初等圈 链中无重复的点和边 初等链 如一条链中起点和终点重合 圈 点边交错序列 链 8 1图与网络基本知识 二 无向图的有关概念 图G去掉点v及v的关联边的图 G v 对G V E 若G V E 使V V E 是E的子集 则G 是G的一个支撑子图 支撑子图 对不连通图 每一连通的部分称为一个连通分图 连通分图 任意两点之间至少有一条链 连通图 例8 2 有7个人围桌而坐 如果要求每次相邻的人都与以前完全不同 试问不同的就座方案共有多少种 8 1图与网络基本知识 提示 用顶点表示人 用边表示两者相邻 共有3种方案 8 1图与网络基本知识 三 有向图的有关概念 有多重弧 多重有向图 无自环 无多重弧 简单有向图 圈中无重复的点和弧 初等圈 回路 链中无重复的点和弧 初等链 道路 如一条链中起点和终点重合 圈 回路 点弧交错序列 链 道路 对弧a u v u为a的始点 v为a的终点 始点和终点 由点和弧组成 表示为 D V A V 点集合A 弧集合 有向图 树 一个无圈的无向连通图称为树 如果一个无圈的图中每一个分支都是树 则称图为森林 8 1图与网络基本知识 四 树的概念 树的性质 在图中任意两点之间必有一条而且只有一条通路 2 在图中划去一条边 则图不连通 3 在图中不相邻的两个顶点之间加一条边 可得一个且仅得一个圈 4 图中边数为 p 1 p为顶点数 例8 4 一个班级的学生共计选修A B C D E F六门课程 其中一部分人同时选修D C A 一部分人同时选修B C F 一部分人同时选修B E 还有一部分人同时选修A B 期终考试要求每天考一门课 六天内考完 为了减轻学生负担 要求每人都不会连续参加考试 试设计一个考试日程表 8 1图与网络基本知识 解 以每门课程为一个顶点 共同被选修的课程之间用边相连 得图 按题意 相邻顶点对应课程不能连续考试 不相邻顶点对应课程允许连续考试 因此 作图的补图 问题是在图中寻找一条哈密顿道路 如C E A F D B 就是一个符合要求的考试课程表 8 1图与网络基本知识 8 1图与网络基本知识 四 树的概念 图的支撑树 生成树 1 定义 设图T V E 是图G V E 的支撑子图 如果T是一个树 则称T是G的一个支撑树 最优树 最小生成树 最小支撑树 在赋权图G中 一棵生成树所有树枝上权的总和 称为生成树的权 具有最小权的生成树 称为最优树 或最小树 2 定理5 图G V E 有支撑树的充分必要条件是G是连通的 四 树的概念求最小生成树的方法有破圈法和避圈法 8 1图与网络基本知识 五 欧拉回路与中国邮递员问题 8 1图与网络基本知识 一笔划问题欧拉链 道路 图中存在一条链 过每边一次且仅一次 欧拉圈 回路 图中存在一简单圈 过每边一次且仅一次 欧拉图 具有欧拉圈的图 一笔划问题 8 1图与网络基本知识 定理 连通多重图G是欧拉图 当且仅当G中无奇点 推论 连通多重图G有欧拉链 当且仅当G恰有两个奇点 五 欧拉回路与中国邮递员问题 例8 3 哈密尔顿 Hamilton 回路是英国数学家哈密尔顿1857年提出 给出一个正12面体图形 共有20个顶点表示20个城市 要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次 最后回到原处的周游世界线路 并不要求经过每条边 8 1图与网络基本知识 8 1图与网络基本知识 中国邮递员问题 五 欧拉回路与中国邮递员问题 一个邮递员 负责某一地区的信件投递 他每天要从邮局出发 走遍该地区所有的街道再返回邮局 问应如何安排送信的路线可以使所走的总路程最短 8 1图与网络基本知识 中国邮递员问题奇偶点作业法 若图中无奇点 问题已解决 五 欧拉回路与中国邮递员问题 否则 1 第一可行方案的确定 奇点配对 找奇点间的一条链 3 最优性判定 满足a 和b 两条 8 1图与网络基本知识 中国邮递员问题 2 调整可行方案 使重复边总长度下降 a 最优方案中 每一边上最多有一条重复边 b 最优方案中 每个圈上重复边的总权不大于圈总权的一半 8 2最短路问题 三种算法求解三类最短路问题 1 Dijkstra算法 求无负权网络最短路问题 2 逐步逼近算法 求带负权网络最短路问题 3 Floyd算法 求网络上任意两点间的最短路问题 8 2最短路问题 一 Dijkstra算法 求无负权网络最短路问题 采用标号法 P标号和T标号 PermanentandTentativeLabel P标号 已确定出最短路的节点 永久性标号 T标号 未确定出最短路的节点 表示其距离的上限 试探性标号 算法的每一步都把某一点的T标号改为P标号直至改完为止 v4 8 2最短路问题 一 Dijkstra算法 8 2最短路问题 一 Dijkstra算法 解 1 P V1 0T Vi i 2 3 8 2 考察V1V2和V1V3两边 T V2 min T V2 P V1 l12 min 0 4 4 T V3 min T V3 P V1 l13 min 0 6 6 比较所有T标号 T V2 最小 有P V2 4 并记录路径 V1 V2 3 考察V2V4和V2V5两边 T V4 min T V4 P V2 l24 min 4 5 9 T V5 min T V5 P V2 l25 min 4 4 8 比较所有T标号 T V3 最小 有P V3 6 并记录路径 V1 V3 8 2最短路问题 一 Dijkstra算法 4 考察V3V4和V3V5两边 T V4 min T V4 P V3 l34 min 9 6 4 9 T V5 min T V5 P V3 l35 min 8 6 7 8 比较所有T标号 T V5 最小 有P V5 8 并记录路径 V2 V5 3 考察V5V6和V5V7两边 T V6 min T V6 P V5 l56 min 8 5 13 T V7 min T V7 P V5 l57 min 8 6 14 比较所有T标号 T V4 最小 有P V4 9 并记录路径 V2 V4 依此类推 一直计算到 8 8 考察V8点 只有一个T标号 T V8 15 令P V8 15 记录路径 V7 V8 计算结束 反推得最V1至V8的最短路为V1 V2 V5 V7 V8 路长15 8 2最短路问题 一 Dijkstra算法 求无负权网络最短路问题 计算步骤 1 给Vs以P标号 P Vs 0 其余各点给T标号 T Vi 2 若Vi点为刚得到P标号的点 考虑点Vj Vi Vj 属于E 且Vj为T标号 则修改T Vj T Vj min T Vj P Vi lij 3 比较所有T标号的点 把最小者改为P标号 即 P Vi min T Vi 当存在两个以上最小者时 可同时改为P标号 二 逐次逼近法基本思想 令P1j表示从v1到vj的最短路长 P1i为v1到vi的最短路长 则必有下列方程 P1j min P1i lij 8 2最短路问题 i 8 2最短路问题 例 求图示中V1点到各点的最短路 8 2最短路问题 解 初始条件为 P11 1 0 P12 1 2 P13 1 5 P14 1 3 P15 1 P16 1 P17 1 P18 1 第一轮迭代 P11 2 min P11 1 l11 P12 1 l21 P13 1 l31 P14 1 l41 P15 1 l51 P16 1 l61 P17 1 l71 P18 1 l81 0 求解 见Excel表格求解 P12 2 min P11 1 l12 P12 1 l22 P13 1 l32 P14 1 l42 P15 1 l52 P16 1 l62 P17 1 l72 P18 1 l82 2 依此类推 8 2最短路问题 10 10 10 15 M M 0 1 M 3 M M M M V8 9 9 14 M M M M 0 2 M 7 M M M V7 6 6 6 6 11 M 4 M 0 3 M M M M V6 3 3 3 6 6 M M M M 0 M M M M V5 3 3 3 3 3 3 M M M M 0 4 M M V4 0 0 0 0 0 5 M M 6 M M 0 M M V3 2 2 2 2 2 2 M M M 4 M 2 0 M V2 0 0 0 0 0 0 M M M M 3 5 2 0 V1 V8 V7 V6 V5 V4 V3 V2 V1 P 6 1j P 5 1j P 4 1j P 3 1j P 2 1j P 1 1j lij ji 8 2最短路问题 三 Floyd算法 算法功能 求网络上任意两点间的最短路 算法步骤 1 令网络的权矩阵为D dij n n lij为Vi到Vj的距离 其中 2 输入权矩阵为D 0 D 3 计算D k dij k n n k 1 2 3 n 其中 三 Floyd算法 8 2最短路问题 例13 P267 求解 见手工和Excel 8 3最大流问题 一 基本概念和基本定理1 网络与流定义 对有向图G V E vs 发点 vt 收点 其余 中间点 c vi vj 弧 vi vj 的容量 简写为cij G V A C 容量网络 fij 弧 vi vj 上的流量 2 可行流与最大流可行流满足 8 3最大流问题 3 增广链 几个概念 对可行流 8 3最大流问题 8 3最大流问题 增广链 设f是一可行流 是从始点到终点的一条链 若 满足下列条件 称其为一条增广链 4 割集和割量 截集和截量 最小割 割集 S T 的容量之和 称为 S T 的割集容量 割量 其中最小者为G的最小割集容量 最小割 8 3最大流问题 定义 G V A C 中 Vs Vt为发 收点 若有弧集E 把图G分为两个子图G1 G2 其顶点集分别记为S和T Vs Vt分属S T中 有 G V E E 不连通 E 为E 的真子集 而G V E E 仍连通 则称E 为G的割集 记E S T 5 最大流 最小割定理 8 3最大流问题 任一图G中 从Vs到Vt的最大流的流量等于分离Vs Vt的最小割的容量 8 3最大流问题 6 求最大流的标号算法 分两步 第1步 标号过程 通过标号来寻找可增广链 第2步 调整过程 沿可增广链调整f以增加流量 8 3最大流问题 6 求最大流的标号算法 1 标号过程 发点标号 选择一个已标号顶点Vi 对于Vi所有未标号的邻接点Vj进行标号 处理规则如下 a Vj Vi E 且fji 0 则令 j min fji i 并给Vj标号 Vi j b Vi Vj E 且fij 0 则令 j min cij fij i 并给Vj标号 Vi j 重复上述标号过程 直到Vt被标号或不再有顶点可标号为止 8 3最大流问题 6 求最大流的标号算法 2 调整过程 a Vi Vj 为可增广链上前向边 Vi Vj 为可增广链上后向边 Vi Vj 不在可增广链上 b 去掉所有标号 回到第 1 步 重新标号 8 4最小费用流问题 最小部分树问题的应用例子 已知有A B C D E F六个城镇间的道路网络如图 现要在六个城镇间架设通讯网络 均沿道路架设 每段道路上的架设费用如图 求能保证各城镇均能通话且总架设费用最少的架设方案 E A C B F D 5 10 6 9 3 5 3 9 7 8 2 8 4 最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划 下面给出一