运筹学__图与网络分析(11-11).ppt

第八章图与网络分析 引例 哥尼斯堡七桥问题 环球旅行问题 环球旅行问题的解 第1节图与网络的基本知识 图可以用来做什么 管理当中 事物及事物间的联系可以用图来描述 五只球队的比赛情况 工作分配问题 图已经应用于物质结构 交通 信息传递等的描述 图与网络的基本概念 1 图 这里讨论的图由点以及点与点间的连线构成 与平面几何的图不同 这里只关心图中有多少个点 点与点间有无连线 至于点与点间的连线是直线还是曲线 点的相对位置 则是无关紧要的 图与网络的基本概念 2 定义1一个图是由点集V vi 和V中的元素的无序对的一个集合E ek 所构成的二元组 记为G V E V中的元素vi叫做顶点 E中的元素ek叫做边 V v1 v2 v3 v4 v5 E e1 e2 e3 e4 e5 e6 e1 v1 v1 e2 v1 v2 例 图与网络的基本概念 3 相邻 图中的两点间存在连线 边 则称这两点相邻 并称它们是这条边的端点 若两条边有公共的端点 则称这两条边相邻 并称它们是其公共端点的关联边 边数 m G E 顶点数 n G V 图与网络的基本概念 4 无向边与无向图 若图中任一条边的端点无序 即 vi vj 与 vj vi 是同一条边 则称它为无向边 此时图称为无向图 有向图 若图中边 vi vj 的端点是有序的 则称它是有向边 或弧 vi与vj分别称为这条有向边的始点和终点 相应的图称为有向图 图与网络的基本概念 5 v2 v1 v5 v3 v4 e2 e1 e3 e4 e5 e6 环 自回路 多重边 定义2不含环和多重边的图称为简单图 含多重边的图称为多重图 图与网络的基本概念 6 定义3每一对顶点间都有边相连的无向简单图称为无向完全图 有向完全图是指每一对顶点间有且仅有一条有向边的简单图 完全图顶点数n与边数m间成立如下关系 m n n 1 2 图与网络的基本概念 7 定义4图G V E 的点集V可以分为两个非空子集X Y 即X Y V X Y 使得E中的每条边的两个端点中必有一个属于X 另一个属于Y 则称G为二部图 偶图 有时记为G X Y E 图与网络的基本概念 8 定义5以v为端点的边数 叫做点v的次 degree 记作deg v 或简记为d v d v1 4 d v2 3 悬挂点 孤立点 悬挂边 偶点 奇点 图中顶点次的性质 定理1任何图中顶点次数的总和等于边数的2倍 定理2任何图中次为奇数的顶点必有偶数个 定义6在有向图中 以顶点v为始点的边数称为顶点v的出次 记为d v 以v为终点的边数称为v的入次 记为d v 顶点v的出次与入次的和称为点v的次 图与网络的基本概念 9 定义7图G V E 若E 是E的子集 若V 是V的子集 且E 中的边仅与V 中的顶点相关联 则称G V E 为图G的一个子图 特别地 若V V 则称G 为G的一个生成子图 支撑子图 图与网络的基本概念 10 有时需要用图来表示事物及事物之间的定量的联系 这时图中除了顶点与边外 还有与点或边有关的某些数量指标 常称它们为 权 权在图中可以表示距离 费用 通过能力等 这种点或边带权的图称为网络 或赋权图 连通图 1 定义8无向图中一个点 边交错的序列 序列中的第一个和最后一个元素都是点 若其中每条边以序列中位于它之前和之后的点为端点 则称这个点边序列为图中连接其第一个点与最后一个点的链 链中所含的边数称为链长 链 但只是简单链而非初等链 简单链 没有重复边 初等链 既无重复边也无重复点 对有向图可类似定义链 如果各边的方向一致 则称为道路 连通图 2 定义9若在无向图中 一条链的第一个点与最后一个点重合 则称这条链为圈 只有重复点而无重复边的圈为简单圈 既无重复点又无重复边的圈为初等圈 初等圈 非简单的圈 连通图 3 路 边的方向一致 不是路 连通图 4 定义10一个图中任意两点间至少有一条链相连 则称此图为连通图 任何一个不连通图总可以分为若干个连通子图 每一个称为原图的一个分图 连通分支 连通图 非连通图 图的矩阵表示 邻接矩阵 对于图G V E V n 构造一个矩阵A aij n n 其中 图的矩阵表示 权矩阵 对于网络 赋权图 G V E V n 其中边 vi vj 上有权wij 构造一个矩阵A aij n n 其中 欧拉回路 1 定义13连通图G中 若存在一条道路 经过每边一次且仅一次 则称这条道路为欧拉道路 若存在一条回路经过每边一次也仅一次 则称这条回路为欧拉回路 具有欧拉回路的图称为欧拉图 E图 定理3无向连通图G是欧拉图 当且仅当G中无奇点 欧拉回路 2 推论1无向连通图G为欧拉图 当且仅当G的边集可以划分为若干个初等回路 推论2无向连通图G中有欧拉道路 当且仅当G中恰好有两个奇点 哥尼斯堡七桥问题无解 一笔画问题 欧拉回路 3 定理4连通有向图G是欧拉图 当且仅当它的每个顶点的出次等于入次 连通有向图G有欧拉道路 当且仅当这个图中除了两个顶点外 其余每个顶点的出次等于入次 且这两个顶点中 一个顶点的入次比出次多1 另一个的入次比出次少1 树 树的概念 定义14连通且不含圈的无向图称为树 树中次为1的点称为树叶 次大于1的点称为分枝点 树 树的性质 定理6T V E V n E m 则下列关于树的说法是等价的 1 T是一个树 即T是不含圈的连通图 树 树的性质 2 T无圈 且m n 1 树 树的性质 3 T连通 且m n 1 树 树的性质 4 T无圈 但每加一新边就得到唯一的一个圈 T是边数最多的无圈图 树 树的性质 5 T连通 但任舍去一边就不连通 T是边数最少的连通图 树 树的性质 6 T中任意两点有唯一一条链相连 生成树 概念 定义15若图G的生成子图是一棵树 则称该树为图G的生成树 支撑树 或简称为图G的树 定理7图G有生成树的充分必要条件是图G是连通的 生成树 解法 1 避圈法 这种方法是每步从连通图中选出一条边 使得它与已经选出的边不构成圈 直到选够n 1条边为止 一个图的生成树不是唯一的 避圈法的另一种表述 先去掉图G中所有边 只留下点 每次任意放回一条边 使之与已经放回的边不构成圈 反复进行 直到有 n 1 条边为止 5个顶点 4条边 生成树 解法 2 破圈法 这种方法是每步从连通图中选一个圈 并去掉该圈的一条边 直到图中不含圈为止 另一种解法 最小生成树 概念 定义16连通图G V E 每条边上有非负权L e 一棵生成树上各边的权之和 称为这棵生成树的权 具有最小权的生成树 称为最小生成树 最小支撑树 简称最小树 例如如何用造价最省的电话线网将各有关单位连起来的问题 就归结为求最小生成树的问题 3 5 4 3 6 7 1 2 4 非最小树 最小生成树 解法1 Kruskal算法 避圈法 这种方法每步从图中挑选一条边 满足 1 它与已经选出的边不构成圈 2 它是满足条件 1 的权最小的边 直到选够n 1条边为止 9个顶点 8条边 避圈法另一种表述 先去掉图G的所有边 只留下顶点 每次放回一条权最小的边 使之与已经放回的边不构成圈 反复进行 直到有 n 1 条边为止 9 4 8 2 3 3 3 7 9 1 4 2 3 3 1 6个顶点 5条边 最小生成树 解法 2 破圈法 这种方法每步从图中任选一个圈 然后去掉该圈中权最大的边 直到图中没有圈为止 1 4 1 2 1 3 1 4 4 5 5 3 2 4 5 2 9个顶点 8条边 破圈法举例 9 4 8 2 3 3 3 7 9 1 9 4 8 2 3 3 3 7 9 1 6个顶点 5条边 破圈法举例 最小生成树的权 9 最短路问题 最短路问题是网络理论中应用最广泛的问题之一 许多优化问题 如设备更新 管道铺设 线路安排等都可以化为最短路问题求解 最短路问题的提法 设G V E 为连通图 图中的各边 vi vj 有非负权lij lij 表示vi vj间无边 vs vt是图中任意两点 求一条道路 使它是从vs到vt的所有道路中总权最小的道路 Dijkstra算法 原理 若 vs v1 vn 1 vn 是vs到vn的最短路 则 vs v1 vn 1 是vs到vn 1的最短路 思路 采用标号法 使用两种标号 T标号和P标号 一个点的P标号是永久性标号 表示起点到该点最短路的权 它一旦给出就不再改变 而点的T标号是临时性的标号 表示对起点到该点最短路的权的估计值 当得到更精确的估计值时要修改原来的T标号 此外算法的每一步要把某一个点的T标号改成P标号 当得到终点vt的P标号时算法结束 Dijkstra算法步骤 第一步 给vs点P标号P vs 0 其余点T标号T vi 第二步 若vi为刚获得P标号的点 则修改以vi为起点的各边终点的T标号为下两个数中的较小者 一个是vi的P标号与该边权之和 另一个是该终点原来的T标号 第三步 取所有具有T标号的点中T标号值最小的点 将其T标号改为P标号 若本次得到P标号的点为终点 算法终止 否则返回上一步 例 p251 给起点P标号0 其余点T标号 在下面的求解过程中 粉色的数字为P标号 修改以刚获得P标号的点为起点的边的终点的T标号 然后将最小的T标号改成P标号 4 6 5 4 4 7 7 9 6 5 5 4 1 0 4 9 6 8 最短路线见图 v1 v2 v3 v4 v6 v5 v7 v8 3 8 4 2 2 4 3 3 1 2 3 3 4 0 T v2 min 0 4 4 T v3 min 0 8 8黄色数字表示P标号 最短路问题举例 v1 v2 v3 v4 v6 v5 v7 v8 3 8 4 2 2 4 3 3 1 2 3 3 4 0 4 8 比较所有的T标号 4最小 所以P v2 4 4 从v2出发 到v4 v5 T v4 min 4 3 7 T v5 min 4 4 8 7 8 v1 v2 v3 v4 v6 v5 v7 v8 3 8 4 2 2 4 3 3 1 2 3 3 4 0 4 8 比较所有的T标号 7最小 所以P v4 7 4 从v4出发 到v6 T v6 min 7 3 10 7 8 7 10 v1 v2 v3 v4 v6 v5 v7 v8 3 8 4 2 2 4 3 3 1 2 3 3 4 0 4 8 比较所有的T标号 8最小 所以P v3 P v5 8 4 从v3出发 到v7 T v7 min 8 3 11从v5出发 到v8 T v8 min 8 4 12 7 8 7 10 8 8 11 12 v1 v2 v3 v4 v6 v5 v7 v8 3 8 4 2 2 4 3 3 1 2 3 3 4 0 4 8 比较所有的T标号 10最小 所以P v6 10 4 从v6出发 到v7 T v7 min 11 10 3 11比较所有的T标号 11最小 所以P v7 11 7 8 7 10 8 8 12 10 11 11 v1 v2 v3 v4 v6 v5 v7 v8 3 8 4 2 2 4 3 3 1 2 3 3 4 0 4 8 4 从v7