《运筹学基础及应用(第五版)(第六章图与网络分析)》由会员分享，可在线阅读，更多相关《运筹学基础及应用(第五版)(第六章图与网络分析)（81页珍藏版）》请在金锄头文库上搜索。
1、2020 4 4 1 运筹学OPERATIONSRESEARCH 2020 4 4 2 1 图的基本概念与模型 2 树图和图的最小部分树 3 最短路问题 4 网络的最大流 5 最小费用流 第六章图与网络分析 2020 4 4 3 当地的居民热衷于这样一个问题 一个漫步者如何能够走过这七座桥 并且每座桥只能走过一次 最终回到原出发地 尽管试验者很多 但是都没有成功 哥尼斯堡的七桥问题 2020 4 4 4 为了寻找答案 1736年欧拉把陆地缩为一点 把桥作为连接点的边 将这个问题抽象成图形的一笔画问题 即能否从某一点开始不重复地一笔画出这个图形 最终回到原点 欧拉在他的论文中证明了这是不可能的
2、因为这个图形中每一个顶点都与奇数条边相连接 不可能将它一笔画出 这就是古典图论中的第一个著名问题 2020 4 4 5 在实际的生产和生活中 人们为了反映事物之间的关系 常常在纸上用点和线来画出各式各样的示意图 例有六支球队进行足球比赛 我们分别用点v1 v6表示这六支球队 它们之间的比赛情况 也可以用图反映出来 已知v1队战胜v2队 v2队战胜v3队 v3队战胜v5队 如此等等 这个胜负情况 可以用下图所示的有向图反映出来 v3 v1 v2 v4 v6 v5 2020 4 4 6 6 1 图的基本概念与模型 图 graph 是由一些结点或顶点 nodesorvertices 以及连接点的边
3、edges 构成 记做G V E 其中V是顶点的集合 E是边的集合 给图中的点和边赋以具体的含义和权值 我们称这样的图为网络图 赋权图 一 基本概念 2020 4 4 7 图中的点用v表示 边用e表示 对每条边可用它所联结的点表示 如图 则有 e1 v1 v1 e2 v1 v2 或e2 v2 v1 用点和点之间的线所构成的图 反映实际生产和生活中的某些特定对象之间的特定关系 通常用点表示研究对象 用点与点之间的线表示研究对象之间的特定关系 一般情况下 图中点的相对位置如何 点与点之间线的长短曲直 对于反映研究对象之间的关系 显的并不重要 因此 图论中的图与几何图 工程图等本质上是不同的 202
4、0 4 4 8 端点 关联边 相邻 若边e可表示为e vi vj 称vi和vj是边e的端点 同时称边e为点vi和vj的关联边 若点vi vj与同一条边关联 称点vi和vj相邻 若边ei与ej有公共端点 称边ei和ej相邻 如果边e的两个端点相重 称该边为环 如果两个点之间的边多于一条 称为具有多重边 对无环 无多重边的图称为简单图 环 多重边 简单图 2020 4 4 9 次 奇点 偶点 孤立点 与某个点相关联的边的数目 称为该点的次 或度 线度 记作d v 次为奇数的点称为奇点 次为偶数的点称为偶点 次为零的点称为孤立点 如图 奇点为v5 v3 偶点为v1 v2 v4 v6 孤立点为v6 2
5、020 4 4 10 链 圈 路 回路 连通图 图中有些点和边的交替序列 v0 e1 v1 e2 ek vk 若其各边e1 e2 ek各不相同 且任意vi t 1 vit 2 t k 都相邻 称 为链 如果链中所有的顶点v0 v1 vk也不相同 这样的链成为路 起点和终点重合的链称为圈 起点和终点重合的路称为回路 若在一个图中 每一对顶点之间至少存在一条链 称这样的图为连通图 否则称该图为不连通的 链 路 圈 2020 4 4 11 完全图 偶图 一个简单图中若任意两点之间均有边相连 称这样的图为完全图 含有n个顶点的完全图 其边数有条 如果图的顶点能分成两个互不相交的非空集合V1和V2 使在
6、同一集合中任意两个顶点均不相邻 称这样的图为偶图 也称二分图 如果偶图的顶点集合V1和V2之间的每一对顶点都有一条边相连 称这样的图为完全偶图 完全偶图中V1含m个顶点 V2含有n个顶点 则其边数共m n条 2020 4 4 12 子图 部分图 图G1 V1 E1 和G2 V2 E2 如果有和 称G1是G2的一个子图 若有 则称G1是G2的一个部分图 注意 部分图也是子图 但子图不一定是部分图 子图 部分图 2020 4 4 13 2 树图和最小部分树 树图 简称树 记作T V E 是无圈的连通图 无圈 无多重边 一 树的性质 性质1 任何树中必存在次为1的点 次为1的点称为悬挂点 与之关联的
7、边称为悬挂边 性质2 具有n个顶点的树恰有 n 1 条边 性质3 任何具有n个点 n 1 条边连通图是树 说明 1 树中只要任意再加一条边 必出现圈 2 树中任意两点之间有且只有一条通路 从树中任意删掉一条边 就不再连通 树是最脆弱的连通图 2020 4 4 14 二 图的最小部分树 如果G1是G2的部分图 又是树图 则称G1是G2的部分树 或支撑树 树图的各条边称为树枝 假定各边均有权重 树枝总长最小的部分树 称为该图的最小部分树 也称最小支撑树 定理1 图中任一个点i 若j是与i相邻点中距离最近的 则边 i j 一定包含在该图的最小部分树中 推论 把图的所有点分成V和两个集合 则两集合之间
8、连线的最短边一定包含在最小部分树内 2020 4 4 15 三 避圈法和破圈法 寻找最小部分树的方法主要有避圈法和破圈法两种 避圈法步骤 1 从图中任选一点vi 让vi V 图中其余点均包含在中 2 从V与的连线中找出最小边 这条边一定包含在最小部分树中 不妨设这条边为 vi vj 将其加粗 标记为最小部分树中的边 3 令V vj V vj 4 重复2 3两步 一直到图中所有点均包含在V中 2020 4 4 16 避圈法另一种做法 1 在所有各边中找到边权最小的一条 将其作为最小部分树中的第一边 在剩余的边中 仍然找到边权最小的作为最小部分树的第二条边 2 在剩余的边中 找到边权最小的边 查看
9、其是否与前面的边形成圈 如果没有 则在最小部分树中添加该边 如果形成了圈 则不再考虑该边 3 重复进行第二步 直到找到第n 1条边为止 因为有n个顶点的树中一定有n 1条边 2020 4 4 17 例 分别用两种避圈法构造下图的最小部分树 第一种解法 1 在点集中任选一点 不妨取S 令V S 2 找到和S相邻的边中 权值最小的 S A 2020 4 4 18 3 V S A 4 重复第2 3步 找到下一个点 2020 4 4 19 第二种做法求解过程 2020 4 4 20 破圈法求解步骤 1 从图N中任取一回路 去掉这个回路中边权最大的边 得到原图的一个子图N1 2 从剩余的子图中任找一回路
10、 同样去掉回路中边权最大的一条边 得一新的子图 3 重复第2步 直到图中不再含有回路为止 用破圈法求解上例 1 任意找到一回路 不妨取DETD 去掉边权最大的边 T E 2020 4 4 21 2 从剩余的子图中任找一回路 同样去掉回路中边权最大的一条边 得一新的子图 依次类推 2020 4 4 22 破圈法的另一种解法 1 从剩余图中找到边权最大的一条边 如果将其删除后图仍然是连通的 则删除此边 否则不再考虑此边 2 重复上述步骤 直到剩余边数为n 1为止 用此法求解上述问题 2020 4 4 23 注意 1 一个图的最小部分树不唯一 该题中用几种解法得到的结果都是相同的 是特殊情况 2 不
11、同解法得到的最小部分树所包含的边虽然可能不相同 但是 每个最小部分树中所有边权的总和一定都是相同的 即都达到了最小 2020 4 4 24 3 最短路问题 最短路问题是指从给定的网络图中找出任意两点之间距离最短 权值和最小 的一条路 某些整数规划和动态规划问题可以归结为求最短路的问题 如选址问题 管道铺设选线问题 设备更新 投资等问题 最短路的求法 1 从某一点至其它各点之间最短距离的狄克斯屈拉 Dijksrta 算法 2 求网络图中任意两点之间的最短距离的矩阵算法 2020 4 4 25 一 Dijkstra算法 1 设dij表示图中两相邻点i与j的距离 若i与j不相邻 令dij 显然dii
12、 0 Dijkstra算法假设 基本思路 如果v1 v2 v3 v4是v1 v4的最短路径 则v1 v2 v3一定是v1 v3的最短路径 v2 v3 v4一定是v2 v4的最短路径 2 设Lsi表示从s点到i点的最短距离 2020 4 4 26 Dijkstra算法步骤 1 对起始点s 因Lss 0 将0标注在s旁的小方框内 表示s点已标号 2 从点s出发 找出与s相邻的点中距离最小的一个 设为r 将Lsr Lss dsr的值标注在r旁的小方框内 表明点r也已标号 3 从已标号的点出发 找出与这些点相邻的所有未标号点p 若有Lsp min Lss dsp Lsr drp 则对p点标号 并将Ls
13、p的值标注在p点旁的小方框内 4 重复第3步 直到t点得到标号为止 求从起始点s到终止点t的最短路径 2020 4 4 27 例 求下图中从v1到v7的最短路 解 1 从v1点出发 对v1点标号 将L11 0标注在旁的小方框内 令v1 V 其余点属于 2020 4 4 28 L1r min 0 d12 0 d13 min 5 2 2 L13 2 同v1相邻的未标号点有v2 v3 2020 4 4 29 对v3标号 将L13的值标注在v3旁的小方框内 将 v1 v3 加粗 并令V v3 V 2020 4 4 30 L1p min L11 d12 L13 d34 L13 d36 min 0 5 2
14、 7 2 4 5 L12 3 同v1 v3相邻的未标号点有v2 v4 v6 2020 4 4 31 对v2标号 将L12的值标注在v2旁的小方框内 将 v1 v2 加粗 并令V v2 V 2020 4 4 32 L1p min L12 d25 L12 d24 L13 d34 L13 d36 min 5 7 5 2 2 7 2 4 6 L16 4 同v1 v2 v3相邻的未标号点有v4 v5 v6 2020 4 4 33 对v6标号 将L16的值标注在v6旁的小方框内 将 v3 v6 加粗 并令V v6 V 2020 4 4 34 L1p min L12 d25 L12 d24 L13 d34
15、L16 d64 L16 d65 L16 d67 min 5 7 5 2 2 7 6 2 6 1 6 6 7 L14 L15 5 同v1 v2 v3 v6相邻的未标号点有v4 v5 v7 2020 4 4 35 对v4 v5同时标号 将L14 L15的值标注在v4 v5旁的小方框内 将 v2 v4 v6 v5 加粗 并令V v4 v5 V 2020 4 4 36 L1p min L15 d57 L16 d67 min 7 3 6 6 10 L17 6 同v1 v2 v3 v4 v5 v6相邻的未标号点只有v7 2020 4 4 37 对v7标号 将L17的值标注在v7旁的小方框内 将 v5 v7
16、 加粗 图中粗线表明从点v1到网络中其它各点的最短路 各点旁的数字就是点v1到各点的最短距离 2020 4 4 38 二 求任意两点间最短距离的矩阵算法 用Dijkstra算法只能计算从图中某一点到其他点的最短距离 如果要计算各点之间的最短距离就需要对每个点分别计算 而用矩阵算法则可以同时求出所有各点间的最短距离 例 利用矩阵算法求上述网络图中各点间的最短距离 解 设dij表示图中两相邻点i与j的距离 若i与j不相邻 令dij 显然dii 0 建立距离矩阵 2020 4 4 39 2020 4 4 40 从上述距离矩阵可以看出从i点到j点的直接距离 但从i到j的最段距离不一定就是从i点直接到j点 如上述问题中 从v1 v2的最短距离应该是min d11 d12 d12 d22 d13 d32 d14 d42 d15 d52 d16 d62 d17 d72 即min d1r dr2 因此可以构造一个新的矩阵D 1 令D 1 中每一个元素为 dij 1 min dir drj 则矩阵D 1 给出了网络中任意两点之间直接到达及经由一个中间点时的最短距离 2020 4 4 41 再构造矩阵D
