1.图的基本概念 2.树 3.最短路 4.最大流问题 5.最小费用最大流 6.中国邮递员问题

Presentation on theme: "1.图的基本概念 2.树 3.最短路 4.最大流问题 5.最小费用最大流 6.中国邮递员问题"— Presentation transcript:

1 1.图的基本概念 2.树 3.最短路 4.最大流问题 5.最小费用最大流 6.中国邮递员问题
第七章 图与网络分析 1.图的基本概念 2.树 3.最短路 4.最大流问题 5.最小费用最大流 6.中国邮递员问题

2 图与网络分析 问题提出 应用：生产组织，邮递员问题，通讯网络等。 哥尼斯堡七桥问题

3 在图中找一条经过每边一次且仅一次的路——欧拉回路。
哥尼斯堡七桥问题 在图中找一条经过每边一次且仅一次的路——欧拉回路。 A D B C 由点和边组成 A B C D

4 “环球旅行”问题 在图中找一条经过每个点一次且仅一次的路——哈密尔顿回路。 “中国邮路问题” 在图中找一条经过每边的最短路——类似带权的欧拉回路。 “货郎担问题” 在图中找一条经过每个点一次且仅一次的最短路——带权的哈密尔顿回路。

5 1.图的基本概念 例 1: 铁路交通图 例 2: 球队比赛图 点: 表示研究对象. 连线：表示两个对象之间的某种特定关系。
例 1: 铁路交通图 例 2: 球队比赛图 点: 表示研究对象. 连线：表示两个对象之间的某种特定关系。 关系的对称性：两对象之间的关系可互换。

6 边：不带箭头的联线，表示对称关系。 弧：带箭头的联线，表示不对称关系。 无向图：简称图，有点和边组成。 表示为： G=（V，E） V--点集合 E--边集合 例：右图 V={v1，v2，v3，v4} E={e1，e2，…,e7} e1=[v1,v2]e2=[v1,v2], …,e7=[v4,v4]

7 有向图：由点和弧组成。表示为： D=（V，A） V--点集合 A--弧集合 点数: p(G) 或 p(D) 边数: q(G) 弧数:q(D)
例：右图 V={v1，v2,…,v5} A={a1，a2,…,a7} a1={v1,v5},a2={v5,v4},…,a7={v1,v4}

8 无向图的有关概念 端点: e=[u,v]∈E, 则u,v是e的端点, 称u,v相邻. 关联边: e是点u,v的关联边.
多重边: 两点之间多于一条边. 简单图: 无环,无多重边的图. 多重图: 无环,允许有多重边的图.

9 次: 以点v为端点的边的个数称为v的次. 表示为: d(v) 悬挂点: 次为1的点. 悬挂边: 悬挂点的关联边. 孤立点: 次为0的点.
奇点: 次为奇数的点. 偶点: 次为偶数的点. 悬挂边 孤立点

10 定理1: 图G=(V,E)中,所有点的次之和是边数的两倍, 即:
定理2: 任意一图中, 奇点的个数为偶数. 证明:设 V1--奇点的集合, V2--偶点的集合 偶数 偶数 偶数

11 链：点边交错系列， 记为： 圈： 的链。 初等链：点 均不相同。 初等圈：点 均不相同。 简单链：链中边均不相同。 简单圈：圈中边均不相同。
圈： 的链。 初等链：点 均不相同。 初等圈：点 均不相同。 简单链：链中边均不相同。 简单圈：圈中边均不相同。 例：右图 无重复点,无重复边 有重复点,无重复边

12 连通图：任意两点之间至少有一条链。 不连通图： 连通分图：对不连通图，每一连通的部分称为一个连通分图。 支撑子图：对G=（V，E），若G`=(V`,E`), 使V`=V, E` E, 则G`是G的一个支撑子图（生成子图）. G-v: 图G去掉点v及v的关联边的图.

13 有向图的有关概念 基础图: 对D=(V, A), 去掉图上的箭头. 始点和终点: 对弧a=(u,v), u为a的始点, v为a的终点.
圈, 初等链,初等圈: 类似定义. 方向可以不同

14 道路:若 是D中的一条链，且 ，t=1,2,…,k-1,称之为从 到 的一条道路。
回路: 的路. 初等路: 道路中点不相同. 初等回路: 回路中点不相同. 简单有向图: 无自环, 无多重弧. 多重有向图: 有多重弧. 方向相同

