第九章_图与网路分析(黑白)

第九章图与网络分析 图是最直观的模型 第一节图论基础 一 图及其相关概念 引例 1 哥尼斯堡七桥问题 问 从岸上某点出发 能否恰好经过每座桥一次又回到出发点 如果可以 路线如何 引例 2 铁路运输网络图 图G区别于几何学中的图 在几何学中 图中点的位置 线的长度和斜率都十分重要 而这里只关心图中有多少个点以及哪些点之间有线相连 由一个表示研究对象事物的 点的集合 V 和一个表示事物之间关联关系的 线的集合 E 组成的点线图G V E 图的概念 如果给图中的点和边赋以具体的含义和权数 如距离 费用 容量等 把这样的图称为网络图 记作N 图2 对研究的问题确定具体对象及这些对象间的性质联系 并用图的形式表示出来 这就是对研究的问题建立图的模型 用建立图的模型的办法往往能帮助我们解决一些用其他方法难于解决的问题 二 图模型的建立 例1有甲 乙 丙 丁 戊 己六名运动员报名参加A B C D E F六个项目的比赛 表中打 的是各运动员报名参加的比赛项目 问六个项目的比赛顺序应如何安排 做到每名运动员都不连续参加两项比赛 解 把比赛项目作为研究对象 用点表示 如果两个项目有同一名运动员参加 在代表这两个项目的点之间连一条线 得图10 4 在该图中只要找到一个点的序列 使依次排列的两个点不相邻 即能做到每名运动员不连续参加两项比赛 从图中看到 满足上述要求的点的序列很多 例如 A C B F E D就是其中之一 课堂练习 要求A或H做首尾 任何一个人不连续参加两个节目 A F B C G D E HA F G C B D E H 端点 关联边 相邻若有边e可表示为是边e的端点 反之称边e为点的关联边 若与同一条边关联 称点相邻 若边具有公共的端点 称边相邻 环 多重边 简单图如果边e的两个端点相重则称该边为环 如图2中的e1为环 如果两个点之间多于一条 称为具有多重边 如图2中的e4和e5 对无环 无多重边的图称作简单图 三 图的基本概念 次 奇点 偶点 孤立点与某一个点vi相关联的边的数目称为点vi的次 也叫做度 记作d vi 图2中d v1 4 d v3 5 d v5 1 次为奇数的点称为奇点 次数为偶数的点称为偶点 次数为0的点称为孤立点 次数为1的点称为悬挂点 pendantvertex 注 图中可以只有点 而没有边 而有边必有点 基本定理 1 图G V E 中 所有顶点次数之和为边数的2倍 2 任意图G中 奇点的个数为偶数 链 圈 路 回路 连通图图中有些点和边的交替序列若其中各边互不相同 且对任意 2 t k 均相邻 称 为链 如果链中所有的顶点也不相同 这样的链称为路 图2中是一条链 也是一条链 但 2可以称作路 1中因顶点v3重复出现 不能称作路 对起点与终点重合的链称作圈 起点与终点重合的路称作回路 若在一个图中 如果每一对顶点之间至少存在一条链 称这样的图为连通图 否则该图是不连通的 连通图中不存在孤立的点 如果图中两点之间的联线无方向之别 称之为边 相应的图称为无向图 记为G V E 四 图的类型 1 无向图 V v1 vn E e1 em e u v v u 如果图中两点之间的联线有方向之别 称之为弧 一般用箭头表示方向 由点及弧组成的图称为有向图 记为D V A 2 有向图 V v1 vn A a1 am a u v v u 3 同构图 如果图G V E 和图G V E 的顶点集合V和边的集合E一一对应 则G和G 称为同构图 4 完全图一个简单图中若任意两点之间均有边相连 称这样的图为完全图 含有n个顶点的完全图 其边数有条 5 偶图 如果图的顶点能分成两个互不相交的非空集合V1和V2 使在同一集合中任意两个顶点均不相邻 称这样的图为偶图 二部图 如果偶图的顶点V1 V2之间的每一对不同顶点都有一条边相连 称这样的图为完全偶图 完全偶图中V1含m个顶点 V2含n个顶点 则其边数共m n条 6 子图 部分图 图G1 V1 E1 和图G2 V2 E2 如果有 称G1是G2的一个子图 若有 则称G1是G2的一个部分图 图3 a 是图2的一个子图 图3 b 是图2的部分图 注意部分图也是子图 但子图不一定是部分图 一 欧拉链 若Q为连通无向图G的一条链 G中每条边在Q中恰出现一次 则称Q为图G的一条欧拉链 二 欧拉圈 若C为连通无向图G的一条路 G中每条边在路C中恰出现一次 则称C为图G的一条欧拉圈 欧拉环游 三 欧拉图 若连通无向图G中含有一条欧拉圈 欧拉环游 则称图G为欧拉图 四 非欧拉图 若连通无向图G中不存在一条欧拉圈 欧拉环游 则称图G为非欧拉图 B A 7 欧拉图 1 连通无向图G为欧拉图 当且仅当G中无奇点 2 连通无向图G含有欧拉链 当且仅当G中恰有2个奇点 分别为欧拉链的起终点 基本定理 反映了连通无向图G的一笔画性质 基本推论 若连通无向图G能够一笔画出 则当且仅当 1 连通无向图G为欧拉图 无奇点 含有多条欧拉圈 欧拉环游 2 连通无向图G虽非欧拉图 但G中恰有2个奇点 含有一条以2个奇点为起终点的欧拉链 一个无圈的无向连通图G称为树 记为T V E 给定连通图G 若树T满足V T V G E T E G 则称T为图G的生成树 生成树是能把原图上顶点以最小边数连接起来的树 在同一个图中由于边的取法不同可以有很多生成树 8 树图和生成树 补充 关联矩阵和邻接矩阵 图可用集合来定义 也可用图形来表达 还可以用矩阵来表示 一 无向图的关联矩阵给无向图G V E V v1 v2 vn E e1 e2 em 用矩阵的行标号i表示图G的顶点下标 用列标号j表示图G的边的下标 可构造n m矩阵 其中 例 试作出无向图的关联矩阵 二 无向图的邻接矩阵给无向图G V E V v1 v2 vn E e1 e2 em 用矩阵的行标号i和列标号j都表示图G顶点 可构造n n矩阵 其中bij 连接顶点vi和vj的边的数目 有向图D的关联矩阵M D 为 e1e2e3e4e5 v1v2v3v4 三 有向图的关联矩阵给有向图G V E V v1 v2 vn E e1 e2 em 用矩阵的行标号i表示图G的顶点下标 用列标号j表示图G的边的下标 可构造n m矩阵 其中 四 有向图的邻接矩阵给有向图G V E V v1 v2 vn E e1 e2 em 用矩阵的行标号i和列标号j都表示图G顶点 可构造n n矩阵 其中bij 以顶点vi为起点和vj为终点的边的数目 下面有向图D的邻接矩阵为 v1v2v3v4 v1v2v3v4 课堂练习 1 作出如下各图的关联矩阵和邻接矩阵 2 若图G的关联矩阵如下 作出几何图G 3 若有向图G的邻接矩阵如下 作出几何图 第二节树图和图的最小部分树 一 树的定义及其性质 一 树的概念1 树 无回路且连通的无向图 记为 T 2 生成树 若T V E 是无向图G V E 的生成子图 且T V E 是一个树 则称T是G的生成树 二 树的基本性质 圈 二 最小生成树问题 1 概念 2 定理 3 避圈法和破圈法 根据上述定理及推论 用避圈法在给定的图中寻找最小部分树的步骤是 从图中任选一点 让vi V 图中其余点均包含在中V 从V和 的连线中找出最小边 这条边一定包含在最小部分树内 不妨设最小边为 vi vj 将 vi vj 加粗 以标记最小树内的边 令重复2 3步 一直到图中所有点均包含在V中为止 用避圈法时 先从图10 7中任选一点 设为S 令 V与间的最短边为 S A 将该边加粗 标志它是最小树内的边 再令重复上述步骤 一直到所有点连通为止 例2 如图所示 S A B C D E T代表村镇 它们间连线表明各村镇间现有道路交通情况 连线旁数字代表道路的长度 现要求沿图中道路架设电线 使上述村镇全部用上电 问应如何架设使总的线路长度为最短 破圈法 从网络图N中任取一回路 去掉这个回路中权数最大的一条边 得一子网络图N1 在N1中再任取一回路 再去掉回路中权数最大的一条边 得N2 如此继续下去 一直到剩下的子图中不再含回路止 该子图就是N的最小部分树 用破圈法求例2的解时 从图中任取一回路 如为DETD 去掉最大边 得N1 从N1中再任取一回路 如为BDEB 去掉最大边BD 得N2 从N2中再任取一回路 如为ABEDA 去掉最大边AD 得N3 依次类推 从N3的EBCE回路中去掉CE 从N4的SABS回路中去掉SB 从N5的SABCS回路中去掉SC得N6 N6即为所求的最小部分树 例 有一项工程 要填埋电缆将中央控制室与15个控制点连通 下图中各线段标出了允许挖电缆沟的地点和距离 单位 100米 若电缆线每米10元 电缆沟 深1米 宽0 6米 土方3元 m3 其他材料和施工费5元 米 请做工程预算 最少需要多少钱 6200 10 0 6 3 5 104160 元 最短路问题 一般来说就是从给定的网络图中找出任意两点之间距离最短的一条路 这里说的距离说的只是权数的代称 在实际的网络中 权数可以是时间 费用等 有些问题 如选址 管道铺设时的选线 设备更新 投资 某些整数规划和动态规划的问题 也可以归结为求最短路的问题 因此这类问题在生产实际中得到广泛应用 求最短路有两种算法 一是求从某一点到其它各点之间最短距离的狄克斯屈拉 Dijkstra 另一种是求网络图上任意两点之间最短距离的矩阵算法 第三节最短路问题 一 Dijkstra算法 这种算法的基本思路是 假定是的最短路 见上图 则一定是的最短路 是的最短路 否则 设之间的最短路为 就有的路必小于 这与原假设相矛盾 计算两节点之间或一个节点到所有节点之间的最短路令dij表示vi到vj的直接距离 两点之间有边 若两点之间没有边 则令dij 若两点之间是有向边 则dji 令dii 0 s表示始点 t表示终点 把所有顶点分成两个集合 和 为便于计算和区分个顶点是否已进入集合 给已求出到起点最短路的点 k赋以标号 标号有两部分组成 记为 d vs vk vi 其中vi表示vk到起点最短路的前点 d vs vk 表示从起点到vk的最短路长 双标号法 计算步骤 从点S出发 因Lss 0 令始点 s赋号为表示S点已标号 从S点出发 找出与S相邻的点中距离最小的一个设为r 计算 并对点r赋号 从已标号的点出发 找出与这些点相邻的所有未标号点p 计算重复上一步骤 当t 时计算结束 例2 见下图 求该图中从的最短路 解 用Dijkstra算法的步骤如下 解 1 从点V1出发 将L11 0 先给起点 赋号为 此时 2 同V1相邻的未标号点有V2 V3 L1p min 0 d12 0 d13 min 5 2 2 L13 即对点V3标号 2 v1 S V1 V3 3 与V1 V3相邻的未标号点有V2 V4 V6 计算L1p min L11 d12 L13 d34 L13 d36 min 0 5 2 7 2 4 5 L12 对点V2标号 5 v1 S V1 V2 V3 4 同标号点V1 V2 V3相邻的点有V5 V4 V6 有L1p min L12 d25 L12 d24 L13 d34 L13 d36 min 5 7 5 2 2 7 2 4 6 L16 对点V6标号 6 v3 S V1 V2 V3 V6 5 同标号点V1 V2 V3 V6相邻的点有V4 V5 V7 有L1p min L12 d25 L12 d24 L13 d34 L16 d64 L16 d65 L16 d67 min 5 7 5 2 2 7 6 2 6 1 6 6 7 L14 L15 故对点V4 V5同时标号为 V4 7 V2 V5 7 V6 S V1 V2 V3 V5 V6 6 同各标号点相邻的未标号点只有V7 因有L17 min L15 d57 L16 d67 min 7 3 6 6 10 故对点V7标号为 V7 10 V5 S V1 V2 V3 V5 V6 V7 课堂练习 用双标号法求解s点到t点的最短距离 0 课堂练习结果 第四节中国邮递员问题 参考教材 运筹学教材组编 一 问题及其目标 一 问题的提出一个邮递员每次送信 必须从邮局出发 至少一次地走过他所负责的投递范围内的每一条街道 待完成任务后仍回到邮局 问 邮递员如何选择一条投递路线 可以使其所走的路程最短 若邮递员负责管辖的街道图 视为非负赋权连通无向图G 边e的权W e 0表示街道的长度 则问题的目标如下 在无向图G中寻找一条闭链C W C Min W C C为包含图G中全部边的闭链 二 问题的目标 二 欧拉图及其最佳邮递员投递路线 若邮递员负责管辖的街道图无奇点 则为欧拉图 相应的欧拉圈 欧拉环游 即为最短邮递路线 按照欧拉圈 他可以从邮局出发 经过每条街道一次 且仅经过一次 又回到邮局 三 非欧拉图及其最佳邮递员投递路线 一般情况下 若邮递员负责管辖的街道图存在偶数个 2 4 6 8 奇点 为非欧拉图 此时 任意一条以邮局为起终点的包含图G全部边的回路中 必然有部分图G的边一次或多次重复出现 即邮递员完成投递任务必须在某些街道重复走一次或多次 显然总投递路程的长度取决于重复走的街道的长度 问题目标转化为寻求重复边长度最小的欧拉圈 一 相关基本概念及优化问题的转换 1 重复边 设Q为任意一条包含图G全部边的欧拉圈 其中部分图G的边e u v 一次或多次重复出现 则称e为重复边 2 欧拉图GQ 若边e在Q中出现k 1次 则在图G中添家k条边e u v W e W