第二章 图论模型

《第二章 图论模型》由会员分享，可在线阅读，更多相关《第二章 图论模型（90页珍藏版）》请在金锄头文库上搜索。

1、 数学建模简明教程 国家精品课程 第二章图论模型 一 问题引入与分析 二 图论的基本概念 三 最短路问题及算法 四 最小生成树及算法 五 旅行售货员问题 六 模型建立与求解 1 98年全国大学生数学建模竞赛B题 最佳灾 今年 1998年 夏天某县遭受水灾 为考察灾情 组织自救 县领导决定 带领有关部门负责人到 全县各乡 镇 村巡视 巡视路线指从县政府 所在地出发 走遍各乡 镇 村 又回到县政 府所在地的路线 情巡视路线 中的前两个问题是这样的 一 问题引入与分析 1 若分三组 路 巡视 试设计总路程最 短且各组尽可能均衡的巡视路线 2 假定巡视人员在各乡 镇 停留时间T 2 小时 在各村停留时

2、间t 1小时 汽车行驶速度V 35公里 小时 要在24小时内完成巡视 至少应分 几组 给出这种分组下最佳的巡视路线 公路边的数字为该路段的公里数 2 问题分析 本题给出了某县的公路网络图 要求的是在不 同的条件下 灾情巡视的最佳分组方案和路线 将每个乡 镇 或村看作一个图的顶点 各乡 镇 村之间的公路看作此图对应顶点间的边 各 次再回到点O 使得总权 路程或时间 最小 条公路的长度 或行驶时间 看作对应边上的权 所给公路网就转化为加权网络图 问题就转化图论 中一类称之为旅行售货员问题 即在给定的加权网 络图中寻找从给定点O出发 行遍所有顶点至少一 如第一问是三个旅行售货员问题 第二问是四 本题

3、是旅行售货员问题的延伸 多旅行售货员问题 本题所求的分组巡视的最佳路线 也就是m条 众所周知 旅行售货员问题属于NP完全问题 显然本问题更应属于NP完全问题 有鉴于此 经过同一点并覆盖所有其他顶点又使边权之和达 到最小的闭链 闭迹 个旅行售货员问题 即求解没有多项式时间算法 一定要针对问题的实际特点寻找简便方法 想找到 解决此类问题的一般方法是不现实的 对于规模较 大的问题可使用近似算法来求得近似最优解 二 图论的基本概念 1 图的概念 2 赋权图与子图 3 图的矩阵表示 4 图的顶点度 5 路和连通 定义一个图G是指一个二元组 V G E G 其中 其中元素称为图G的顶点 组成的集合 即称为

4、边集 其中元素称为边 2 E G 是顶点集V G 中的无序或有序的元素偶对 1 图的概念 定义若一个图的顶点集和边集都是有限集 则称 其为有限图 只有一个顶点的图称为平凡图 其他的 所有图都称为非平凡图 定义若图G中的边均为有序偶对 vi vj 称G为有向 图 称边为有向边或弧 称是从 连接 称为e的尾 称为e的头 若图G中的边均为无序偶对 称G为无向图 称 为e的端点 边为无向边 称e连接和 顶点和称 既有无向边又有有向边的图称为混合图 常用术语 1 边和它的两端点称为互相关联 2 与同一条边关联的两个端点称 为相邻的顶点 与同一个顶点 点关联的两条边称为相邻的边 3 端点重合为一点的边称为

5、环 端点不相同的边称为连杆 4 若一对顶点之间有两条以上的边联结 则这些边 称为重边 5 既没有环也没有重边的图 称为简单图 常用术语 6 任意两顶点都相邻的简单图 称为完全图 记为Kv 7 若 且X中任意两顶点不 相邻 Y中任意两顶点不相邻 则称为二部图或 偶图 若X中每一顶点皆与Y中一切顶点相邻 称 为完全二部图或完全偶图 记为 m X n Y 8 图叫做星 定义若图G V G E G 的每一条边e都赋以 一个实数w e 称w e 为边e的权 G连同边上的权 称为赋权图 定义设和是两个图 1 若 称是的一个子图 记 2 若 则称是的生成子图 3 若 且 以为顶点集 以两端点 均在中的边的全

