图与网络分析1.doc

图与网络分析 1图的基本概念 2树 3最短路 4最大流问题 5最小费用最大流 6中国邮递员问题 图与网络分析 问题提出 应用生产组织邮递员问题通讯网络等 哥尼斯堡七桥问题 1图的基本概念 例 1 铁路交通图 例 2 球队比赛图 点 表示研究对象 连线表示两个对象之间的某种特定关系 关系的对称性两对象之间的关系可互换 边不带箭头的联线表示对称关系 弧带箭头的联线表示不对称关系 无向图简称图有点和边组成 表示为 G VE V-点集合 E-边集合 例右图 有向图由点和弧组成表示为 D VA V-点集合 A-弧集合 点数 p G 或 p D 边数 q G 弧数q D 无向图的有关概念 端点 e uvE 则uv是e的端点 称uv相邻 关联边 e是点uv的关联边 环 若u v e是环 多重边 两点之间多于一条边 简单图 无环无多重边的图 多重图 无环允许有多重边的图 次 以点v为端点的边的个数称为v的次 表示为 d v 悬挂点 次为1的点 悬挂边 悬挂点的关联边 孤立点 次为0的点 奇点 次为奇数的点 偶点 次为偶数的点 定理2 任意一图中 奇点的个数为偶数 证明设 V1-奇点的集合 V2-偶点的集合 链点边交错系列 记为 圈 的链 初等链点 均不相同 初等圈点 均不相同 简单链链中边均不相同 简单圈圈中边均不相同 例右图 连通图任意两点之间至少有一条链 不连通图 连通分图对不连通图每一连通的部分称为一个连通分图 支撑子图对G VE若G VE 使V V E E 则G是G的一个支撑子图生成子图 G-v 图G去掉点v及v的关联边的图 有向图的有关概念 基础图 对D V A 去掉图上的箭头 始点和终点 对弧a uv u为a的始点 v为a的终点 链 点弧交错序列 若在其基础图中对应一条链 则称为 D的一条链 圈 初等链初等圈 类似定义 道路若 是D中的一条链且 t 12k-1称之为从 到 的一条道路 回路 的路 初等路 道路中点不相同 初等回路 回路中点不相同 简单有向图 无自环 无多重弧 多重有向图 有多重弧 2 树 21 树及其性质 22 图的支撑树生成树 23最小支撑树问题 24 根树及其应用 21 树及其性质 例 电话线架设比赛程序组织结构等 树连通的无圈的无向图称为树 树的性质 图G VEp个点q条边下列说法是等价的 1G是一个树 2G连通且恰有p-1条边 3G无圈且恰有p-1条边 4G连通但每舍去一边就不连通 5G无圈但每增加一边即得唯一一个圈 6G中任意两点之间恰有一条链 简单链 22 图的支撑树生成树 定义设图T VE 是图G VE 的支撑子图如果T是一个树 则称T是G的一个支撑树 定理5图G VE有支撑树的充分必要条件是G是连通的 找图中生成树的方法 求支撑树的破圈法 找图中生成树的方法 求支撑树的避圈法 23最小支撑树问题 赋权图 网络 给图G VE 对G中的每一条边vivj 相应地有一个数wij 则称这样的图为赋权图 wij 称为边vivj上的权 支撑树的权若T VE 是G的一个支撑树 E中的所有边的权之和称为支撑树的权 记为w T 定义 最小支撑树 最小树 T 求最小树的 避圈法 例 图8-27 求最小树的 破圈法 例 图8-28 24 根树及其应用 有向树中根树 在计算机科学决策论的应用 带权的二叉树T有s个叶子权分别为pi 根到各叶子的距离层次为 二叉树的总权数 3 最短路问题 31 引例 单行线交通网v1到v8使总费用最小的旅行路线 最短路问题的一般描述 对D VA a vivjwa wijP是vs到vt的路定义路P的权是P中所有弧的权的和记为wP 路P0的权称为从vs到vt的距离记为 d vsvt 32最短路算法 Dijkstra算法 有向图 wij0 一般结论 Dijkstra算法基本思想 P标号已确定出最短路的节点 T标号为确定出最短路的节点但表示其距离的上限 SiP标号节点的集合 v 最短路中前一个节点的编号 初始值 例 总结 算法步骤 Dijkstra算法 无向图求最短链wij0 存在负权时求最短路问题 4网络最大流问题 41基本概念和基本定理 网络与流 定义 对有向图D VA vs -始点 vt - 终点 其余 - 中间点 c vivj - 弧 vivj 的容量 简写为cij D VAC - 网络 fij - 弧 vivj 上的流量 可行流与最大流 可行流满足 最大流问题 增广链 几个概念 对可行流 例图10-23 增广链 设f是一可行流 时从始点到终点的一条链 若满足下列条件称其为一条增广链 例 图10-24 截集和截量 设 把始点在S终点在T中的所有弧构成的集合 记为 ST 定义 截集 定义 截量 几点结论 42求最大流的标号法 网络中的点分为 标号点 标号未检查点 标号已检查点 未标号点 1 标号过程 2 调整过程 沿增广链调整流量 例 图10-25 5最小费用最大流 定义 对D VAC 给定一个单位流量的费用bij0 最小费用最大流即求一最大流f 使 对增广链 若调整流量 1 那么新可行流f的费用比原可行流f的费用增加 此为增广链的费用 最小费用最大流的求解 构造赋权有向图w f 定义 在w f 中找最小费用增广链 直至没有最小费用增广链为止 若存在最小费用增广链 调整流量如下 6中国邮递员问题 61一笔划问题 欧拉链 图中存在一条链 过每边一次且仅一次 欧拉圈 图中存在一简单圈 过每边一次 欧拉图 具有欧拉圈的图 定理 连通多重图G是欧拉图 当且仅当G中无奇点 推论 连通多重图G有欧拉链 当且仅当G恰有两个奇点 奇偶点作业法 若图中无奇点 问题已解决 否则 第一可行方案的确定 奇点配对 找奇点间的一条链 调整可行方案 使重复边总长度下降 a 最优方案中 每一边上最多有一条重复边 b 最优方案中 每个圈上重复边的总权不大于圈总权的一半 最优性判定 满足a 和b 两条 求最小费用最大流算法 40 1 5 2 0 15 2 5 6 0 40 在最短 路上增 加流量 V1 V2 V3 Vs Vt 求最小费用最大流算法 40 2 0 6 0 40 在最短 路上增 加流量 原流量 如图所 示 V1 V2 V3 Vs Vt 1 0 1 0 2 0 求最小费用最大流算法 40 2 0 6 0 40 求 增 加 的 流 量 V1 V2 V3 Vs Vt 8 - 0 5 - 0 7 - 0 最小 f 0 1 0 1 0 2 0 求最小费用最大流算法 40 1 5 2 0 15 2 5 6 0 40 在最短 路上增 加流量 5 得到新 的流量 f 1 5 V1 V2 V3 Vs Vt 求最小费用最大流算法 40 1 5 2 0 15 2 5 6 0 40 依据新 的流量 构造又 一赋权 图 W f 1 只对增广链 V1 V2 V3 Vs Vt 8 求最小费用最大流算法 40 2 0 15 2 5 6 0 40 赋 权 图 W f 1 的构造 只对增广链 V1 V2 V3 Vs Vt 8 -1 5 1 5 求最小费用最大流算法 40 2 0 15 2 5 6 0 40 赋 权 图 W f 1 的构造 只对增广链 V1 V2 V3 Vs Vt 8 5 -1 5 1 5 求最小费用最大流算法 40 2 0 15 6 0 40 赋 权 图 W f 1 的构造 只对增广链 V1 V2 V3 Vs Vt 8 5 -2 5 7 -15 -1 5 1 5 求最小费用最大流算法 40 2 0 15 6 0 40 构造的 赋权 图 W f 1 只对增广链 V1 V2 V3 Vs Vt -2 5 -15 -1 5 1 5 求最小费用最大流算法 40 2 0 15 6 0 40 在赋 权图 W f 1 上求出 最短路 V1 V2 V3 Vs Vt -2 5 -15 -1 5 1 5 求最小费用最大流算法 Vs 40 1 5 2 0 15 2 5 6 0 40 在最短 路上增 加流量 V1 V2 V3 Vs Vt 7 - 5 2 10 - 0 最小 求最小费用最大流算法 Vs 42 1 5 2 0 17 2 5 6 0 40 2 得到新 的流量 f 2 7 新的流 量图如 图所示 V1 V2 V3 Vs Vt 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W f 2 只对增广链 V1 40 1 5 2 0 15 6 0 40 V1 V2 V3 Vs Vt -1 5 -2 5 -15 求最小费用最大流算法 对最短 路上求 新的权 值 V1 42 1 5 2 0 17 6 0 40 V1 V2 V3 Vs Vt -1 5 -2 5 10 求最小费用最大流算法 赋 权 图 的构造 W f 2 只对增广链 V1 42 1 5 2 0 17 6 0 40 V1 V2 V3 Vs Vt -1 5 -2 5 -42 求最小费用最大流算法 赋 权 图 的构造 W f 2 只对增广链 V1 42 -1 5 2 0 17 6 0 40 V1 V2 V3 Vs Vt 1 5 -2 5 7 -42 求最小费用最大流算法 赋 权 图 的构造 W f 2 只对增广链 V1 42 2 0 -17 6 0 40 V1 V2 V3 Vs Vt -2 5 -42 -1 5 1 5 求最小费用最大流算法 新 赋 权 图 W f 2 只对增广链 V1 42 2 0 -17 6 0 40 V1 V2 V3 Vs Vt -2 5 -42 -1 5 1 5 求最小费用最大流算法 在赋 权图 W f 2 上求出 最短路 V1 42 2 0 -17 6 0 40 V1 V2 V3 Vs Vt -2 5 -42 -1 5 1 5 求最小费用最大流算法 42 1 5 2 0 17 2 5 6 0 40 在最短 路上增 加流量 3 V1 V2 V3 Vt 8 - 5 3 最小 10 - 0 4 - 0 求最小费用最大流算法 42 1 8 2 3 17 2 5 6 0 43 在最短 路上增 加流量 3 得到新 的流量 f 3 10 V1 V2 V3 Vt 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W f 3 只对增广链 V1 42 2 3 -17 6 0 43 V1 V2 V3 Vs Vt -2 5 -15 -42 1 8 8 10 4 求最小费用最大流算法 赋 权 图 W f 3 的构造 只对增广链 V1 42 2 3 -17 6 0 43 V1 V2 V3 Vs Vt -2 5 -15 -42 -1 8 -43 -2 3 求最小费用最大流算法 在赋权 图 W f 3 上求出 最短路 V1 42 2 3 -17 6 0 43 V1 V2 V3 Vs Vt -2 5 -15 -42 -1 8 -43 -2 3 求最小费用最大流算法 在初始 赋权图 W f 0 上求出 最短路 V1 42 2 3 -17 6 0 43 V1 V2 V3 Vs Vt -2 5 -15 -42 -1 8 -43 -2 3 求最小费用最大流算法 42 1 8 2 3 17 2 5 6 0 43 在最短 路上增 加流量 V1 V2 V3 Vt 5 最小 10 - 3 4 - 3 1 10 - 2 求最小费用最大流算法 43 1 8 2 4 17 2 4 6 0 44 在最短 路上增 加流量 1 得新的 流量 f 4 11 V1 V2 V3 Vt 求最小费用最大流算法 43 1 8 2 4 17 2 4 6 0 44 注意 在负向 弧上减 去增量 值 V1 V2 V3 Vt 5 - 1 求最小费用最大流算法 上一次 的赋权 图 依据新 流量在最 短路径上 对此重求 赋权值 V1 42 2 3 -17 6 0 43 V1 V2 V3 Vs Vt -2 5 -42 -1 8 -43 -2 3 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W f 4 只对增广链 V1 43 2 4 -17 6 0 44 V1 V2 V3 Vs Vt 2 4 1 8 10 5 10 4 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W f 4 只对增广链 V1 43 -2 4 -17 6 0 34 V1 V2 V3 Vs Vt -2 4 -43 -1 8 -34 2 4 求最小费用最大流算法 没有最短路算法结束所得为最小费用最大流 V1 43 -2 4 -17 6 0 34 V1 V2 V3 Vs Vt -2 4 -43 -1 8 -34 2 4 只有出弧 流入量 流出量 流入量 流出量 可增加流量的链 求最小费用最大流算法 初 始 网 络 数 值 Vs V1 V2 V3 Vt 求最小费用最大流算法 410 1 8 2 4 1 7 2 5 6 2 410 bij Cij 初 始 网 络 数 值 Vs V1 V2 V3 Vt 求最小费用最大流算法 取初始 可行流 f 0 0 V1 V2 V3 Vs Vt 求最小费用最大流算法 40 1 0 2 0 1 0 2 0 6 0 40 取初始 可行流 f 0 0 V1 V2 V3 Vs Vt bij fij 求最小费用最大流算法 40 1 0 2 0 1 0 2 0 6 0 40 取初始 可行流 f 0 0 构造赋 权图 W f 0 V1 V2 V3 Vs Vt 求最小费用最大流算法 40 1 0 2 0 1 0 2 0 6 0 40 取初始 可行流 f 0 0 构造赋 权图 W f 0 V1 V2 V3 Vs Vt 求最小费用最大流算法 40 1 0 2 0 1 0 2 0 6 0 40 取初始 可行流 f 0 0 构造赋 权图 W f 0 0 V1 V2 V3 Vs Vt 求最小费用最大流算法 40 1 0 2 0 1 0 2 0 6 0 40 在初始 赋权图 W f 0 上求出 最短路 V1 V2 V3 Vs Vt 运筹学 A B C D 哥尼斯堡七桥问题 在图中找一条经过每边一次且仅一次的路欧拉回路 A D B C 由点和边组成 环球旅行问题 在图中找一条经过每个点一次且仅一次的路哈密尔顿回路 中国邮路问题 在图中找一条经过每边的最短路类似带权的欧拉回路 货郎担问题 在图中找一条经过每个点一次且