图论及其算法 张莉 Tongji University

Presentation on theme: "图论及其算法 张莉 Tongji University"— Presentation transcript:

1

2 图论及其算法 张莉 Tongji University lizhang@tongji.edu.cn

3 §1 最小支撑树问题 1. 树：无回路的无向连通图. 一. 基本概念 2. 叶：树中度数为 1 的顶点. 3. 森林：连通分支大于 1 ，且每个连通分支均为 树的非连通图.

4 1. 例 1 ：在偏远地区，可以通过公路连接分散的村落， 但没有任何电话服务。我们希望铺设电话线路， 使得每一对村落都可以通过电话线连接 ( 不必是 直接的 ) 。沿着现存的公路铺设电话线最便宜， 问沿着哪些公路铺设电话线，可以确保每一对 村落被连接，且电话线的总长度达到最小 ( 电话 线总长度可能与安装总成本成正比 ) ？ 二. 最小生成树 解：寻找最小生成树.

5 例 2 ：假设在一个没有良好高速公路的偏远地区涌现 了几个城市，理想的是建筑足够多的高速公路， 使得城市之间或者直接通过高速公路往来，或 者可以通过去其他城市来实现彼此的互相往来. 现在我们希望成本最小化. 注 : (1) 成本最小化即：可以实现城市间的互通，同时， 每条高速路都不浪费 ( 即去掉后就不能互通了 ). (2) 不允许高速路在所研究的城市以外的某点 处连接.

6 此问题可抽象为设△ ABC 为等边三角形，，连接三 顶点的路线（称为网络）。这种网络有许多个， 其中最短路线者显然是二边之和 ( 如 AB ∪ AC). A B C 最短网络问题 : 如何用最短的线路将三部电话连起来？

7  但若增加一个周转站（新点 P ），连接 4 点的新网 络的最短路线为 PA ＋ PB ＋ PC 。最短新路径之长 N 比原来只连三点的最短路径 O 要短。  这样得到的网络不仅比原来节省材料，而且稳定性 也更好。 A BC P

8 斯坦纳（ Steiner ）最小树是可以在给定的点之外再增加 若干个点 ( 称为斯坦纳点 ) ，然后将所有这些点连起来。 如果不允许增加任何额外的点作为网络的顶点，这种最 短网络称为最小生成树。 在前面的例子中 Steiner 最小树的长为. 最小生成树的长为 2. 1968 年贝尔实验室波雷克 (Pollak) 和研究员吉尔伯特 (Gilbert) 提出如下猜想：平面上任意 n 点集，斯坦纳最 小树长与最小生成树之长的比值的最小值是.

9 1967 年前，贝尔公司按照连结各分部的最小生成树 的长度来收费。 1967 年一家航空公司戳了贝尔公司 一个大洞。当时这家企业申请要求贝尔公司增加一 些服务点，而这些服务点恰恰位于构造该公司各分 部的斯坦纳最小树需增加的斯坦纳顶点上。这使得 贝尔公司不仅要拉新线，增加服务网点，而且还要 减少收费。这一意外事件迫使贝尔公司自此以后便 采用了斯坦纳最小树原则 。 Steiner 猜想起源于在美国贝尔电话公司发生的一个 富有戏剧性的事件。

10 1. 问题描述：如村落间铺设电话线的问题. 三. Kruskal 算法 2. 算法思想 ( 贪婪算法 ) ：总是选择权最小的边.

11 3. 算法描述： 步骤 1 ：按照权的递增顺序排列图 G 的边，置集合 T 为空集. 步骤 2 ：检查排列序表中第一条未检查的边，此边被放入 T 中当且仅当它不与 T 中的边形成回路。若这条边被加 入 T 中，进入步骤 3 ，否则重复步骤 2. 步骤 3 ：若 T 有 n-1 条边，则停止， T 即为所找的最小支撑 树，否则，进入步骤 2.

12 5. 实例： b 53 d 8 54 e 12 10 70 22 a 63 c 解： ab—cd—de--bd 排序： ab, cd,de,ec,bd,be,ac,ae