15 2. 树 2.1 树及其性质 2.2 图的支撑树（生成树） 2.3最小支撑树问题 2.4 根树及其应用

16 2.1 树及其性质 例: 电话线架设、比赛程序、组织结构等。 树:连通的无圈的无向图称为树。

17 树的性质： （1）G是一个树 （2）G连通，且恰有p-1条边。 （3）G无圈，且恰有p-1条边。 （4）G连通，但每舍去一边就不连通。
图G=（V，E），p个点、q条边下列说法是等价的 （1）G是一个树 （2）G连通，且恰有p-1条边。 （3）G无圈，且恰有p-1条边。 （4）G连通，但每舍去一边就不连通。 （5）G无圈，但每增加一边即得唯一一个圈。 （6）G中任意两点之间恰有一条链(简单链)。

18 2.2 图的支撑树（生成树） 定义:设图T=(V，E’) 是图G=(V,E)的支撑子图,如果T是一个树, 则称T是G的一个支撑树。
定理5：图G=（V，E）有支撑树的充分必要条件是G是连通的。

19 找图中生成树的方法： 求支撑树的破圈法

20 找图中生成树的方法： 求支撑树的避圈法 深探法 广探法

21 2.3最小支撑树问题 赋权图(网络）: 给图G=(V,E), 对G中的每一条边[vi,vj], 相应地有一个数wij, 则称这样的图为赋权图, wij 称为边[vi,vj]上的权. 支撑树的权:若T=(V,E’) 是G的一个支撑树, E’中的所有边的权之和称为支撑树的权, 记为w(T):

22 定义: 最小支撑树(最小树)T*: 求最小树的 避圈法: 例: 图8-27 求最小树的 破圈法: 例: 图8-28

23 2.4 根树及其应用 有向树中根树 在计算机科学、决策论的应用 有向树：
分点枝 有向树： 根树：有向树T，恰有一个结点入次为0，其余各点入次为1，则称T为根树。 M叉树： 二叉树： 第一层 第二层 第三层 三叉树 叶

24 带权的二叉树T：有s个叶子，权分别为pi， 根到各叶子的距离（层次）为 二叉树的总权数
最优二叉树（ Huffman树）：总权数最小的二叉树 算法步骤：——Huffman算法 将s个叶子按权由小到大排列， 将两个最小的叶子合并为一个分枝点，其权为两者之和，将新的分枝点作为一个叶子，转上一步，直到结束。

25 例1、s=6，其权分别为4，3，2，2，1，求最优二叉树。
5 3 6 1 2 3 4

26 例1、s=6，其权分别为4，3，2，2，1，求最优二叉树。
9 6 5 15 15 9 5 3 6 1 2 3 4

27 例2、最优检索问题。 使用计算机进行图书分 类。现有五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册，问如何安排分检过程，可使总的运算（比较）次数最小？

28 例3：P235、例11 1.0 0.55 0.30 0.18 0.10 0.05 0.45 0.08 0.12 0.25 一等品 五等品 四等品 三等品 二等品 等外品 测试顺序

29 3. 最短路问题 3.1 引例 单行线交通网：v1到v8使总费用最小的旅行路线。 最短路问题的一般描述：
对D=（V，A）， a=（vi，vj），w（a）=wij，P是vs到vt的路，定义路P的权是P中所有弧的权的和，记为w（P）

30 路P0的权称为从vs到vt的距离，记为： d（ vs，vt ） 3.2最短路算法 一般结论 则最短路问题为：
Dijkstra算法 ：有向图 ，wij≥0 一般结论

31 Dijkstra算法基本思想 P标号：已确定出最短路的节点。 T标号：为确定出最短路的节点，但表示其距离的上限。 Si：P标号节点的集合。 λ(v)：最短路中前一个节点的编号。 初始值：

32 例:

33

34

35

36

37

38

39

40 总结: 算法步骤:

41 Dijkstra算法 ：无向图求最短链，wij≥0
存在负权时求最短路问题

42 4.网络最大流问题 4.1基本概念和基本定理 网络与流 定义: 对有向图D=(V,A):
vs --始点 vt -- 终点 其余 -- 中间点 c(vi,vj) -- 弧(vi,vj)的容量, 简写为cij D=(V,A,C) -- 网络 fij -- 弧(vi,vj)上的流量

43 可行流与最大流 可行流满足: 流入量=流出量 流入量 流出量

44 最大流问题

45 增广链: 几个概念: 对可行流 例:图10-23

46 增广链: 设f是一可行流, μ时从始点到终点的一条链, 若μ满足下列条件,称其为一条增广链.
可增加流量的链 增广链: 设f是一可行流, μ时从始点到终点的一条链, 若μ满足下列条件,称其为一条增广链. 例: 图10-24 截集和截量 设 把始点在S,终点在T中的所有弧构成的集合, 记为(S,T).

47 定义: 截集 定义: 截量

48 几点结论

49 4.2求最大流的标号法 网络中的点分为: 标号点 标号未检查点 标号已检查点 未标号点

50 1) 标号过程

