06 第六章 图与网络分析.pptx

第1页：图与网络分析章节目录

本章内容：

• 6.1 图的基本概念
• 6.2 树：树与支撑树、最小支撑树问题
• 6.3 最短路问题
• 6.4 网络最大流问题

第2页：图的基本概念（无向图）

6.1 图的基本概念

图

由点和点与点之间的连线组成。若点与点之间的连线没有方向，称为边，由此构成的图为无向图，记为 G = (V, E)

简单图、多重图

不含环与多重边的图为简单图，含多重边的为多重图

次

一个点关联的边数称为该点的次

奇点、偶点

次为奇数的点称奇点，次为偶数的点称偶点

悬挂点、悬挂边、孤立点

次为 1 的点称悬挂点，与之关联的边称悬挂边，次为 0 的点称孤立点

端点、相邻、关联边、环

一条边的两个点互为端点并称相邻，边与其端点互为关联，两个端点重合的边称环

链

是一个点、边交错序列，如 (v1, e2, v2, e3, v4)，其中间点不重复

圈

链中若起始点与终了点是同一个点，则称为圈，例如 (v1, e2, v2, e3, v4, e4, v3, e1, v1)

第3页：有向图与连通性

若点与点之间的连线有方向，称为弧，由此构成的图为有向图，记为 D = (V, A)。

基础图

去掉有向图各弧的方向后得到的无向图

始点、终点

弧的方向起点称始点，终点称终点

路、回路

有向图中方向一致的点弧交错序列称路，起点与终点重合的路称回路

连通图、不连通图

任意两点间都有链相连的图称连通图，否则为不连通图

连通分图

不连通图中每个连通的部分称其一个连通分图

支撑子图

包含原图全部点的子图称支撑子图

第4页：运动员参赛项目安排实例

例1：有甲、乙、丙、丁、戊、己六名运动员报名参加六个项目比赛，参加情况如下表（✓ 表示该运动员参加该项目）。问应如何安排比赛项目的顺序，才能做到运动员不连续地参加两项比赛。

本例可用图与网络模型描述：把项目作为点、把「有同一运动员参加」的两个项目之间连边，问题转化为在该图上寻找满足条件的安排（相邻两项目之间不能有共同的运动员）。一种可行的安排顺序为 A、C、B、F、E、D。

源文件该页参加情况表（甲、乙、丙、丁、戊、己 与 A—F 项目的 ✓ 分布）被打散，无法安全还原为行列，建议对照原图核对。

第5页：树与支撑树的定义

6.2 树

树

一个无圈的连通图称为树

树的边数

树图 G = (V, E) 的点数记为 p，边数记为 q，则 q = p - 1

支撑树

若图 T = (V, E′) 是图 G = (V, E) 的支撑子图，且图 T 是一个树，则称 T 是 G 的一个支撑树

第6页：破圈法与避圈法

图 G 有支撑树，当且仅当图 G 是连通的。求连通图支撑树的方法有「破圈法」和「避圈法」两种。

• 破圈法：任取一个圈，从圈中去掉任一条边；在余下的图中重复这个步骤，直到得到一个不含圈的连通图为止
• 避圈法（也称加边法）：开始选一条边，以后每一步中，总从未被选取的边中选一条边，使其与已选边不构成圈，直到不能添加为止

第7页：最小支撑树问题

6.2.2 最小支撑树问题

给图 G 中的每一条边 [vi, vj] 一个相应的数 ωij，则称 G 为赋权图。在赋权图 G 的所有支撑树中，必有某个支撑树，其所有边的权之和为最小，称为最小树（最小支撑树）。

求赋权图 G 的最小支撑树的方法也有两种——「破圈法」和「避圈法」。

破圈法

任选一个圈，从圈中去掉权最大的一条边；在余下的图中重复这个步骤，直到得到一个不含圈的图为止

源文件该页示例图的边权（如 6、5、5、1、7、2、3、4、4 等）与顶点编号为图形化排布，具体连线关系建议对照原图核对。

第8页：避圈法求最小树

避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小、且与已选边不构成圈的边，直到选够 p - 1 条边为止，即得最小支撑树。

示例图中 v1 至 v6 六个点的边权为 1、2、2、3、4、4、5、5、6、7 等，按上述规则依次取边后即得最小树，其权之和为最小。

源文件该页为图形化排布，边的连接关系与权值的对应建议对照原图核对。

第9页：最短路问题的定义

