运筹学图与网络分析.ppt

图与网络分析 GraphTheoryandNetworkAnalysis 图与网络的基本知识 最短路问题 树及最小树问题 最大流问题 哥尼斯堡七桥问题 哥尼斯堡 现名加里宁格勒 是欧洲一个城市 Pregei河把该城分成两部分 河中有两个小岛 十八世纪时 河两边及小岛之间共有七座桥 当时人们提出这样的问题 有没有办法从某处 如A 出发 经过各桥一次且仅一次最后回到原地呢 哥尼斯堡七空桥 一笔画问题 哈密尔顿 Hamilton 回路是十九世纪英国数学家哈密顿提出 给出一个正12面体图形 共有20个顶点表示20个城市 要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次 最后回到原处的周游世界线路 并不要求经过每条边 有7个人围桌而坐 如果要求每次相邻的人都与以前完全不同 试问不同的就座方案共有多少种 用顶点表示人 用边表示两者相邻 因为最初任何两个人都允许相邻 所以任何两点都可以有边相连 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 得到第一次就座方案是 1 2 3 4 5 6 7 1 继续寻求第二次就座方案时就不允许这些顶点之间继续相邻 因此需要从图中删去这些边 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 得出第二次就座方案是 1 3 5 7 2 4 6 1 那么第三次就座方案就不允许这些顶点之间继续相邻 只能从图中删去这些边 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 得到第三次就座方案是 1 4 7 3 6 2 5 1 那么第四次就座方案就不允许这些顶点之间继续相邻 只能从图中删去这些边 只留下7点孤立点 所以该问题只有三个就座方案 1 2 3 7 6 4 5 引论图的用处 某公司的组织机构设置图 总公司 分公司 工厂或办事处 一 图与网络的基本知识 一 图与网络的基本概念 1 一个图是由点和连线组成 连线可带箭头 也可不带 前者叫弧 后者叫边 例 图1 2 不带箭头的连线叫做边 如果一个图是由点和边所构成的 则称其为无向图 记作G V E 连接点的边记作 vi vj 或者 vj vi 3 若点与点之间的连线有方向 称为弧 如果一个图是由点和弧所构成的 那么称它为有向图 记作D V A 其中V表示有向图D的点集合 A表示有向图D的弧集合 一条方向从vi指向vj的弧 记作 vi vj 图2 4 一条边的两个端点是相同的 那么称这条边是环 5 如果两个端点之间有两条以上的边 那么称它们为多重边 6 不含环和多重边的图称为简单图 有多重边的图称为多重图 7 每一对顶点间都有边相连的无向简单图称为完全图 有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图 次为零的点称为弧立点 次为1的点称为悬挂点 悬挂点的关联边称为悬挂边 次为奇数的点称为奇点 次为偶数的点称为偶点 8 以点v为端点的边的个数称为点v的次 记作 图中d v1 4 d v6 4 环计两次 定理1所有顶点次数之和等于所有边数的2倍 定理2在任一图中 奇点的个数必为偶数 所有顶点的入次之和等于所有顶点的出次之和 有向图中 以vi为始点的边数称为点vi的出次 用表示 以vi为终点的边数称为点vi的入次 用表示 vi点的出次和入次之和就是该点的次 9 设G V E G V E 如果V V E E 称G 是G的子图 如果V V E E 称G 是G的生成子图或支撑子图 在实际应用中 给定图中每条边 对应一个数 称之为 权 通常把这种赋权的图称为网络 10 由两两相邻的点及其相关联的边构成的点边序列称为链 如 v0 e1 v1 e2 v2 e3 v3 vn 1 en vn 11 图中任意两点之间均至少有一条链相连 则称此图为连通图 其链长为n 其中v0 vn分别称为链的起点和终点 所含的点 边均不相同的链称为初等链 起点和终点是同一个点的链称为圈 二 图的矩阵表示对于网络 赋权图 G V E 其中边有权 构造矩阵 其中 称矩阵A为网络G的权矩阵 设图G V E 中顶点的个数为n 构造一个矩阵 其中 称矩阵A为网络G的邻接矩阵 例 权矩阵为 邻接矩阵为 二 树及最小树问题已知有六个城市 它们之间要架设电话线 要求任意两个城市均可以互相通话 并且电话线的总长度最短 1 一个连通的无圈的无向图叫做树 树中次为1的点称为树叶 次大于1的点称为分支点 树的性质 1 数必连通 但无回路 圈 2 n个顶点的树必有n 1条边 3 树中任意两个顶点之间 恰有且仅有一条链 初等链 4 树连通 但去掉任一条边 必变为不连通 5 树无回路 圈 但不相邻的两个点之间加一条边 恰得到一个回路 圈 2 若图G V E 的生成子图是一个树 那么称该树是G的一个生成树 支撑树 或简称为图G的树 图G中属于生成树的边称为树枝 不在生成树中的边称为弦 一个图G有生成树的充要条件是G是连通图 一 破圈法 在图中任选一个圈 从这个圈中去掉一条边 在余下的图中重复这个步骤 直到得到一不含圈的图为止 用破圈法求出下图的一个生成树 二 避圈法 开始选一条边 以后每一步中 总从未被选取的边中选出一条与已选边不构成圈的边 重复这个过程 直到不能进行为止 根据破圈法和避圈法两种方式得到了图的两个不同的生成树 由此可以看到连通图的生成树不是唯一的 3 最小生成树问题 一棵生成树所有树枝上权的总和为这个生成树的权 具有最小权的生成树 称为最小生成树 求赋权图G的最小支撑树的方法也有两种 破圈法 和 避圈法 破圈法 在原图中 任选一个圈 从圈中去掉权最大的一条边 在余下的图中重复这个步骤 直到得到一不含圈的图为止 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 17 4 1 23 总造价 1 4 9 3 17 23 57 v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 避圈法 开始选一条权最小的边 以后每一步中 总从未被选取的边中选一条权尽可能小 且与已选边不构成圈的边 某六个城市之间的道路网如图所示 要求沿着已知长度的道路联结六个城市的电话线网 使电话线的总长度最短 最短路的一般提法为 设为连通图 图中各边有权 表示之间没有边 为图中任意两点 求一条路 使它从到的所有路中总权最短 即 最小 一 狄克斯彻 Dijkstra 算法适用于wij 0 给出了从vs到任意一个点vj的最短路 三 最短路问题 算法步骤 1 给始点vs以P标号 这表示从vs到vs的最短距离为0 其余节点均给T标号 2 设节点vi为刚得到P标号的点 考虑点vj 其中 且vj为T标号 对vj的T标号进行如下修改 3 比较所有具有T标号的节点 把最小者改为P标号 即 当存在两个以上最小者时 可同时改为P标号 若全部节点均为P标号则停止 否则用代替vi 返回步骤 2 例一 用Dijkstra算法求下图从v1到v6的最短路 解 1 首先给v1以P标号 给其余所有点T标号 2 3 4 5 6 7 8 9 10 反向追踪得v1到v6的最短路为 二 逐次逼近法首先设任一点vi到任一点vj都有一条弧 显然 从v1到vj的最短路是从v1出发 沿着这条路到某个点vi再沿弧 vi vj 到vj 则v1到vi的这条路必然也是v1到vi的所有路中的最短路 设P1j表示从v1到vj的最短路长 P1i表示从v1到vi的最短路长 则有下列方程 开始时 令即用v1到vj的直接距离做初始解 从第二步起 使用递推公式 求 当进行到第t步 若出现则停止计算 即为v1到各点的最短路长 例二 6 6 0 5 3 v8 5 5 5 0 1 v7 1 1 1 7 1 0 1 v6 3 3 1 0 1 v5 7 7 7 3 2 0 8 v4 2 2 2 2 1 5 0 3 v3 5 5 5 1 2 0 6 v2 0 0 0 0 3 2 1 0 v1 P 4 P 3 P 2 P 1 v8 v7 v6 v5 v4 v3 v2 v1 求图中v1到各点的最短路 1 8 v1 v2 v3 v4 v5 2 6 3 5 1 3 5 2 1 1 2 1 1 v6 v7 v8 3 7 0 0 v3 5 v1 2 v3 7 v2 3 v4 5 v3 1 v6 6 例 求 5年内 哪些年初购置新设备 使5年内的总费用最小 解 1 分析 可行的购置方案 更新计划 是很多的 如 1 每年购置一台新的 则对应的费用为 11 11 12 12 13 5 5 5 5 5 842 第一年购置新的 一直用到第五年年底 则总费用为 11 5 6 8 11 18 59显然不同的方案对应不同的费用 2 方法 将此问题用一个赋权有向图来描述 然后求这个赋权有向图的最短路 求解步骤 1 画赋权有向图 设Vi表示第i年初 Vi Vj 表示第i年初购买新设备用到第j年初 j 1年底 而Wij表示相应费用 则5年的一个更新计划相当于从V1到V6的一条路 2 求解 标号法 W12 11 5 16W13 11 5 6 22W14 11 5 6 8 30W15 11 5 6 8 11 41W16 11 5 6 8 11 18 59 W23 11 5 16W24 11 5 6 22W25 11 5 6 8 30W26 11 5 6 8 11 41 W45 12 5 17W46 12 5 6 23W56 13 5 18 W34 12 5 17W35 12 5 6 23W36 12 5 6 8 31 四 最大流问题 一 基本概念1 设一个赋权有向图G V E 在V中指定一个发点vs和一个收点vt 其它的点叫做中间点 对于D中的每一个弧 vi vj E 都有一个非负数cij 叫做弧的容量 我们把这样的图G叫做容量网络 简称网络 记做G V E C 网络G上的流 是指定义在弧集合E上的一个函数其中f vi vj fij叫做弧 vi vj 上的流量 2 称满足下列条件的流为可行流 1 容量条件 对于每一个弧 vi vj E有0 fij cij 2 平衡条件 对于发点vs 有对于收点vt 有对于中间点 有 可行流中fij cij的弧叫做饱和弧 fij cij的弧叫做非饱和弧 3 容量网络G V E C vs为始点 vt为终点 如果把V分成两个非空集合使 则所有一点属于 而另一点属于的弧的集合 称为由决定的割集 记作 割集中所有始点在 终点在的弧的容量之和 称为这个割集的容量 记为 关于最大流问题的定理 最大流最小割定理 任一网络中 最大流的流量等于最小割集的容量 4 容量网络G 若为网络中从vs到vt的一条链 给定向为从vs到vt 上的弧凡与方向相同的称为前向弧 凡与方向相反的称为后向弧 其集合分别用和表示 f是一个可行流 如果满足 则称为从vs到vt的关于f的一条增广链 推论可行流f是最大流的充分必要条件是不存在从vs到vt的关于f的一条可增广链 是一个增广链 显然图中增广链不止一条 二 求最大流的标号法标号过程 1 给发点vs标号 0 2 取一个已标号的点vi 对于vi一切未标号的邻接点vj按下列规则处理 1 如果边 且 那么给vj标号 其中 2 如果边 且 那么给vj标号 其中 3 重复步骤2 直到vt被标号或标号过程无法进行下去 则标号结束