- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
最短路径问题的一般提法如下： G = (V , E ) 为赋权图， 设 图中各边 ( v i , v j ) 有权 lij ，若 lij = ∞ 则表示 vi , v j 没有边相连， ，求一条道路 µ ， v s , v t 为图中任意两点（或指定的两点） 使它是从 v s 到 vt 的所有道路中总权最小的道路。即求满足
标号，对 v j 的 T 标号进行如下的更改：
T (v j ) = min[T (v j ), p (vi ) + lij ]
（3）比较所有具有 T 标号的点，把最小者改为 P 标号，即：
P (v j ) = min[T (v j )]
当存在两个以上最小者时，可同时改变为 P 标号。若全部均为 P 标号则停 止。否则用 v j 代替 vi ，转回（2） 。
X ∪Y = V, X ∩Y = φ
，使得 E 中每一条边的两个端点必有一个
端点属于 X ，另一个端点属于 Y ，则称 G 为二部图（偶图） ， 记作： G = ( X , Y , E ) 。
以点 v 为端点的边数叫做顶点 v 的次（度） ，记作:
deg(v) (d (v)) 。
图与网络的概念
定理 6-1 任何图中顶点次数的总和等于边数的 2 倍。 推论 6-1 任何图中，次为奇数的顶点必有偶数个。 图 G = (V , E ) 和图 H = (V ′, E ′) ，若 V ′ ⊂ V且E ′ ⊂ E ，则 子图，记作： H ⊂ G ；特别的，当 V ′ = V 时， 称 H 是 G 的子图 子图 称 H 为 G 的生成子图 生成子图。 生成子图
【例6-8】中国邮路问题 一个邮递员，负责某一地区的信件投递。 他每天要从邮局出发，走遍该地区所有街 道再返回邮局，问应如何安排送信的路线 可以使所走的总路程最短？用图论的语言 描述：给定一个连通图，每边有非负权， 要求一条回路过每边至少一次，且满足总 权最小。
第二节 最短路径问题
• Dijkstra算法 • Floyd算法
设有向图 G = (V , E ) ， G 的每一条边 (vi , v j ) 上的非负数 cij 称为边的容量，在 V 中指定了一点称为发点（记为 vs ） ，指定 了另一点称为收点（记为 vt ） ，其余的点为中间点，这样的网 络 G 称为容量网络，记作： G = (V , E , C ) 。
对任意 G 中的边 vi , v j 有流量 f ij ，称集合 f = f ij 为 G 的一个流。 称满足下列条件的流为可行流。 （1）容量限制条件：对 G 中每条边 vi , v j ，有 0 ≤ f ij ≤ cij 。 （2）平衡条件：对中间点 vi ，有 资的流入量与流出量相等） 。 对收、发点 ut , us ，有
一个有向图 G 是指一个有序二元组 (V (G ), E (G )) ，其中 有序对的集合； V (G ) 是一个非空集合， E (G ) 是 V (G ) 中元素的有序对 有序对 简写为 G = (V , E ) 。 V (G ) 称为图 G 的顶点集， (G ) 称为 G 的边集， E
当边 ek
算法基本步骤为： （1）输入边权矩阵 D (0) = D ； （2）计算 D 其中 lij
(k )
(k )
( = (lijk ) )n×n , (k = 1, 2,3, 4,L, n),
( ( ( = min[lijk −1) , likk −1) + lkjk −1) ] ； (n) ( ( = (lijn ) ) n×n 中元素 lijn ) 就是 vi 到 v j 的最短路长。
+ −
则称 µ 为从 vS 到 vt 的（关于 f 的）可增广链。 可行流 f 是最大流的充要条件是不存在从 vS 到 vt 的（关于 f 的）可增 广链。
求最大流问题的标号法
• 将所有的点都标上号的过程（即寻找可 增广链的过程） • 调整过程（将能够调整的流量进行调整 的过程）
【例 6-12】某企业从配送中心 vs 向接货点 vt 送货，运输线路如图 6-14 所示，路 旁第一个数字是线路的最大通行能力，第二个数字是一个容许通行的流量。 现在 要求制定一个运输方案使从 vs 运到 vt 的货物数量最多。
【例6-6】公路连接问题 某一地区有若干个主要城市，现准备 修建高速公路把这些城市连接起来，使得 从其中任何一个城市都可以经高速公路直 接或间接到达另一个城市。假定已经知道 了任意两个城市之间修建高速公路的成本， 那么应如何决定在哪些城市间修建高速公 路，使得总成本最小？
【例6-7】指派问题 一家公司经理准备安排n名员工去完成 n项任务，每人一项。由于各员工的特点不 同，不同的员工去完成同一项任务时所获 得的回报是不同的。如何分配工作方案可 以使总回报最大？
第一节 图与网络的概念和模型
• 图与网络的概念 • 树 • 图与网络分析实例
图与网络的概念
一个无向图 G 是指一个有序二元组 (V (G ), E (G )) ，其中
V (G ) 是一个非空集合， E (G ) 是 V (G ) 中元素的无序对 无序对的集合； 无序对 V (G ) 称为图 G 的顶点集， (G ) 称为 G 的边集， E 简写为 G = (V , E ) 。
第六章
图与网络分析
图与网络的概念和模型 最短路径问题 最大流问题 最小费用流问题 运输路径优化应用
知识目标
• • • • • 掌握图与网络的概念和模型； 掌握求最小路径两种算法的计算过程； 掌握最大流算法； 掌握最小费用最大流方法； 了解图与网络分析在运输路径中的应用。
技能目标
• 能够结合实际情况建立图与网络模型； • 能够应用本章算法求最优运输路径。
（3） D
Floyd算法 算法
【例 6-11】 （物流中心选址问题）考虑在某城市建立物流配送网络。若各需求点 之间物流费用如图 6-13 所示，试对该网点布局选择最佳配送中心。
v2 1 2 v1 3 4 v4 6 7 v3 5 2
8
5
图 6-13 各需点及其物流费用
第三节 最大流问题
最大流问题是涉及怎样使得配送网络中物流量最大的问题
bij f ij < cij wij = +∞ f ij = cij −bij f ij > 0 w ji = +∞ f ij = 0
注：长度为 +∞ 的边可以从 W ( f ) 中略去。
寻求最小费用流算法的基本步骤： （1）取零流为初始可行流，即 f 0 = {0}，置 k = 1 。 （ 2 ） 若 有 f ( k −1) ， 构 造 赋 权 有 向 图 W ( f ( k −1) ) ， 在
连通且不含圈的无向图称为树，树中次为 1 的点称为树叶 树 树叶，次 树叶 大于 1 的点称为支点 支点。 支点 图 T = (V , E ), V = n , E = m 等价的。 （1）T 是一个树。 （2）T 无圈，且 m =n-1。 （3）T 连通，且 m =n-1。 （4）T 无圈，但每加一新边即唯一一个圈。 （5）T 中任意两点，有唯一链相连 （6）T 连通，但每舍去一边就不连通。 ，则下列关于树的说法是
vt , µ 上的边，凡与 µ 同向称为前向边，凡与 µ 反向称为后向边，其集合分
别用 µ + 和 µ − 表示， f = { f ij } 是一个可行流，如果满足
0 ≤ f ij < cij cij ≥ f ij > 0
(v , v ) ∈ µ (v , v ) ∈ µ
i j i j
图与网络的矩阵表示
网络（赋权图）G = (V , E ) ，边 (vi , v j ) 有权 wij ，构造矩阵
A = (aij )n × n 其中：当 (vi , v j ) ∈ E 时 aij = wij ，否则为 0 ，
则称矩阵 A 为网络 G 的边权矩阵。 图 G = (V , E ) 中， V = n ，构造一个矩阵 A = ( a ij )n × n ， 其中当 (vi , v j ) ∈ E 时 a ij = 1 ，否则为 0；称 A 图 G 的邻接 矩阵。
v2
(4,3)
v4
(3,3) (1,1) (1,1) (3,0)
(5,3)
vs
(5,1)
vt
(2,1)
v1
(2,2)
v3
图 6- 14
运输线路图
第四节 最小费用最大流问题
在容量网络 G = (V , E , C ) ，每一条边 (vi , v j ) ∈ E 上，除了已 给容量 cij 外，还给了一个单位流量的费用 bij ≥ 0 ，记此时的容 量网络为 G = (V , E , C , B) 。 所谓最小费用最大流问题就是要求一个最大流 f ，使流的 总运输费用 b( f ) =
【例 6-9】 （最短路问题）某物流公司要将一批产品从城市 v1 运到城市 v3 ，其中 经过的城市及城市间的距离见图 6-11，试求从 v1 到 v3 的最短路径。
v2 4 v1 5 v7 1 3 v5
2 7 v6 6 4 1 3
v3 2 v4 1 v8
图 6-11
城市及距离
Floyd算法 算法
L( µ ) =
( vi , v j )∈
∑ µl
ij
最小的 µ 。
Dijkstra算法 算法
算法的基本步骤： （1）给 vs 以 P 标号， P(vs ) = 0 ，其余各点均给 T 标号， T (vi ) = +∞ 。 （2）若 vi 点为刚得到 P 标号的点，考虑这样的点 v j： i , v j ) ∈ E ，且 v j 为 T (v
图与网络的概念
在无向图 G = (V , E ) 中， 若图 G 中某些点与某些边的交替序列可以排成 如下
(vi 0 , ei1 , vi1 , ei 2 L , vik −1 , eik , vik )
