第三章 图和网络技术.ppt

第三章图与网络技术 图的概念 网络概念 网络最短树问题 网络最短路问题 网络最大流问题 图的概念 所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为E，则图可以表示为：G＝（V，E），点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。 在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。 5. 树 一个没有圈的图称为一个无圈图或称为林。 一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。 定理 以下关于树的六种不同描述是等价的： ①无圈连通图。 ②无圈，q=p-1。 ③连通，q=p-1。 ④无圈，但若任意增加一条边，则可得到一个且仅一个圈。 ⑤连通，但若任意舍弃一条边，图便不连通。 ⑥每一对顶点之间有一条且仅有一条链。 6.图的部分（支撑）树 第二节 网络分析 一. 最小部分（支撑）树问题 避圈法是一种选边的过程，其步骤如下： 用避圈法解例2 二. 最短路问题 标号法步骤： 用标号法解例3 三. 最大流问题 最大流问题的数学模型 最大流最小割集定理1 最大流最小割集定理2 最大流最小割集定理3 福德－富克逊方法原理 福德－富克逊方法流图 福德－富克逊方法图示 福德－富克逊方法讨论 福德－富克逊方法讨论 增广链的性质 福德－富克逊方法步骤 寻求增广链的方法 福德－富克逊方法示例 福德－富克逊方法示例 福德－富克逊方法示例 福德－富克逊方法示例 福德－富克逊方法示例 福德－富克逊方法示例 福德－富克逊方法示例 福德－富克逊方法示例 福德－富克逊方法示例 一、工程计划网络问题（关键路径法） 例1 为筹建某餐馆，需制定计划。将工程分为14道工序，各工序需时及先后关系如下表。试求该工程完工期T及关键路径。 二、工序时间不确定的工程计划网络问题  （计划评审技术PERT） ②寻求增广链 如图v1是已经标记的点, 其它点是未标记的点 (v1 ,v2)是非饱和弧, v2可以标记: [v1+,e2] e2=min{e1,b12-x12} (v1 ,v3)是饱和弧, 目前v3和其它点暂时不能标记，即暂时没有从v1 到v3或其它点的增广链。 vs 10 11 5 6 4 7 3 9 15 vt v5 v3 v4 v2 (4) (9) (3) (1) (5) (7) (5) (8) [-, ∞] [vs+, 11] ②寻求增广链 如图v2是已经标记的点, v3是未标记的点 (v3 ,v2)是非零流弧, v3可以标记: [v2-,e3] e3=min{e2, x32}=min{11,3} [-, ∞] [vs+, 11] [v2-, 3] [v2+, 4] [v3+, 3] [v5+, 4] vs 11 5 4 3 15 vt v5 v3 v4 v2 (4) (9) (1) (5) (7) (5) (8) 10 7 9 (3) 6 ③在增广链上调整流量。 vt已经标记, 找到流量增广链。 vs 10 11 5 6 4 7 3 9 15 vt v5 v3 v4 v2 (4) (9) (3) (1) (5) (7) (5) (8) [-, ∞] [vs+, 11] [v2-, 3] [v2+, 4] [v3+, 3] [v5+, 4] 正向流流量增加et，逆向流流量减少et 调整后流量f=17 ②寻求增广链 vs 10 11 5 4 3 15 vt v5 v3 v4 v2 (8) (9) (3) (1) (5) (7) (9) (8) (4) 9 6 7 [-, ∞] [vs+, 7] [v2-, 3] [v3+, 1] [v3+, 3] [v4+, 3] vt已经标记, 找到流量增广链。 ③在增广链上调整流量。 正向流流量增加et=3，逆向流流量减少et 调整后流量 f=20 vs 10 11 5 4 3 15 vt v5 v3 v4 v2 (11) (9) (4) (5) (7) (9) (11) (4) 9 6 7 ②寻求增广链 Vs