6、体为边集的图的子图 称 为的由导出的子图 记为 4 若 且 以为边集 以的端点 集为顶点集的图的子图 称为的由导出的 边导出的子图 记为 2 赋权图与子图 3 若 且 以为顶点集 以两端点 均在中的边的全体为边集的图的子图 称 4 若 且 以为边集 以的端点 集为顶点集的图的子图 称为的由导出的 边导出的子图 记为 为的由导出的子图 记为 1 对无向图 其邻接矩阵 其中 3 图的矩阵表示 2 对有向图 其邻接矩阵 其中 其中 3 对有向赋权图 其邻接矩阵 对于无向赋权图的邻接矩阵可类似定义 1 对无向图 其关联矩阵 其中 关联矩阵 2 对有向图 其关联矩阵 其中 定义1 在无向图G中 与顶点v

7、关联的边的数目 环 算两次 称为顶点v的度或次数 记为d v 或dG v 称度为奇数的顶点为奇点 度为偶数的顶点为偶点 2 在有向图中 从顶点v引出的边的数目称为顶点 v的出度 记为d v 从顶点v引入的边的数目称为 v的入度 记为d v 称d v d v d v 为顶点v的 度或次数 定理 的个数为偶数 推论任何图中奇点 4 图的顶点度 定义1 无向图G的一条途径 或通道或链 是指 一个有限非空序列 它的项交替 地为顶点和边 使得对 的端点是和 称W是从到的一条途径 或一条途径 整数k称为W的长 顶点和分别称为起点和终点 而称为W的内部顶点 2 若途径W的边互不相同但顶点可重复 则称W 为迹

8、或简单链 3 若途径W的顶点和边均互不相同 则称W为路 或路径 一条起点为 终点为的路称为 路记为 5 路和连通 定义 1 途径中由相继项构成子序列 称为途径W的节 2 起点与终点重合的途径称为闭途径 3 起点与终点重合的的路称为圈 或回路 长 为k的圈称为k阶圈 记为Ck 4 若在图G中存在 u v 路 则称顶点u和v在图G 中连通 5 若在图G中顶点u和v是连通的 则顶点u和v之 之间的距离d u v 是指图G中最短 u v 路的长 若没 没有路连接u和v 则定义为无穷大 6 图G中任意两点皆连通的图称为连通图 类似地 可定义有向迹 有向路和有向圈 例在右图中 途径或链 迹或简单链 路或路

9、径 圈或回路 三 最短路问题及算法 最短路问题是图论应用的基本问题 很多实际 问题 如线路的布设 运输安排 运输网络最小费 用流等问题 都可通过建立最短路问题模型来求解 最短路的定义 最短路问题的两种方法 Dijkstra和Floyd算法 1 求赋权图中从给定点到其余顶点的最短路 2 求赋权图中任意两点间的最短路 2 在赋权图G中 从顶点u到顶点v的具有最小权 定义1 若H是赋权图G的一个子图 则称H的各 边的权和为H的权 类似地 若 称为路P的权 若P u v 是赋权图G中从u到v的路 称 的路P u v 称为u到v的最短路 3 把赋权图G中一条路的权称为它的长 把 u v 路的最小权称为u

10、和v之间的距离 并记作d u v 1 求赋权图中从给定点到其余顶点的最短路 解决上述问题的一个方法是由Dijkstra于1959 年提出的算法 此算法不仅能求出赋权图指定两点 最短路 目前它是求无负权图最短路的最好方法 间的最短路 而且能求出从指定点到其余各顶点的 中从到的最短路 则必为从到 的最短路 则称是的先驱点 记为 它可用于追踪最短路的路径 最短路是一条路 且最短路的任一节也是最短路 假设G为赋权有向图或无向图 G边上的权均非 负 若 则规定 求下面赋权图G中顶点v0到其余顶点的最短路 输入 图G的带权邻接矩阵W Dijkstra算法 求G中从顶点到其余顶点的最短路 对每个顶点 定义两

11、个标记 l v t v 其中 l v 表示从顶点到的一条路的权 t v 表示的先驱点 它可用以确定最短路的路径 算法的过程就是在每一步改进这两个标记 l v t v 使最终l v 为从顶点v0到v的最短路的权 S 具有永久标号的顶点集 Dijkstra算法步骤 用上述算法求出的l v 就是v0到v的最短路的权 1 初始化操作 置S v0 l v0 0 对每个 令 2 设v 是使l v 取最小值的中的顶点 即 则令 若 停止 否则 转 3 3 更新l v t v 对每个 若l v l u w u v 则令l v l u w u v 转 2 从v的先驱点标记t v 追溯到v0 就得到v0到v的最短

