图论和算法.ppt

8.算法思想：从任何一个可行流(如零流)出发，寻找增广路，调节修正流量. 缺陷：符号顺序任意，导致增广路任意. 改进：最短增广路算法. 注：算法最终停止时，S为已标号点，T为未标号点，C(S, T)即为最大流. 7. 实例 v1 (5,2) v4 (5,5) (3,3) (4,2) x (4,2) v2 (3,0) v5 (3,3) y (3,2) (2,2) (5,4) v3 (2,2) v6 (-v5,2) (+v1,2) v1 (5,2) v4 (5,5) (3,3) (4,2) x (4,2) v2 (3,0) v5 (3,3) y (△, ∞) (+x, 2) (+v2,2) (+v4,2) (3,2) (2,2) (5,4) v3 (2,2) v6 (+x,1) 找到一条x-y增广路P=xv2v5v1v4y,调整P中边的流量: v1 (5,4) v4 (5,5) (3,1) (4,4) x (4,4) v2 (3,2) v5 (3,3) y (3,2) (2,2) (5,4) v3 (2,2) v6 再重新标号，只能从x标到v3，S={x,v3},T={v1,v2,v4, v5,v6,y},C(S,T)=11=v(f). * * * * * * * 图论及其算法 张莉 Tongji University lizhang@tongji.edu.cn §1 最小支撑树问题 1. 树：无回路的无向连通图. 一.基本概念 2. 叶：树中度数为1的顶点. 3. 森林：连通分支大于1，且每个连通分支均为树的非连通图. 1. 例1：在偏远地区，可以通过公路连接分散的村落，但没有任何电话服务。我们希望铺设电话线路，使得每一对村落都可以通过电话线连接(不必是直接的)。沿着现存的公路铺设电话线最便宜，问沿着哪些公路铺设电话线，可以确保每一对村落被连接，且电话线的总长度达到最小(电话线总长度可能与安装总成本成正比)？ 二.最小生成树 解：寻找最小生成树. 例2：假设在一个没有良好高速公路的偏远地区涌现了几个城市，理想的是建筑足够多的高速公路，使得城市之间或者直接通过高速公路往来，或者可以通过去其他城市来实现彼此的互相往来. 现在我们希望成本最小化. 注: (1)成本最小化即：可以实现城市间的互通，同时，每条高速路都不浪费(即去掉后就不能互通了). (2)不允许高速路在所研究的城市以外的某点处连接. 此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和(如AB∪AC). A B C 最短网络问题: 如何用最短的线路将三部电话连起来？ 但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。 这样得到的网络不仅比原来节省材料，而且稳定性也更好。 A B C P 斯坦纳（Steiner）最小树是可以在给定的点之外再增加 若干个点(称为斯坦纳点)，然后将所有这些点连起来。 如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。 在前面的例子中Steiner最小树的长为 . 最小生成树的长为2. 1968年贝尔实验室波雷克(Pollak)和研究员吉尔伯特 (Gilbert)提出如下猜想：平面上任意n点集，斯坦纳最 小树长与最小生成树之长的比值的最小值是 . 1967年前，贝尔公司按照连结各分部的最小生成树的长度来收费。1967年一家航空公司戳了贝尔公司一个大洞。当时这家企业申请要求贝尔公司增加一些服务点，而这些服务点恰恰位于构造该公司各分部的斯坦纳最小树需增加的斯坦纳顶点上。这使得贝尔公司不仅要拉新线，增加服务网点，而且还要减少收费。这一意外事件迫使贝尔公司自此以后便采用了斯坦纳最小树原则 。 Steiner猜想起源于在美国贝尔电话公司发生的一个富有戏剧性的事件。 1. 问题描述：如村落间铺设电话线的问题. 三. Kruskal算法