运筹学图与网络1(qh).ppt

第十章图与网络分析 引言图论是专门研究图的理论的一门数学分支 属于离散数学范畴 与运筹学有交叉 它有200多年历史 大体可划分为三个阶段 第一阶段是从十八世纪中叶到十九世纪中叶 处于萌芽阶段 多数问题为游戏而产生 最有代表性的工作是所谓的Euler七桥问题 1736年 即一笔画问题 第二阶段是从十九世纪中叶到二十世纪中叶 这时 图论问题大量出现 如Hamilton问题 地图染色的四色问题以及可平面性问题等 这时 也出现用图解决实际问题 如Cayley把树应用于化学领域 Kirchhoff用树去研究电网络等 第三阶段是二十世纪中叶以后 由生产管理 军事 交通 运输 计算机网络等方面提出实际问题 以及大型计算机使大规模问题的求解成为可能 特别是以Ford和Fulkerson建立的网络流理论 与线性规划 动态规划等优化理论和方法相互渗透 促进了图论对实际问题的应用 例10 1 哥尼斯堡七桥问题哥尼斯堡 现名加里宁格勒 是欧洲一个城市 Pregei河把该城分成两部分 河中有两个小岛 十八世纪时 河两边及小岛之间共有七座桥 当时人们提出这样的问题 有没有办法从某处 如A 出发 经过各桥一次且仅一次最后回到原地呢 A B C D 最后 数学家Euler在1736年巧妙地给出了这个问题的答案 并因此奠定了图论的基础 Euler把A B C D四块陆地分别收缩成四个顶点 把桥表示成连接对应顶点之间的边 问题转化为从任意一点出发 能不能经过各边一次且仅一次 最后返回该点 这就是著名的Euler问题 A C B D 例10 2 有7个人围桌而坐 如果要求每次相邻的人都与以前完全不同 试问不同的就座方案共有多少种 用顶点表示人 用边表示两者相邻 因为最初任何两个人都允许相邻 所以任何两点都可以有边相连 1 2 3 7 6 4 5 假定第一次就座方案是 1 2 3 4 5 6 7 1 那么第二次就座方案就不允许这些顶点之间继续相邻 只能从图中删去这些边 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 假定第二次就座方案是 1 3 5 7 2 4 6 1 那么第三次就座方案就不允许这些顶点之间继续相邻 只能从图中删去这些边 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 假定第三次就座方案是 1 4 7 3 6 2 5 1 那么第四次就座方案就不允许这些顶点之间继续相邻 只能从图中删去这些边 只留下7点孤立点 所以该问题只有三个就座方案 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 例10 3 哈密顿 Hamilton 回路是十九世纪英国数学家哈密顿提出 给出一个正12面体图形 共有20个顶点表示20个城市 要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次 最后回到原处的周游世界线路 并不要求经过每条边 一 有甲 乙 丙 丁 戊 己6名运动员报名参加A B C D E F 6项比赛 下表给出6个运动员报名参加的比赛项目 问6个项目比赛顺序如何安排 做到每名运动员不连续参加两项比赛 甲 乙 丙 丁 戊 己 ABCDEF 解 比赛项目作为点 两个比赛项目由同一个人参加连一边 如图 A B D F C E 比赛顺序可安排A C B F E D或A F B C D E 甲 乙 丙 丁 戊 己 ABCDEF 10 1图的基本概念图论是专门研究图的理论的一门数学分支 主要研究点和线之间的几何关系 定义 图 设G V E 其中 V v1 v2 vm 是m个顶点集合 E e1 e2 en 是n条边集合 是描述边与顶点之间关系的函数 称G V E 为一个图 如果它满足 1 V非空 2 E是一个不与V中顶点相交的边集合 3 是关联函数 V E 称为图的三要素 说明 1 V非空 即没有顶点的图不讨论 2 E无非空条件 即允许没有边 3 条件 2 是指点只在边的端点处相交 4 任一条边必须与一对顶点关联 反之不然 v1 v3 v2 v4 v5 v1 v3 v2 v4 v5 有向图 v1 v3 v2 v4 v6 v5 e1 e3 e5 e6 e4 e8 e7 e2 例10 5 V v1 v2 v6 E e1 e2 e8 e1 v1 v2 e2 v1 v2 e7 v3 v5 e8 v4 v4 次 度 与顶点关联的边数 简单图 没有环和重边的图 悬挂点 次为1的点 悬挂边 次为1的边 孤立点 次为0的点 e8 v4 v4 称为自回路 环 v6是孤立点 v5为悬挂点 e7为悬挂边 顶点v3的次为4 顶点v2的次为3 定理1 在一个图中 所有顶点次的和等于边的两倍 定理8 1 在一个图中 所有顶点次的和等于边的两倍 定理2 在任意一个图中 奇顶点的个数必为偶数 证明 设V1和V2分别为G中奇点和偶点的集合 定理8 1 在一个图中 所有顶点次的和等于边的两倍 定理8 2 在任意一个图中 奇顶点的个数必为偶数 注意 一个图的形状并不唯一 但它的三要素是不能变的 注意 一个图的形状并不唯一 但它的三要素是不能变的 例如 这两个图均为K4 v1 v2 v3 v4 v1 v2 v3 v4 定义 设G V E 和G1 V1 E1 1 如果V1 V E1 E则称G1为G的子图 如果G1 V1 E1 1 是G V E 子图 并且V1 V 则称G1为G的生成子图 如果V1 V E1是E中所有端点属于V1的边组成的集合 则称G1是G的关于V1的导出子图 如果G1 V1 E1 1 是G V E 子图 并且V1 V 则称G1为G的生成 支撑 子图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 v1 v5 v4 v2 e1 e5 e3 a 的子图 v1 v5 v4 v2 v3 e8 e6 e5 e2 a 的生成子图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 v1 v5 v4 v2 e1 e8 e7 e6 e5 e4 e3 a 的导出子图 定义 简单图 如果图中任意两个顶点之间至多有一条边 则称为简单图 否则称为多重图 即 无环 无重边的图 定义 简单图 如果图中任意两个顶点之间至多有一条边 则称为简单图 否则称为多重图 定义 有向图 如果图中每一条边都规定了方向 则称为有向图 有向图去掉箭头得到的图称为基础图 定义 链 如果图中的某些点 边可以排列成点和边的交错序列 则称此为一条链 定义 链 如果图中的某些点 边可以排列成点和边的交错序列 则称此为一条链 定义 圈 如一条链中起点和终点重合 则称此为一条圈 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向图 链 路 初等链 点不同 简单链 边不同 v1 v5 v4 v2 e1 e7 e6 e3 v1 v5 v4 v2 e1 e7 e6 e3 v1 v5 v4 v2 e1 e7 e6 e3 v1 v5 v4 v2 e1 e7 e6 e3 圈 回路 连通图 图中任何两个点之间必有一条链 否则 称为不连通图 v1 v5 v4 v2 v3 e1 e7 e6 e5 e4 e3 e2 v6 v7 v8 二 图的矩阵表示一个图非常直观 但是不容易计算 特别不容易在计算机上进行计算 一个有效的解决办法是将图表示成矩阵形式 通常采用的矩阵是邻接矩阵 边长邻接矩阵 弧长矩阵和关联矩阵 1邻接矩阵邻接矩阵A表示图G的顶点之间的邻接关系 它是一个n n的矩阵 如果两个顶点之间有边相联时 记为1 否则为0 v1 v2 v3 v4 v1v2v3v4v10111v21110v31101v41010 无向图的邻接矩阵是对称矩阵 v1 v2 v3 v4 v1 v5 v4 v3 v2 也可以对有向图 v1v2v3v4v5v100011v210010v301100v401101v510010 二 边长邻接矩阵在图的各边上一个数量指标 具体表示这条边的权 距离 单价 通过能力等 赋权图或网络 无向网络 有向网络 混合网络 边权网络 点权网络 以边长代替邻接矩阵中的元素得到边长邻接矩阵 v1 v2 v3 v4 2 5 6 4 3 4 v1v2v3v4v10256v2243 v35304v46 40 其中 表示两点之间不能连接 3弧长矩阵对有向图的弧可以用弧长矩阵来表示 其中 表示两点之间没有弧连接 v1 v5 v4 v3 v2 1 4 2 3 2 2 6 1 2 v1v2v3v4v5v101 2v2 02 4v3 201 v4 3206v5 0 4关联矩阵关联矩阵B揭示了图G的顶点和边之间的关联关系 它是一个nxm矩阵 1 vi vk ejBij 1 vk vi ej0其他 v1 v2 v4 v3 e1 e2 e4 e3 e7 e5 e6 e1e2e3e4e5e6e7v11 110000v200 1 1 100v3010101 1v4 10001 11 对无向图不存在 1元素 10 2最优树问题 或最小树 树是一类极其简单而很有用的图 定义 链 如果图中的某些点 边可以排列成点和边的交错序列 则称此为一条链 定义 链 如果图中的某些点 边可以排列成点和边的交错序列 则称此为一条链 定义 圈 如一条链中起点和终点重合 则称此为一条圈 定义 连通图 如果图中的任意两点之间至少存在一条通路 则称图为连通图 否则为不连通图 定义 连通图 如果图中的任意两点之间至少存在一条通路 则称图为连通图 否则为不连通图 定义 树 一个无圈的连通图称为树 如果一个无圈的图中每一个分支都是树 则称图为森林 定理3 设图G V E 是一个树 顶点个数 则G中至少有两个悬挂点 证明 设是G中含边数最多的初等链 往证是悬挂点 若 则存在边因为G为树 不含圈 故不在P上 是比P更长的初等链 矛盾 定理4 设图G V E 是一个树的充分必要条件是G不含圈 且恰有条边 证明 必要性 用数学归纳法 时 显然成立 设对时也成立 设图G含n 1个点 由定理3 G含悬挂点 考虑图 有充分性 往证G为连通图 若G不为连通图 则有s s 2 个连通分图 每一个都连通不含圈 即为树 矛盾 定理5 设图G V E 是一个树的充分必要条件是G是连通图 且证明 必要性 由定理4即得 充分性 往证G不含圈 对点用数学归纳法 时 显然成立 设对时也成立 设图G含n 1个点 G必含悬挂点 否则 设是G的悬挂点 考虑仍为连通图 由归纳假设知不含圈 则G必不含圈 定理6 设图G V E 是一个树的充分必要条件是G的任意顶点之间恰有一条链 矛盾 1 G不含圈 2 G是连通图 3 4 图G V E 是一个树上述条件有两个成立 就推出其余条件成立 树的性质 1在图中任意两点之间必有一条而且只有一条通路 树的性质 1在图中任意两点之间必有一条而且只有一条通路 2在图中划去一条边 则图不连通 树是边最少的连通图 树的性质 1在图中任意两点之间必有一条而且只有一条通路 2在图中划去一条边 则图不连通 3在图中不相邻的两个顶点之间加一条边 可得一个且仅得一个圈 树的性质 1在图中任意两点之间必有一条而且只有一条通路 2在图中划去一条边 则图不连通 3在图中不相邻的两个顶点之间加一条边 可得一个且仅得一个圈 4图中边数有n p 1 p为顶点数 a b c f e d h g 例10 6 b f e d b f d g b c e d a b c h a f d g 定义 生成树 如果图T是G的一个生成子图 而且T又是一棵树 则称图T为一棵生成树 对于分离 不连通图 图 则称为生成森林 一个子图与生成树的区别是 子图与原图相比少弧又少点 生成树与原图相比少弧不少点 定理图G有生成树的充分必要条件为图是连通图 定义 最优树 在赋权图G中 一棵生成树所有树枝上权的和 称为生成树的权 具有最小权的生成树 称为最优树 或最小树 求最小树的方法有破圈法和避圈法 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 例10 7 破圈法 在给定连通图G中 任取一圈 去掉一条最大权边 如果有两条或两条以上的边都是权最大的边 则任意去掉其中一条边 在余图中 是图G的支撑子图 任取一圈 去掉一条最大权边 重复下去 直到余图中无圈为止 即可得到图G的最小树 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 17 4 1 23 总造价 1 4 9 3 17 23 57 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 避圈法 kruskal算法 在连通图G中 任取权值最小的一条边 若有两条或两条以权数相同且最小 则任取一条 在未选边中选一条权值权值最小的边 要求所选边与已选边不构成圈 重复下去 直到不存在与已选边不构成圈的边为止 已选边与顶点构成的图T就是所求最小树 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 总造价 1 4 9 3 17 23 57 3最短路问题 1959年Dijkstra给出最短路算法 最短路问题是网络分析中的一个基本问题 它不仅可以直接应用于于解决生产实际的许多问题 若管道铺设 线路安排 厂区布局等 而且经常被作为一个基本工具 用于解决其它的优化问题 定义给定一个赋权有向图D V A 记D中每一条弧上的权为为 给定D中一个起点和终点 设P是D中从到的一条路 则定义路P的权是P中所有弧的权之和 记为 即又若P 是D图中到的一条路 且满足则称P 为从到的最短路 下面介绍在一个赋权有向图中寻求最短路的方法 这种方法实际上求出了从给定到任一个顶点的最短路 如下事实是经常要利用的 即如果P是D中从到的最短路 是P中的一点 那么从沿P到路也是从到的最短路 事实上 如果这个结论不成立 设Q是从到的最短路 令P 是从沿Q到达 再从沿P到达的路 那么P 的权就比P的权小 这与P是从到的最短路矛盾 P P Q P 例1 求图A到B的最短路 A B C D E F G 1 3 5 3 5 8 4 6 1 2 4 5 0 B C D E F G 1 3 5 3 5 8 4 6 1 2 4 5 0 1 3 B C D E F G 1 3 5 3 5 8 4 6 1 2 4 5 0 1 3 6 4 B C D E F G 1 3 5 3 5 8 4 6 1 2 4 5 0 1 3 6 4 5 B C D E F G 1 3 5 3 5 8 4 6 1 2 4 5 0 1 3 6 4 5 9 最短路为ACGFB v7 v6 v4 v3 G 7 1 8 2 4 3 3 1 4 7 2 0 2 v1 v2 v5 例2 求图到的最短路 v1 v7 v7 v6 v4 v3 G 7 1 8 2 4 3 3 1 4 7 2 0 2 v1 v2 v5 1 4 v7 v6 v4 v3 G 7 1 8 2 4 3 3 1 4 7 2 0 2 v1 v2 v5 5 1 4 v7 v6 v4 v3 G 7 1 8 2 4 3 3 1 4 7 2 0 2 v1 v2 v5 5 4 1 4 v7 v6 v4 v3 G 7 1 8 2 4 3 3 1 4 7 2 0 2 v1 v2 v5 5 7 4 1 4 v7 v6 v4 v3 G 7 1 8 2 4 3 3 1 4 7 2 0 2 v1 v2 v5 5 7 4 9 1 4 v1到v7的最短路径是 v1 v3 v4 v7 5分 最短距离为1 4 2 7 v7 v6 v4 v3 G 7 1 8 2 4 3 3 1 4 7 2 0 2 v1 v2 v5 5 7 4 9 1 4 v1到v7的最短路径是 v1 v3 v4 v7 5分 最短距离为1 4 2 7 例 某交通网络如下图 求v1到v8的最短路线解 v1 v2 v4 v5 v6 v7 v8 6 3 1 2 2 1 6 10 4 3 10 4 4 6 练习 求最短路 v1 v2 v4 v5 v6 v7 v8 6 3 1 2 2 1 6 10 4 3 10 4 4 6 v1 V2 v3 5 V3 v1 3 V4 v1 1 V5 v2 6 V6 v5 10 6 3 1 2 2 1 6 10 4 10 4 3 6 4 V2 v1 6 v7 v5 9 v8 v5 12 例设备更新问题某工厂使用一台设备 每年年初工厂要作出决定 继续使用 购买新的 如果继续使用旧的 要负维修费 若要购买一套新的 要负购买费 试确定一个5年计划 使总支出最小 若已知设备在各年的购买费 及不同机器役龄时的残值与维修费 如表1所示表1 解 把这个问题化为最短路问题 设bi表示设备在第i年年初的购买费 ci表示设备使用i年后的维修费 V v1 v2 v6 点vi表示第i年年初购进一台新设备 虚设一个点v6表示第5年年底 E vivj 1 i j 6 若每年购置一台新设备 则购置费为 11 11 12 12 13 59 每年的维修费为5元 共59 5 5 84 若在1 2 3年购置一台新设备 则购置费为 11 12 13 36 每年的维修费为 5 6 5 6 5 27 共36 27 63 设备使用一年后就更新则不划算 由表1知 设备使用三年后应当更新 这样上述设备更新问题就变为 在有向赋权图G V E F 图解如下 中求v1到v6的最短路问题 由实际问题可知 设备使用三年后应当更新 因此删除该图中v1到v5 v1到v6 v2到v6的连线 又设备使用一年后就更新则不划算 因此再删除该图中v1v2 v2v3 v3v4 v4v5 v5v6五条连线后得到 从上图中容易得到v1到v6只有两条路 v1v3v6 费用22 31 和v1v4v6 费用22 31 而这两条路都是v1到v6的最短路 3网络最大流问题 引例 如下输水网络 南水北调工程 从vs到vt送水 弧旁数字前者为管道容量 后者为现行流量 如何调整使输水最多 vs vt v2 v1 v4 v3 3 3 5 1 1 1 4 3 1 1 2 2 3 0 2 1 5 3 容量 每个弧上的最大通过能力 用cij表示 即弧上的第一个数字 流量 弧上实际通过的流量 用xij表示 弧上的第二个数字 显然0 xij cij 如果xij cij则称为饱和弧 最大流问题的相关概念网络 给定了弧的容量C vi vj 的有向图D V A C 叫做一个网络 fij记为流量 cij记为容量 可行流 1 2 各点流入量 流出量 且vs的流出量 vt的流入量 这样的流称之为可行流截集 分离始点vs和终点vt的弧的集合 叫做截集截量 截集的容量叫做截量 的弧称为饱和弧 的弧称为非饱和弧 的弧称为零流弧 的弧称为非零流弧 若 是网络中从发点到收点的链 链上的弧分为两类 一类与链的方向一致 叫做前向弧 记为 另一类与链的方向相反 叫做后向弧 记为 增广链 是可行流 是一条从发点到收点的链 若在前向弧上 即在中每一弧是非饱和弧 在后向弧上 即在中每一弧是非零流 则称此链为增广链 vs vt v2 v1 v4 v3 3 3 5 1 1 1 4 3 1 1 2 2 3 0 2 1 5 3 增广链 是可行流 是一条从发点到收点的链 若在前向弧上 即在中每一弧是非饱和弧 在后向弧上 即在中每一弧是非零流 则称此链为增广链 1标号方法很简单 首先找到一条增广链 沿此进行最大可能调整 再找增广链 再调整 直到没有增广链 寻找增广链的标号法 先给vs标号 0 而后依次审查各条弧 vi vj 对前向弧 饱和否 不饱和 使其增加 给vj点标号 vi l vj 对后向弧 是否非零流弧 使其减少 是 给vj标号 vi l vj 直到给vt标上号 就得到了增广链 调整对于增广链 求最大流的方法 调整令 得到新的可行流 重新标号 直至标不下去为止 例 解水网最大流问题 vs V2 0 V1 3 3 5 1 1 1 4 3 1 1 2 2 3 0 5 3 2 1 V4 V3 Vt vs 4 v1 1 v2 1 v2 1 v3 1 1标号 对前向弧 饱和否 不饱和 使其增加 给vj点标号 vi l vj 对后向弧 是否非零流弧 使其减少 是 给vj标号 vi l vj 直到给vt标上号 就得到了增广链 vs V2 0 V1 3 3 5 2 1 0 4 3 1 0 2 2 3 0 5 3 2 2 V4 V3 Vt vs 3 2沿增广链进行调整 前向弧增加1 后向弧减少l vs V2 0 V1 3 3 5 2 1 0 4 3 1 0 2 2 3 0 5 3 2 2 V4 V3 Vt vs 3 vs V2 V1 V3 V4 Vt 3 3 5 2 4 3 1 0 1 0 2 2 3 0 5 3 2 2 0 vs 3 重新标号 直至标不下去为止 最小截集为 vs v2 v1 v3 容量为5 最大流也为5 例1 求从发点V1到收点V7的最大流 弧的流量放在括号内 如图 V 20 4 3 例2 求图的最大流和最小割 图中标号为 vs V2 V1 V3 V4 Vt 2 0 8 8 7 5 9 9 9 4 5 5 10 8 5 4 6 1 6 中国邮递员问题 证明 定理1对连通图G V E 下列条件是相互等价的 1 G是一个欧拉图 2 G的每一个节点的度数都是偶数 3 G的边集合E可以分解为若干个回路的并 证明 1 2 已知G为欧拉图 则必存在一个欧拉回路 回路中的节点都是偶度数 2 3 设G中每一个节点的度数均为偶数 若能找到一个回路C1使G C1 则结论成立 否则 令G1 G C1 由C1上每个节点的度数均为偶数 则G1中的每个节点的度数亦均为偶数 于是在G1必存在另一个回路C2 令G2 G1 C2 由于G为有限图 上述过程经过有限步 最后必得一个回路Cr使Gr Gr 1 Cr上各节点的度数均为零 即Cr Gr 1 这样就得到 的一个分解 3 4 设其中 i 1 2 r 均为回路 由于G为连通图 对任意回路 必存在另一个回路与之相连 即存在共同的节点 现在我们从图G的任意节点出发 沿着所在的回路走 每走到一个共同的节点处 就转向另一个回路 这样一直走下去就可走遍G的每条边且只走过一次 最后回到原出发节点 即G为一个欧拉图 设G V E 为一个图 若存在一条回路 使它经过图中每条边且只经过一次又回到起始点 就称这种回路为欧拉回路 并称图G为欧图 利用定理1去判断一个连通图是否为欧拉图比较容易 但要找出欧拉回路 当连通图比较复杂时就不太容易了 下面介绍一种求欧拉回路的算法 弗罗莱算法算法步骤如下 1 任取起始点 2 设路 已选出 则从E 中选出边 使 与 相连 除非没有其它选择 仍应为连通的 3 重复步骤 2 直至不能进行下去为止 定理2连通的有向图存在欧拉回路的充分必要条件是对任意节点 进入该节点边数 进数 与离开该点的边数 出数 相等 中国邮递员问题一名邮递员带着要分发的邮件从邮局出发 经过要分发的每个街道 送完邮件后又返回邮局 如果他必须至少一次走过他管辖范围内的每一条街道 如何选择投递路线 使邮递员走尽可能少的路程 这个问题是由我国数学家管梅谷先生 山东师范大学数学系教授 在1962年首次提出的 因此在国际上称之为中国邮递员问题 用图论的述语 在一个连通的赋权图G V E 中 要寻找一条回路 使该回路包含G中的每条边至少一次 且该回路的权数最小 也就是说要从包含G的每条边的回路中找一条权数最小的回路如果G是欧拉图 则很容易由弗罗莱算法求出一个欧拉回路 但是若G不是欧拉图 即存在奇度数的节点 则中国由递员问题的解决要困难得多 本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法 例 已知邮递员要投递的街道如图11 20所示 试求最优邮路 解先找出奇节点 A1 A2 A3 A4 B1 B2 B3 B4 奇节点进行配对 不妨把A1与B1 A2与B2 A3与B3 A4与B4配对 求其最短路 显然它不是最优解 下面我们根据定理3来进行调解 1 2 第一次调整 删去多于一条的重复边 即A3与B3 A4与B4中的 A4 B3 调整后 实际上成为A1与B1 A2与B2 A3与A4 B3与B4的配对 它们的最短路如图11 21所示 图11 21 1 2 第二次调整 发现在回路 A1 A2 B2 A4 B3 B4 B1 A1 中重复边的权数和为11 大于该回路权数20的一半 因而调整时 把该回路的重复边删去 代之以重复其余部分 得图11 22 可以看出 实际上是调整为A1与A2 B1与B4 A3与A4 B2与B3配对 图11 21 1 2 图11 22 图11 23 P281 2从v8出发 因d v8 6 故可设vi1 vi2 vi3 vi4 vi5 vi6与v8相连 而V4 v5 v6 v7中必有一点与v8相连 否则与d v8 6矛盾 令vi1 v4 则vi1必与vi2 vi3 vi4 vi5 vi6中某点相连 否则 d vi1 3 与d v4 5矛盾 v8 vi6 vi5 vi4 vi3 Vi1 v4 vi2 6 中国邮递员问题 在奇点间加边 构造初始可行方案 寻找改进可行方案 在两奇点间检查所有链 若某链的长度小于已加重复边的长度 则在该链的每边加上重复边 去掉原重复边 重复以上步骤 直到任意两奇点间加重复边的链是最短的为止 求解中国邮递员问题 例子 例子的初始可行解 例子的修正解 四 奇偶点作业法的改进方法 奇偶点作业法的瓶颈是需检查太多的链可以首先求出任意一对奇点之间的最短路 从中选出总路长最小的组合方案 也可以由奇点构成偶图 求最小匹配得到最优解 一个四奇点的例子 第九章网络计划 9 1基本概念杜邦公司 关键路线法CPM确定型美国海军武器局 计划评审技术PERT网络图 有向赋权图 的构成结点 也称事项 一道工序的开始或结束工序 弧 相对独立的活动 消耗资源虚工序 只表示衔接关系 不消耗资源工序时间 权 完成工序的时间消耗 9 2 网络规则 1 避免循环 不留缺口2 一一对应 一道工序用两个事项表示3 从左向右依次展开例 A 4 B 6 D 7 E 5 F 9 H 4 I 8 C 6 G 7 9 3关键路线法 CPM 9 3 1时间参数运算什么是关键路线 1 作业时间t i j 经验数据 统计数据2 事项最早时间TE j max