第十章 图与网络的分析.ppt

* 例6.7.1~6.7.2 中心 一般中心 中位点 一般中位点 第十章 图与网络分析 * 图的基本概念 最小支撑树 最短路问题 网络系统最大流问题 网络系统中的最小费用最大流问题 中国邮递员问题 * B A C D 一、图的基本概念 哥尼斯堡七桥问题 (K?nigsberg Bridge Problem)。 Leonhard Euler (1707-1783) 在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理。 * 图与网路的基本概念 图 (Graph) 节点和边的集合 一般用 G(V,E) 表示 点集 V={v1,v2,…, vn} 边集E={eij } * 无向图与有向图 边都没有方向的图称为无向图 当边都有方向时，称为有向图。在有向图中，有向边又称为弧 图中既有边又有弧，称为混合图 * 链，圈，路，回路 相邻节点的序列 {v1? ,v2? ,…, vn?} 构成一条链(link) 首尾相连的链称为圈(loop) 在有向图中，链中每条边的方向和链的方向一致，将该链称为路径(path) 首尾相连的路称为回路(circuit)； * 二、树与最小支撑树 树：无圈的连通图 管理的指标体系、家谱、分类学、组织结构等都是典型的树图 * 图的支撑树 图 图的支撑树 * 避圈法、破圈法 A B C D E F 6 5 5 1 7 2 3 4 4 * 三、最短路问题 V1 V2 V3 V4 V6 V5 V7 8 2 6 2 3 8 6 3 9 5 4 * 狄克斯特拉算法 (Dijkstra algorithm, 1959) 计算两节点之间或一个节点到所有节点之间的最短路 令 dij 表示 vi 到 vj 的直接距离(两点之间有边)，若两点之间没有边，则令 dij = ?，若两点之间是有向边，则 dji = ?；令 dii = 0，s 表示始点，t 表示终点 0、令始点Ts=0，并用框住，所有其它节点临时标记 Tj=? ； 1、从 vs 出发，对其相邻节点 vj1 进行临时标记，有 Tj1=ds,j1 ； 2、在所有临时标记中找出最小者，并用框住，设其为 vr 。若此时全部节点都永久标记，算法结束；否则到下一步； 3、从新的永久标记节点 vr 出发，对其相邻的临时标记节点进行再标记，设 vj2 为其相邻节点，则 Tj2=min{Tj2, Tr+dr,j2 }，返回第2步。 * Dijkstra最短路算法的特点和适应范围 一种隐阶段的动态规划方法 每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种深探法 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij?0，第 k 次迭代得到的永久标记，其最短路中最多有 k 条边，因此最多有n?1 次迭代 可以应用于简单有向图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第 n?1 次迭代后仍有节点的标记为 ?，则表明 vs 到该节点无有向路径 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束了；但算法复杂度是一样的 应用 Dijkstra 算法 n?1 次 ，可以求所有点间的最短路 vs 到所有点的最短路也是一棵生成树，但不是最小生成树 * 四、网络系统的最大流问题 网络系统最大流的概念 定义网路上支路的容量为其最大通过能力，记为 cij ，支路上的实际流量记为 fij 容量限制条件：0? fij ? cij 平衡条件： 满足上述条件的网路流称为可行流 * 确定网路最大流的标号法 从任一个初始可行流出发，如 0 流 基本算法：找一条从 s 到 t 点的增广链(augmenting path) 若在当前可行流下找不到增广链，则已得到最大流 增广链中与 s 到 t 方向一致的弧称为前向弧，反之后向弧 增广过程：前向弧 f?ij=fij +q , 后向弧 f?ij=fij ?q 增广后仍是可行流 * 五、 最小费用最大流 双权网路：每条弧不但有容量，还有单位流量的通过费用 两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法 基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧 基于可行弧集的最大流算法：从 0 费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主-对偶规划的解法。使用这种方法的还有运输问题、匹配问题 * 6.4.5 以最短路为基础汇总网路上的流 在电路网中每两点之间都有中继电路群需求，但并不是