运筹学课件 第八章 图与网络分析.ppt

引言图论是专门研究图的理论的一门数学分支 属于离散数学范畴 与运筹学有交叉 它有200多年历史 大体可划分为三个阶段 第一阶段是从十八世纪中叶到十九世纪中叶 处于萌芽阶段 多数问题围游戏而产生 最有代表性的工作是所谓的Euler七桥问题 即一笔画问题 第八章图与网络分析 第二阶段是从十九世纪中叶到二十世纪中叶 这时 图论问题大量出现 如Hamilton问题 地图染色的四色问题以及可平面性问题等 这时 也出现用图解决实际问题 如Cayley把树应用于化学领域 Kirchhoff用树去研究电网络等 第三阶段是二十世纪中叶以后 由生产管理 军事 交通 运输 计算机网络等方面提出实际问题 以及大型计算机使大规模问题的求解成为可能 特别是以Ford和Fulkerson建立的网络流理论 与线性规划 动态规划等优化理论和方法相互渗透 促进了图论对实际问题的应用 例 哥尼斯堡七桥问题哥尼斯堡 现名加里宁格勒 是欧洲一个城市 Pregei河把该城分成两部分 河中有两个小岛 十八世纪时 河两边及小岛之间共有七座桥 当时人们提出这样的问题 有没有办法从某处 如A 出发 经过各桥一次且仅一次最后回到原地呢 A B C D 最后 数学家Euler在1736年巧妙地给出了这个问题的答案 并因此奠定了图论的基础 Euler把A B C D四块陆地分别收缩成四个顶点 把桥表示成连接对应顶点之间的边 问题转化为从任意一点出发 能不能经过各边一次且仅一次 最后返回该点 这就是著名的Euler问题 A C B D 例 哈密顿 Hamilton 回路是十九世纪英国数学家哈密顿提出 给出一个正12面体图形 共有20个顶点表示20个城市 要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次 最后回到原处的周游世界线路 并不要求经过每条边 图的基本概念图论是专门研究图的理论的一门数学分支 主要研究点和线之间的几何关系 一 图与网络的基本概念1 图及其分类定义1 图 一个图由点集V和V中的元素无序对的一个集合 记为G V E 其中 V v1 v2 vm 是m个顶点集合 E e1 e2 en 是n条边集合 当V和E为有限集合时 G为有限图 2个点u v属于V 如果边 u v 属于E u v相邻 u v为边 u v 的端点 具有公共端点u的两条边 称为点u的关联边 第一节图与网络的基本知识 如果任一边 u v 属于E且端点无序 无向边 图G为无向图 如果任一边 u v 属于E且端点有序 有向边 图G为有向图m G E 表示图G的边数 n G V 表示图G的点数 环 自回路 一条边的两个端点如果相同 两个点之间多于一条边的 多重边 定义2 不含环和多重边的图 简单图 含有多重边的图 多重图 有向图中的两点之间有不同方向的两条边 不是多重边 简单图 定义3 每一对顶点间都有边相连的无向简单图 完全图 有向完全图 指每一对顶点间有且仅有一条有向边的简单图 定义4 图G V E 的点集V可以分为2个非空子集X Y 使得E中每条边的两个端点必有一个端点属于X 另一个端点属于Y G为二部图 偶图 有时记为 G X Y E V1 V4 V3 V2 X Y 2 顶点的次定义5 以点v为端点的边的个数称为点v的次 记作d v 如次为零的点称为弧立点 次为1的点称为悬挂点 悬挂点的边称为悬挂边 次为奇数的点称为奇点 次为偶数的点称为偶点 偶点 d v 偶数 奇点 d v 奇数 v1 v3 v2 v4 v6 v5 e1 e3 e5 e6 e4 e8 e7 e2 V v1 v2 v6 E e1 e2 e8 e1 v1 v2 e2 v1 v2 e7 v3 v5 e8 v4 v4 e8 v4 v4 称为自回路 环 v6是孤立点 v5为悬挂点 e7为悬挂边 顶点v3的次为4 顶点v4的次为4 定理1在一个图中 所有顶点次的和等于边的两倍 定理2在任意一个图中 次为奇数的顶点必为偶数个 定义6 有向图中 以vi为始点的边数称为点vi的出次 d vi 以vi为终点的边数称为点vi的入次 d vi 所有顶点的入次之和 所有顶点的出次之和 3 子图定义 设G V E 和G1 V1 E1 如果V1 V E1 E则称G1为G的子图 如果G1 V1 E1 是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 的生成子图 二 连通图定义8 如果图中的某些点 边可以排列成点和边的交错序列 v0 e1 v1 e2 v2 e3 v3 vn 1 en vn ei vi 1 vi 则称此为一条链 由两两相邻的点及其相关联边构成的点边序列 初等链 链中无重复的点和边 定义9 无向图中 如一条链中起点和终点重合 则称此链为圈 初等圈 圈中无重复的点和边 有向图中 当链 圈 上的边方向相同时 为道路 回路 道路道路回路 链 初等链 初等圈 道路 回路 连通图 图中任意两点之间均至少有一条通路 否则称为不连通图 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 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 圈 三 图的矩阵表示一个图非常直观 但是不容易计算 特别不容易在计算机上进行计算 一个有效的解决办法是将图表示成矩阵形式 通常采用的矩阵是邻接矩阵 边长邻接矩阵 弧长矩阵和关联矩阵 1 邻接矩阵邻接矩阵A表示图G的顶点之间的邻接关系 它是一个nxn的矩阵 如果两个顶点之间有边相联时 记为1 否则为0 定义12 对于G V E 构造矩阵A aij nxnaij 1 vi vj E0矩阵A为邻接矩阵 V1 V3 V5 V6 V4 V2 v1v2v3v4v5v6 2 权矩阵在图的各边上一个数量指标 具体表示这条边的权 距离 单价 通过能力等 以边长代替邻接矩阵中的元素得到边长邻接矩阵 定义11 赋权图G V E 其边 vi vj 有权wij 构造矩阵A aij nxnaij wij vi vj E0矩阵A为权矩阵 v1 v2 v5 v4 v3 9 2 4 3 8 6 7 4 5 v1v2v3v4v5 四 欧拉回路与中国邮政问题1 欧拉回路与道路定义13 连通图G 如果存在一条道路 经过每边一次且仅一次 则称这条路为欧拉道路 如果存在一条回路 经过每边一次且仅一次 则称这条路为欧拉回路 具有欧拉回路的图为欧拉图 定理3 无向连接图G是欧拉图 当且仅当G中无奇点 推论1 无向连接图G为欧拉图 当且仅当G的边集可划为若干个初等回路 推论2 无向连接图G为欧拉道路 当且仅当G恰好有2个奇点 定理4 连通有向图G是欧拉图 当且仅当它每个奇点的出次等于入次 2 中国邮路问题一个邮递员 从邮局出发 走遍所有街道后回到邮局 如何安排 使其总的路程最短 图论 给定一个连通图 每边有非负权 要求一条回路过每边至少一次 且满足总权最小 定理5 已知图G G E1无奇点 则L E1 l e 最小的充要条件 1 每条边最多重复一次 2 对图G中每个初等圈 重复边的长度和不超过圈长的1 2 例 求解网络的中国邮路问题 第一步 确定初始可行方案先检查图中是否有奇点 如果无奇点 为欧拉图 如果有奇点 图中的奇点的个数比为偶数个 所以可以两两配对 构造二重边 图中有4个奇点 v2 v4 v6 v8 配对v2 v4 v6 v8 构造二重边 重复边的总长 2l23 2l36 l69 l98 l23 2l87 2l74 l41 l12 51 第二步 调整可行方案 使重复边最多为一次重复边的总长 l69 l98 l41 l12 21 第三步 检查每个初等圈是否定理条件2 如果不满足 进行调整 直至满足为止 圈 v1v2v5v4v1 总长度24 重复边14 14 21大于1 2 调整 v2 v5 v5 v4 代替 v1 v2 v1 v4 圈 v1v2v5v4v1 总长度24 重复边6 4 10 重复边的总长 l69 l98 l45 l52 17再检查圈 v2v3v6v9v8v5v2 总长 24 重复边的长度13 继续调整 再次调整的重复边的总长 15 满足条件要求 图中任一欧拉回路为最优邮递回路 方法 简单 但要检查每一个初等圈 总结 图的基本概念 G V E