本章要点 了解图论的基本思想 掌握相关的基本概念 学会最短路、最大流、最小费用 最大流的解法 学会用图的工具表达思想和研究问题

Presentation on theme: "本章要点 了解图论的基本思想 掌握相关的基本概念 学会最短路、最大流、最小费用 最大流的解法 学会用图的工具表达思想和研究问题"— Presentation transcript:

1 本章要点 了解图论的基本思想 掌握相关的基本概念 学会最短路、最大流、最小费用 最大流的解法 学会用图的工具表达思想和研究问题
第二章 图论与网络分析 本章要点 了解图论的基本思想 掌握相关的基本概念 学会最短路、最大流、最小费用 最大流的解法 学会用图的工具表达思想和研究问题

2 第1节 图论的由来 哥尼斯堡小城 普雷格尔河（联想） 七桥问题 C A B D （b） （a）

3 第2节 图的基本概念 几何图有长短、曲直、角度和面积等概念，图论的“图” 只有点与线等抽象的关系概念 何谓抽象？
第2节 图的基本概念 几何图有长短、曲直、角度和面积等概念，图论的“图” 只有点与线等抽象的关系概念 何谓抽象？ 边：两点之间的连线叫做边(edge)，记为e 弧：有方向的边叫做弧(arc)，记为a

4 第2节 图的基本概念 无向图：由点集V和边集E组成的图叫做无向图，记为 有向图：由点集V和弧集A组成的图叫做有向图，记为
第2节 图的基本概念 无向图：由点集V和边集E组成的图叫做无向图，记为 有向图：由点集V和弧集A组成的图叫做有向图，记为 连通图：图中任意两点之间直接或间接地均有边相连。跟其它点没有边相连的点叫做孤立点，不含有孤立点的图叫做连通图。 链：一个连续不断的点边交替序列叫做链闭合的链叫做圈 路：方向一致的点弧交替序列叫做路，闭合的路叫做回路。

5 第3节 图的用处 例1.公司结构图

6 第3节 图的用处 例2.人际关系图 a b c e d f g

7 第3节 图的用处 例3.篮球比赛 A D C B E

8 第4节 最小树 树：一个无圈的连通图称之为树 最小树：权值最小的树叫做最小树,也称最小支撑树 树的用处：间谍组织单线联系；电话线；网线
第4节 最小树 树：一个无圈的连通图称之为树 最小树：权值最小的树叫做最小树,也称最小支撑树 树的用处：间谍组织单线联系；电话线；网线 还有什么用处？

9 第4节 最小树 求最小支撑树的破圈法 V1 V5 3 V3 V7 6 6 5 3 4 6 2 V2 2 V4 V6

10 最小树软件

11 最小树软件

12 第5节 最短路 最短路问题 路，是定义在有向赋权图上的，一系列首尾相接的弧就构成了路，权值最小的路叫做最短路 V1 8 6 3 5 2 4
第5节 最短路 最短路问题 路，是定义在有向赋权图上的，一系列首尾相接的弧就构成了路，权值最小的路叫做最短路 V1 8 6 3 5 2 4 V2 V3 V4 V6

13 最短路的解法 V2 8 4 V4 V1 2 5 3 6 V3 V6 T(V1,6) T(V3,5) P(V3,5) T(V2,13)

14 例题2.6 设备更新问题 某公司签署了一项合同，生产一种新产品，为期五年。为此需要购买一台新设备，并在每年年初决定续用还是更新。续用，需要支付维修费用（第i年维修费用Ci元）；更新，需要支付购置费（第i年购置费Ki元）。 年份i 1 2 3 4 5 购置费Ki 11 12 13 维修费Ci 6 8 18

15 问题分析 59 41 30 22 22 23 16 16 17 17 18 V1 V2 V3 V4 V5 V6 23 30 31 41

16 费用测算表 j i 1 2 3 4 5 16 22 30 41 59 — 17 23 31 18

17 最短路软件求解

18 最短路软件求解

19 第6节 最大流 网速太慢、出门塞车——这是什么问题？ 流量太大，容量太小！ 怎么解决？扩容！ 网络是复杂的，全面扩容吗？还是扩某一段？
第6节 最大流 网速太慢、出门塞车——这是什么问题？ 流量太大，容量太小！ 怎么解决？扩容！ 网络是复杂的，全面扩容吗？还是扩某一段？ 制约流量的“瓶颈”因素在哪里？ 这就是“最大流”问题

20 例2.7 网络最大流 某公司从产地Vs运输产品到销地Vt,弧旁数字为Cij（fij），Cij是容量，fij是流量，如何安排才能使流量最大？
例2.7 网络最大流 某公司从产地Vs运输产品到销地Vt,弧旁数字为Cij（fij），Cij是容量，fij是流量，如何安排才能使流量最大？ V1 V2 V3 Vt 5(5) 9(4) 6(3) 10(2) 1(1) 7(6) 8(3) Vs