13 四. Prim 算法 1. 算法思想 ( 贪婪算法 ) ： 从顶点出发，对任意点，总是选择与其关联的 权最小的边放入 T 中.

14 2. 算法描述： 步骤 1 ：置集合 T 为空集, 任选一点 v 放入树 T 中. 步骤 2 ：将连接 T 中的点与 V-V(T) 中的点的所有边中权最小 的边加入到 T 中，若权最小的边有多条，任选其一， 若不可能把任一条边加入到 T 中，则停止，输出 G 非 连通. 步骤 3 ：若 T 有 n-1 条边，则停止， T 即为所找的最小支撑 树，否则，重复步骤 2.

15 5. 实例： b 53 d 8 54 e 12 10 70 22 a 63 c 解： ab—bd—dc--de 1). 选点 a,T={a}, 选出 ab, 2). T={ab}, 选出 bd, 3). T={ab,bd}, 选出 dc, 4). T={ab,bd,dc}, 选出 de

16 §2 最短路径问题 一. 简介 1. 问题：寻找网络中两个顶点之间的最短路径问题. 2. 实例：希望利用公路开车从上海到北京，希望路程 最短. 注： (1) 点 — 城市，边 — 公路， 权 — 距离，连通赋权图. (2) 所有权均非负.

17 二. Dijkstra 算法 (1959) 1. 算法思想：

18 2. 算法描述 ( 从 u 0 到 u n-1 ) ：

19 3. 实例： a 3 d 3 5 x 8 b 2 1 y 4 e 8 c 1 1) S 0 ={x}, 其他 l(v)=∞,l(x)=0 2) l(a)=3,l(b)=8,l(c)=4,S 1 ={x,a} 3) l(b)=8,l(c)=4,l(d)=6, S 2 ={x,a,c} 4) l(b)=8,l(e)=5,l(d)=6,S 3 ={x,a,c,e} 5) l(d)=6,l(b)=7,l(y)=13, S 4 ={a,c,e,d} 6) l(b)=7,l(y)=11,S 5 ={a,c,e,d,b} 7) l(y)=11,S 6 ={a,c,e,d,b,y}

20 一笔画问题 )  在哥尼斯堡有七座桥将普雷格尔 河中两个岛及岛与河岸连接起来 ( 如图 ) 。 Euler 在 1736 年访问 Konigsberg 时，他发现当地的市民正从事一项 非常有趣的消遣活动。这项有趣的消遣活动是在星期六作一次走 过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须 是同一地点。 Euler 证明了不可能存在这样的路线。

21 三. 中国邮递员问题 (1962 ，管梅谷 ) 1. 问题：邮递员每天从邮局选好邮件，送到他所管辖 的邮区的客户手中，再返回邮局，他每天必须走过每 条街道至少一次，问如何选择邮递路线，使得他走过 的投递总行程最短？ 2. 模型：非负赋权图 G ： 顶点 ---- 交叉口或终端，边 ---- 街道，权 ----- 街道长度， 此即求图的通过每条边至少一次的闭途径, 称为 G 的环 游.

22 3. 最优环游：即具有最小权的环游. 注： (1) 若 G 是欧拉图，则欧拉环游即最优. (2) 若 G 不是欧拉图，则重复边权和最小的即最优. 4. 定理：设 P 是赋权连通图 G 中一条包含 G 的所有边 至少一次的闭途径，则 P 最优当且仅当它满足以下两 个条件： (1) P 中没有二重以上的边. (2) 对 G 中的任意圈 C ，其重复边集 E 的长度之和不 超过圈长的一半，即 w(E)≤1/2w(C).

23 步骤 1 ：取 V 0 ={v|d(v) 为奇数 } ， (G 中一定有偶数个奇点 ). 步骤 2 ：对 V 0 中任意 u,v ，求 d(u,v), ( 用 Dijkstra 算法 ). 步骤 3 ：构造完全图 K |v 0 |, 其中边 {u,v} 的权为 d(u,v). 步骤 4 ：求 K |v 0 | 中的权最小的完美匹配 M. 步骤 5 ：在 G 中求以 M 中每条边的两端点为端点的最短路. 步骤 6 ：将步骤 5 中所求的每条最短路上的每条边都添上 一条等权的 “ 倍边 ” ，得到新图 G‘. 步骤 7 ：在新图 G’ 中用 Fleury 算法求欧拉环游，则即为 G 的最优环游. 5. Edmonds-Johnson 算法