6.3 最短路问题（从一点到各点最短路）

对于有向图 D = (V, A)，给其每一个弧 (vi, vj) 一个相应的权值 wij，D 就成为赋权有向图。

路的权

给定赋权有向图 D 中的两个顶点 vs 和 vt，设 P 是由 vs 到 vt 的一条路，把 P 中所有弧的权之和称为路 P 的权，记为 w(P)

最短路

如果路 P* 的权 w(P*) 是由 vs 到 vt 的所有路的权中的最小者，则称 P* 是从 vs 到 vt 的最短路

距离

最短路 P* 的权 w(P*)，称为从 vs 到 vt 的距离，记为 d(vs, vt)

源文件该页示例图含 v1—v9 九个顶点，各弧的权值（如 1、2、3、4、6、10 等）为图形化排布，建议对照原图核对。

第10页：最短路的标号法求解

本页演示用标号法（狄克斯屈拉算法）求 v1 到其余各点的最短路：每个顶点处标注形如 (vi, l) 的临时标号，其中 vi 表示最短路上的前一点、l 表示当前的路长，方括号 [·] 表示已确定为永久标号。

• 起点 v1 标 [--, 0]；v2 得 (v1, 1)、v3 得 (v1, 3)、v4 得 (v1, 6)
• v3 得永久标号 [v3, 5]，进而 v2 得 [v2, 6]、v5 得 (v3, 5)
• v5 得 [v5, 9] 与 [v5, 10]、[v5, 12]，v4 得 (v4, 11) 等

对无向图的最短路问题，可把每条边看作两条方向相反的弧，同样用上述方法求解。

源文件该页标号全部为图形化排布，各轮的标号与顶点的对应关系建议对照原图核对。

第11页：最短路例题图

本页为最短路问题的示例赋权图，含 v1 至 v6 六个顶点，各弧（边）的权值为 5、7、2、2、7、2、6、1、3、6、4 等。

源文件该页仅有顶点编号与连排的权值数字（如 5 7 2 2 7 2 6 1 3 6 4），顶点之间的连接关系未提取成功，故无法还原为权值表，建议对照原图补充。

第12页：各点间最短路

6.3 最短路问题（各点间最短路）

求赋权图中所有点对之间的最短路，可用矩阵迭代法：以各点对间的直接距离作为初始矩阵 A⁽⁰⁾ = (dij)，其中不直接相邻的点对间距离记为 ∞；然后依次以各点为中间点作迭代，逐次得到 A⁽¹⁾、A⁽²⁾ …… 直到矩阵不再变化，即为各点对间的最短路距离矩阵。

源文件该页 A⁽⁰⁾ 至 A⁽²⁾ 三个矩阵的数字全部连排且次序被打乱（含 0、2、3、4、5、6、7、10 等元素），无法安全切分为行列，故不作矩阵还原，具体数值建议对照原图核对。

第13页：最大流问题的基本概念

6.4 最大流问题

给一个有向图 D = (V, A)，指定两个点，一个点称为发点，记为 vs；另一个点称为收点，记为 vt；其余点称为中间点。对于 D 中的每一个弧 (vi, vj)，相应地给一个数 cij（cij ≥ 0），称为弧 (vi, vj) 的容量。我们把这样的 D 称为网络（或容量网络），记为 D = (V, A, C)。

源文件该页示例网络含 vs、v1、v2、v3、v4、vt 六个点，各弧容量（如 3、1、1、2、3、5、5、2、4 等）为图形化排布，建议对照原图核对。

第14页：可行流与最大流

所谓网络上的流，是指定义在弧集 A 上的函数 f = {f(vi, vj)}，并称 f(vi, vj) 为弧 (vi, vj) 上的流量，简记为 fij。

可行流

满足容量限制与中间点流量守恒条件的流

可行流的流量

指从发点流出的总流量（等于流入收点的总流量）

最大流

网络中流量最大的可行流

源文件该页示例网络在各弧上标注 (容量, 流量) 形式的数对，如 (3,1)、(5,2)、(1,0)、(2,2)、(4,1) 等，建议对照原图核对。

第15页：截集与最小截集

给定容量网络 D = (V, A, C)，若点集 V 被剖分为两个非空集合 V1 和 V2，使 vs ∈ V1、vt ∈ V2，则把弧集 (V1, V2) 称为（分离 vs 和 vt 的）截集。