12、 路的路径 1 初始化操作 置S v0 l v0 0 对每个 令 停止 否则 转 3 则令 若 3 更新l v t v 对每个 若l v l u w u v 则令l v l u w u v 转 2 2 设v 是使l v 取最小值的中的顶点 即 2 设v 是使l v 取最小值的中的顶点 即 置S v0 l v0 0 方框把0框起来 给与v0相邻的顶点 分别标以l v1 w v0v1 w01 1 l v2 2 l v4 7 l v6 4 l v7 8 v1 v2 v4 v6 v7 其余顶点均标以 即l v3 l v5 1 初始化操作 置S v0 l v0 0 对每个 令 停止 否则 转 3 则令

13、若 3 更新l v t v 对每个 若l v l u w u v 则l v l u w u v 转 2 2 设v 是使l v 取最小值的中的顶点 即 2 设v 是使l v 取最小值的中的顶点 即 对每个 记t v v0 即它们的 先驱点均为v0 在 中取标号最小者l v1 1 用方框把1框起来 令 1 初始化操作 置S v0 l v0 0 对每个 令 停止 否则 转 3 则令 若 3 更新l v t v 对每个 若l v l u w u v 则l v l u w u v 转 2 2 设v 是使l v 取最小值的中的顶点 即 的算法步骤 3 重新 2 设v 是使l v 取最小值的中的顶点 即 令

14、 用Dijkstra 的标号l v t v 经计 改进顶点 算只有v3满足条件 则给v3标以l v3 4 令t v3 v1 此时其它 点的两个标号l v t v 保持不变 1 初始化操作 置S v0 l v0 0 对每个 令 停止 否则 转 3 则令 若 3 更新l v t v 对每个 若l v l u w u v 则l v l u w u v 转 2 2 设v 是使l v 取最小值的中的顶点 即 2 设v 是使l v 取最小值的中的顶点 即 重复上面的做法 能在改进为止 直到所有顶点的两 个标号l v t v 不 定义根据顶点v的标号l v 的取值途径 使到v 的最短路中与v相邻的前一个顶点

15、w 称为v的先驱 点 记为t v 即t v w 先驱点可用于追踪最短路径 上例的标号过程也 可按如下方式进行 首先写出左图带权邻接矩阵 因G是无向图 故W是对称阵 见VisualC 6 0程序 Dijkstra cpp I 求距离矩阵的方法 II 求路径矩阵的方法 III 查找最短路路径的方法 Floyd算法 求任意两顶点间的最短路 举例说明 2 求赋权图中任意两顶点间的最短路 算法的基本思想 算法的基本思想 直接在图的带权邻接矩阵中用插入顶点的 方法依次构造出v个矩阵D 1 D 2 D v 使最后得到的矩阵D v 成为图的距离矩阵 同时 也求出插入点矩阵以便得到两点间的最短路径 I 求距离矩

16、阵的方法 设赋权图G的顶点集为 1 写出赋权图G的带权邻接矩阵W 把它作为距离 矩阵的初值 即 其中 表示从vi到vj且中间点仅为v1 v2 vk的k个点的 所有路径中的最短路的长度 于是中元素就是从到的 路径中间可插入任何顶点的路径中最短路的长度 即就是所求距离矩阵 在建立距离矩阵的同时可建立路径矩阵R II 求路径矩阵的方法 设 这里的含义是从到 的最短路要经过点号为的点 算法开始于 迭代到第k步 即由到迭代 若某个元素改变 变小 则由到迭代中 相应元素改为k 表示到第 k次迭代 从到的最短路过点比过原中间点更短 在求得时求得 可由来查找任何点对 之间最短路的路径 然后用同样的方法再分头查找 若 III 查找最短路路径的方法 IV Floyd算法 求任意两顶点间的最短路 d i j i到j的距离 r i j i到j之间的插入点 输入 带权邻接矩阵 1 赋初值 对所有i j d i j w i j r i j j k1 2 更新d i j r i j 对所有i j 若d i k d k j d i j 则d i j d i k d k j r i j k 3 若k v 停止 否则kk