51 2) 调整过程: 沿增广链调整流量. 例: 图10--25

52 5.最小费用最大流 定义: 对D=(V,A,C), 给定一个单位流量的费用bij≥0, 最小费用最大流即:求一最大流f, 使
对增广链μ, 若调整流量θ=1, 那么新可行流f’的费用比原可行流f的费用增加:

53 此为增广链μ的费用. 最小费用最大流的求解 构造赋权有向图w(f), 定义:

54 在w(f)中找最小费用增广链, 直至没有最小费用增广链为止.
若存在最小费用增广链, 调整流量如下:

55 求最小费用最大流算法 V1 初 始 网 络 数 值 Vt Vs V3 V2

56 求最小费用最大流算法 初 始 网 络 数 值 V1 (1, 7) (4,10) Vt Vs (2, 5) (6, 2) (2, 4)
(1, 8) bij Cij (4,10) V3 V2

57 求最小费用最大流算法 V1 取初始 可行流 f (0) =0 Vt Vs V3 V2

58 求最小费用最大流算法 取初始 可行流 f (0) =0 V1 (1, 0) (4,0) Vt Vs (2, 0) (6, 0) (2, 0)
bij fij V3 (4,0) V2

59 求最小费用最大流算法 取初始 可行流 f (0) =0 构造赋 权图 W(f (0)) V1 (1, 0) (4,0) Vt Vs
(2, 0) (6, 0) (2, 0) (1, 0) V3 (4,0) V2

60 求最小费用最大流算法 取初始 可行流 f (0) =0 构造赋 权图 W(f (0)) V1 (1, 0) (4,0) Vt Vs
(2, 0) (6, 0) (2, 0) (1, 0) V3 (4,0) V2

61 求最小费用最大流算法 取初始 可行流 f (0) =0 构造赋 权图 W(f (0)) ( +, 0 ) V1 (1, 0) (4,0)
Vt Vs (2, 0) (6, 0) (2, 0) (1, 0) V3 (4,0) V2

62 求最小费用最大流算法 在初始 赋权图 W(f (0)) 上求出 最短路 V1 (1, 0) (4,0) Vt Vs (2, 0)
(6, 0) (2, 0) (1, 0) (4,0) V3 V2

63 求最小费用最大流算法 在最短 路上增 加流量 V1 (1,5) (4,0) Vt Vs (2, 5) (6, 0) (2, 0)
(1, 5) (4,0) V3 V2

64 求最小费用最大流算法 在最短 路上增 加流量 原流量 如图所 示 V1 (1, 0) (4,0) Vt Vs (2, 0) (6, 0)

65 求最小费用最大流算法 求 增 加 的 流 量 f (0) V1 (1, 0) (4,0)  7 - 0 Vt Vs (2, 0)
(6, 0)  5 - 0 (2, 0) 最小 (1, 0)  8 - 0  (4,0) V3 V2 f (0)

66 求最小费用最大流算法 在最短 路上增 加流量  = 5 得到新 的流量 f (1)=5 V1 (1,5) (4,0) Vt Vs
(2, 5) (6, 0) (2, 0) (1, 5) (4,0) V3 V2

67 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W(f (1)) V1 (1,5) (4,0) Vt Vs (2, 5)
*只对增广链 (4,0) Vt Vs (2, 5) (6, 0) (2, 0) (1, 5)  8 (4,0) V3 V2