显然，若把某一截集的弧从网络中去掉，则从 vs 到 vt 便不存在路。所以，直观上说，截集是从 vs 到 vt 的必经之路。

截集的容量（简称截量）

截集中各弧的容量之和

最小截集

所有截集中截量最小的那个截集

第16页：增广链的定义

对于可行流 f = {fij}，我们把网络中使 fij = cij 的弧称为饱和弧，使 fij < cij 的弧称为非饱和弧；把使 fij = 0 的弧称为零流弧，使 fij > 0 的弧称为非零流弧。

设 f 是一个可行流，μ 是从 vs 到 vt 的一条链，若 μ 满足前向弧都是非饱和弧、后向弧都是非零流弧，则称 μ 是（可行流 f 的）一条增广链。

若 μ 是联结发点 vs 和收点 vt 的一条链，我们规定链的方向是从 vs 到 vt，则链上的弧被分成两类：前向弧（方向与链一致）与后向弧（方向与链相反）。

第17页：最大流最小截定理

对最大流问题有下列定理：

定理1

可行流 f* = {fij*} 是最大流，当且仅当 D 中不存在关于 f* 的增广链

定理2（最大流最小截定理）

任一网络中，最大流的流量等于最小截集的截量

第18页：求最大流的标号法思想

6.4.2 求最大流的标号法

标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从发点 vs 到收点 vt 的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，即得最大流。

第19页：标号过程的步骤

标号过程：

1. 给 vs 标号 (-, +∞)，vs 成为已标号未检查的点，其余都是未标号点
2. 取一个已标号未检查的点 vi，对一切未标号点 vj：
   • 若有非饱和弧 (vi, vj)，则给 vj 标号 (vi, l(vj))，其中 l(vj) = min[l(vi), cij - fij]
   • 若有非零流弧 (vj, vi)，则给 vj 标号 (-vi, l(vj))，其中 l(vj) = min[l(vi), fji]
   此时 vj 成为已标号未检查的点，而 vi 成为已标号已检查的点
3. 重复步骤 (2)，直到 vt 成为标号点或所有标号点都检查过。若 vt 成为标号点，表明得到一条从 vs 到 vt 的增广链，转入调整过程；若所有标号点都检查过而 vt 未得标号，则表明这时的可行流即为最大流

调整过程：沿增广链按 l(vt) 对各前向弧加、后向弧减，得到新的可行流。

第20页：标号法求最大流实例

下面用实例说明具体的操作方法。

例：在图中给出的可行流的基础上，求 vs 到 vt 的最大流。图中各弧标注 (容量, 流量)，如 (3,3)、(5,1)、(1,1)、(4,3)、(2,2)、(3,0)、(2,1) 等。

• 第一轮标号：vs 标 (-, +∞)，v1 标 (vs, 4)，v2 标 (-v1, 1)、v3 标 (v2, 1) 等，vt 得标号 (v4, 11) 形式的增广链，标号结束，进入调整过程
• 第二轮标号后无增广链，标号结束，得最大流，同时得到最小截集

源文件该页标号与 (容量, 流量) 数对全部为图形化排布，各轮标号与顶点的对应关系建议对照原图核对。

第21页：应用举例：桥梁切断

应用举例：某河流中有 4 个岛屿，从两岸（A、F）至各岛屿（B、C、D、E）之间的桥梁联系情况如图。问至少炸断几座桥，才能完全切断两岸联系。

本例把每座桥看作一条容量为 1 的弧、把两岸分别看作发点与收点，则「完全切断两岸联系」所需炸断的最少桥梁数，就是该网络的最小截量，可由最大流最小截定理求得。图中各弧的编号为 1—13。

源文件该页桥梁连接关系与弧编号为图形化排布，建议对照原图核对具体的桥梁分布。

第22页：应用举例：摩托车更新

应用举例：某人购买一台摩托车，准备在今后 4 年内使用。他可在第一年初购一台新车连续使用 4 年，也可于任何一年年末卖掉，于下一年初换一台新车。已知各年初的新车购置价见表，不同役龄车的年使用维护费及年末处理价见表。要求确定该人使用摩托车的最优更新策略，使 4 年内总费用最省。

本例可化为最短路问题求解：把各年初作为顶点、把「第 i 年初买车用到第 j 年初」的总费用作为弧权，求第一年初到第四年末（或第五年初）的最短路即为最优更新策略。

源文件该页表格数据与文字交错连排，购置价、维护费与处理价三行的对应关系按原文顺序整理，建议对照原图核对。