21 最大流的相关概念 1.网络与流： 给定一个有向图，指定了Vs为发点，Vt为收点，其余为中间点；每一条弧均给定了相应的流通能力，称为该弧的容量，记为Cij，这样的有向图称之为网络，记为D(V,A,C)。 弧（vi，vj）上的实际通过量称为该弧的流量，记为fij。整个网络从发点至收点的荷载叫做流，记为f。网络的流量记为v(f)。

22 最大流的相关概念 2.可行流： 所谓可行流，要满足下列条件： （1）容量限制条件：弧的流量不超过容量，即0≤fij≤Cij
（2）平衡条件：对于中间点：流出量=流入量，对于发点和收点则有：发点的流出量＝收点的流入量

23 最大流的相关概念 3.弧的种类 饱和弧 非饱和弧 零流弧 前向弧 后向弧

24 最大流的相关概念 4.增广链： 设f是网络D=(V,A,C)上的一个可行流， μ是从vs到vt的一条链， 若μ满足下列条件：
(1)前向弧均为非饱和弧； (2)后向弧均为非零流弧， 则称μ是关于可行流f的一条增广链。

25 最大流的相关概念 定理1：在网络D=(V,A,C)中，可行流是最大流的充分必要条件是D中不存在关于f的增广链。

26 最大流的相关概念 5.截集： 给定网络D=(V,A,C)，若点集V被分割成两个非空集合 ，使得 ,且 ，则把分离Vs和Vt的弧的集合叫做一个截集，记为 。

27 最大流的相关概念 定理2：对于任意给定的网络D=(V,A,C)，从出发点VS到收点Vt的最大流的流量必等于分割 的最小截集的截量。

28 例2.7求解： V2 9(4) 7(6) Vs 6(3) Vt 1(1) 5(5) 8(3) V1 10(2) V3 （VS, 5）

29 例2.7求解： V2 9(5) 7(7) Vs 6(3) Vt 1(1) 5(5) 8(3) V1 10(2) V3 (vs，4)

30 例2.7求解： V1 V2 V3 Vt 5(5) 9(8) 6(0) 10(5) 1(1) 7(7) 8(6) Vs

31 例2.7求解： 给Vs、V2标号之后，无法继续给Vt标号，于是过程结束，斜线切断的从Vs到Vt一方的弧即是网络的最小截集。 V2 9(8)
7(7) Vs 6(0) Vt 1(1) (Vs，+∞) 5(5) 8(6) V1 10(5) V3 给Vs、V2标号之后，无法继续给Vt标号，于是过程结束，斜线切断的从Vs到Vt一方的弧即是网络的最小截集。

32 最大流的计算机求解

33 最大流的计算机求解

34 第7节 最小费用最大流 网络中流量最大是不是极致？ 除此之外还有什么追求？ 各条弧上的费用不同，如何实现费用最低？ 这就是最小费用最大流

35 例2.8 交通网络如下图，弧旁数字为 ，问题是：如何安排各弧的流量使得网络的总费用最省？ V2 (3,7) (4,9) Vs (3,6)
交通网络如下图，弧旁数字为 ，问题是：如何安排各弧的流量使得网络的总费用最省？ V2 (3,7) (4,9) Vs (3,6) Vt (5,1) (2,5) (1,8) V1 (3,10) V3

36 例2.8求解 解题的思路是：把一张图剥离为两张图，相互参照，分别处理。把流量和费用分开考虑，一张图专门研究流量，叫做流量图G(f)；一张图专门研究费用，叫做赋权有向图W(f)。流量图是赋权有向图的依据，赋权有向图是流量图演变的指导。

37 例2.8求解 V3 V1 V2 Vs 2 4 3 5 1 图2-20（b） W(f0) V1 V2 V3 Vs 5(0) 9(0) 6(0)
10(0) 7(0) 8(0) 图2-20（a） G(f0)

38 例2.8求解 V1 V2 V3 Vs -2 4 3 5 1 -3 图2-21（b） W(f1) -1 V1 V2 V3 Vs 5(5)
9(0) 6(0) 10(5) 1(0) 7(0) 8(5) 图2-21（a） G(f1)

39 例2.8求解 V2 V1 V2 V3 Vs 5(5) 9(7) 6(0) 10(5) 1(0) 7(7) 8(5)
图2-22（a） G(f2) 4 -3 Vs -4 5 Vs 3 -2 1 3 -1 V1 V3 -3 图2-22（b） W(f3)

40 例2.8求解 -4 V3 V1 V2 Vs -2 4 3 5 -3 1 -1 图2-23（b） W(f3) V1 V2 V3 Vs 5(5)
9(8) 6(0) 10(5) 1(1) 7(7) 8(6) 图2-23（a） G(f2) 3

41 例2.8求解 由图2-23（b） W(f3) 可见，从VS到Vt已经无路可走，说明当前的流已经是最大流。
在求解过程中，始终沿着最短路调增流量，因此始终保持着最小费用。此时的最大流就是最小费用最大流。