68 求最小费用最大流算法 赋 权 图 W(f (1)) 的构造 V1 (1,5) (4,0) Vt Vs (2, 5) (6, 0)
*只对增广链 (4,0) Vt Vs (2, 5) (6, 0) (2, 0) (1, 5) (-1, 5)  8 (4,0) V3 V2

69 求最小费用最大流算法 赋 权 图 W(f (1)) 的构造 V1 (1,5) (4,0) Vt Vs (2, 5) (6, 0)  5
*只对增广链 (4,0) Vt Vs (2, 5) (6, 0)  5 (2, 0) (1, 5) (-1, 5)  8 (4,0) V3 V2

70 求最小费用最大流算法 赋 权 图 W(f (1)) 的构造 V1 (1,5)  7 (4,0) Vt (-1,5) Vs (-2, 5)
*只对增广链  7 (4,0) Vt (-1,5) Vs (-2, 5) (6, 0)  5 (2, 0) (1, 5) (-1, 5)  8 (4,0) V3 V2

71 求最小费用最大流算法 构造的 赋权 图 W(f (1)) V1 (1,5) (4,0) Vt (-1,5) Vs (-2, 5)
*只对增广链 (4,0) Vt (-1,5) Vs (-2, 5) (6, 0) (2, 0) (1, 5) (-1, 5) (4,0) V3 V2

72 求最小费用最大流算法 在赋 权图 W(f (1)) 上求出 最短路 V1 (1,5) (4,0) Vt (-1,5) Vs (-2, 5)
(6, 0) (2, 0) (1, 5) (-1, 5) (4,0) V3 V2

73 求最小费用最大流算法 在最短 路上增 加流量 V1 最小 (1,5) (4,0)  7 - 5 = 2 Vt  10 - 0 Vs Vs
(2, 5) (6, 0) (2, 0) (1, 5) (4,0) V3 V2

74 求最小费用最大流算法  = 2 得到新 的流量 f (2)=7 新的流 量图如 图所示 V1 (1,7) (4,2) Vt Vs Vs
(2, 5) (6, 0) (2, 0) (1, 5) (4,0) V3 V2

75 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W(f (2)) V1 V1 (1,5) (4,0) Vt (-1,5) Vs
*只对增广链 (4,0) Vt (-1,5) Vs (-2, 5) (6, 0) (2, 0) (-1, 5) (1, 5) (4,0) V3 V2

76 求最小费用最大流算法 对最短 路上求 新的权 值 V1 V1 (1,7) (4,2) Vt  10 Vs (-2, 5) (6, 0)
(2, 0) (-1, 5) (1, 5) (4,0) V3 V2

77 求最小费用最大流算法 赋 权 图 的构造 W(f (2)) V1 V1 (1,7) (4,2) Vt (-4,2) Vs (-2, 5)
*只对增广链 (4,2) Vt (-4,2) Vs (-2, 5) (6, 0) (2, 0) (-1, 5) (1, 5) (4,0) V3 V2

78 求最小费用最大流算法 赋 权 图 的构造 W(f (2)) V1 V1 (1,7) (4,2)  7 Vt (-4,2) Vs
*只对增广链 (4,2)  7 Vt (-4,2) Vs (-2, 5) (6, 0) (2, 0) (1, 5) (-1, 5) (4,0) V3 V2

79 求最小费用最大流算法 赋 权 图 的构造 W(f (2)) V1 V1 (-1,7) (4,2) Vt (-4,2) Vs (-2, 5)
*只对增广链 (4,2) Vt (-4,2) Vs (-2, 5) (6, 0) (2, 0) (1, 5) (-1, 5) (4,0) V3 V2

80 求最小费用最大流算法 新 赋 权 图 W(f (2)) V1 V1 (-1,7) (4,2) Vt (-4,2) Vs (-2, 5)
*只对增广链 (4,2) Vt (-4,2) Vs (-2, 5) (6, 0) (2, 0) (1, 5) (-1, 5) (4,0) V3 V2

81 求最小费用最大流算法 在赋 权图 W(f (2)) 上求出 最短路 V1 V1 (-1,7) (4,2) Vt (-4,2) Vs
(-2, 5) (6, 0) (2, 0) (1, 5) (-1, 5) (4,0) V3 V2