24 三. 旅行商问题 1. 问题：设有 n 个城镇，已知每两个城镇之间的距离， 一个售货员自一个城镇出发巡回售货，问他该如何 选择路线，能使每个城镇经过一次且仅一次，最后 再回到出发地而且行程最短。 2. 模型：此即在赋权完全图中，寻找最小权的哈密尔 顿圈. 注：这个问题是 NPC 的.

25 3. 近似算法 ( 最邻近算法 )

26 4. 实例：求下列赋权完全图的最优 Hamilton 回路. A 2 1 3 4 B 5 E 9 7 10 6 C 8 D 解： ACEBDA: 权和 25 BACEDB: 权和 25 CABEDC ： 权和 22 DACEBD ： 权和 25 EACDBE: 权和 27 所选初始点不同，得到的近似解也不同.

27 5. 修改方法：最邻近插入法 思想方法：每次迭代中都让其构成一个闭的旅行路线， 它由多个阶段形成，每次都比上一次多一个顶点。 求解时，在已建立旅程之外的顶点中，寻找最邻近 于旅程中某个顶点的顶点，将其插入该旅程中，并 使增加的距离尽可能小，当全部顶点收入这个旅程 后，就找到了最短哈密尔顿回路的近似解.

28 实例： A 2 1 3 4 B 5 E 9 7 10 6 C 8 D (1) 初始点为 A ，组成闭旅程 AA ， 下一阶段，最邻近 A 的顶点为 C ， 建立闭旅程 ACA, 再寻找最邻近 A 与 C 的顶点 B ，组成闭旅程 ACBA. (2) 从 D,E 中找一个最邻近 ACBA 的顶点 D ， 将其插入，分别得到 ACDBA( 权和 20) ， ACBDA(23),ADCBA(23), 选择 ACDBA. (3) 最后将 E 插入 ACDBA, 有 4 个位置 AECDBA(30),ACEDBA(25),ACDEBA(22),ACDBEA( 27) ，选择最小的 ACDEBA(22) 即为所求.

29 网络流问题 随着中国经济快速的增长，城市化是未来中国的发 展方向。我们要把物流业作为战略重点列入要大力 发展的新兴服务产业。如何制定一个运输计划使得 生产地到销售地的产品输送量最大？这就是一个网 络最大流问题。

30 6. Ford-Fulkerson 算法 (1) 标号过程

31 (2) 调整过程

32 8. 算法思想：从任何一个可行流 ( 如零流 ) 出发，寻 找增广路，调节修正流量. 缺陷：符号顺序任意，导致增广路任意. 改进：最短增广路算法. 注：算法最终停止时， S 为已标号点， T 为未标号 点， C(S, T) 即为最大流.

33 7. 实例 v 1 (5,2) v 4 (5,5) (3,3) (4,2) x (4,2) v 2 (3,0) v 5 (3,3) y (3,2) (2,2) (5,4) v 3 (2,2) v 6 (-v5,2) (+v1,2) v 1 (5,2) v 4 (5,5) (3,3) (4,2) x (4,2) v 2 (3,0) v 5 (3,3) y ( △, ∞) (+x, 2) (+v2,2) (+v4,2) (3,2) (2,2) (5,4) v 3 (2,2) v 6 (+x,1) 找到一条 x-y 增广路 P=xv 2 v 5 v 1 v 4 y, 调整 P 中边的流量 : v 1 (5,4) v 4 (5,5) (3,1) (4,4) x (4,4) v 2 (3,2) v 5 (3,3) y (3,2) (2,2) (5,4) v 3 (2,2) v 6 再重新标号，只能从 x 标到 v 3 ， S={x,v 3 },T={v 1,v 2,v 4, v 5,v 6,y},C(S,T)=11=v(f).