82 求最小费用最大流算法 在最短 路上增 加流量  = 3 V1 (1,7) (4,2) Vt (2, 5) (6, 0) (2, 0) 最小
(1, 5)  4 - 0  8 - 5 = 3 (4,0) V3 V2  10 - 0

83 求最小费用最大流算法 在最短 路上增 加流量  = 3 得到新 的流量 f (3)=10 V1 (1,7) (4,2) Vt (2, 5)
(6, 0) (2, 3) (1, 8) (4,3) V3 V2

84 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W(f (3)) V1 V1 (-1,7) (4,2) Vt (-4,2)
*只对增广链 (4,2) Vt (-4,2) (-1,5) Vs (-2, 5) (6, 0) (2, 3)  4 (1, 8)  8 (4,3) V3 V2  10

85 求最小费用最大流算法 赋 权 图 W(f (3)) 的构造 *只对增广链 V1 V1 (-1,7) (4,2) Vt (-4,2)
(-1,5) Vs (-2, 5) (6, 0) (-2, 3) (2, 3) (-1, 8) (-4,3) V3 V2 (4,3)

86 求最小费用最大流算法 在赋权 图 W(f (3)) 上求出 最短路 V1 V1 (-1,7) (4,2) Vt (-4,2) (-1,5)
Vs (-2, 5) (6, 0) (-2, 3) (2, 3) (-1, 8) (-4,3) V3 V2 (4,3)

87 求最小费用最大流算法 在初始 赋权图 W(f (0)) 上求出 最短路 V1 V1 (-1,7) (4,2) Vt (-4,2)
(-1,5) Vs (-2, 5) (6, 0) (-2, 3) (2, 3) (-1, 8) (-4,3) V3 V2 (4,3)

88 求最小费用最大流算法 在最短 路上增 加流量 V1 (1,7) (4,2) Vt  10 - 2 (2, 5) (6, 0) (2, 3)
(1, 8)  4 - 3 = 1 (4,3) V3 V2 最小  10 - 3

89 求最小费用最大流算法 在最短 路上增 加流量  = 1 得新的 流量 f (4) =11 V1 (1,7) (4,3) Vt (2, 4)
(6, 0) (2, 4) (1, 8) (4,4) V3 V2

90 求最小费用最大流算法 *注意 在负向 弧上减 去增量 值 V1 (1,7) (4,3) Vt (2, 4) (6, 0) (2, 4) 
5 - 1 (1, 8) (4,4) V3 V2

91 求最小费用最大流算法 上一次 的赋权 图 V1 V1 (-1,7) **依据新 流量在最 短路径上 对此重求 赋权值 (4,2) Vt
(-4,2) Vs (-2, 5) (6, 0) (-2, 3) (2, 3) (-1, 8) (-4,3) V3 V2 (4,3)

92 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W(f (4)) V1 V1 (-1,7) (4,3) Vt  10 Vs
*只对增广链 (4,3) Vt  10 Vs (2, 4) (6, 0)  5 (2, 4)  4 (1, 8) (4,4) V3 V2  10

93 求最小费用最大流算法 依据新 的流量 构造又 一赋权 图 W(f (4)) V1 V1 (-1,7) (4,3) Vt (-4,3) Vs
*只对增广链 (4,3) Vt (-4,3) Vs (-2, 4) (6, 0) (2, 4) (-2, 4) (-1, 8) (-3,4) V3 V2 (3,4)

94 求最小费用最大流算法 只有出弧 没有最短路，算法结束，所得为最小费用最大流 V1 V1 (-1,7) (4,3) Vt (-4,3) Vs
(-2, 4) (6, 0) (2, 4) (-2, 4) (-1, 8) (-3,4) V3 V2 (3,4)

95 6.中国邮递员问题 6.1一笔划问题 欧拉链: 图中存在一条链, 过每边一次且仅一次. 欧拉圈: 图中存在一简单圈, 过每边一次.
欧拉图: 具有欧拉圈的图.

96 定理: 连通多重图G是欧拉图, 当且仅当G中无奇点 .
奇偶点作业法 若图中无奇点, 问题已解决; 否则: 第一可行方案的确定: 奇点配对, 找奇点间的一条链. 调整可行方案, 使重复边总长度下降

97 a)最优方案中, 每一边上最多有一条重复边. b)最优方案中, 每个圈上重复边的总权不大于圈总权的一半. 最优性判定: 满足a)和b)两条.