下载文档原格式
最小分割算法1.什么是最小分割算法？最小分割算法是一种算法，用于将某个问题分成多个子问题，并找到最小的分割成本。
这个算法通常用于网络流平衡问题，如在一组节点之间平衡网络流量，以最小化网络的总成本。
最小分割算法也可以用于其他问题，如图像分割、计算机辅助设计和图形算法等。
2.最小分割算法的应用2.1网络流平衡问题网络流平衡问题通常用于网络预测、流量优化和计算机网络管理等领域。
在这种问题中，数据流必须在网络中沿着某个特定的路径流动，以便满足各种需求和限制。
最小分割算法可用于最小化网络总成本，并提高数据流的效率。
2.2图像分割图像分割是一种常见的计算机视觉技术，用于将图像分成不同的区域。
最小分割算法可用于找到最小的分割成本，并将图像中的对象分离开。
此外，最小分割算法还可以用于视频序列分割和图形卡通化等领域。
2.3计算机辅助设计计算机辅助设计（CAD）需要快速、准确地处理大量复杂的图形数据。
最小分割算法可以用于图形数据分割和组合，从而提高CAD系统的效率。
2.4图形算法图形算法通常用于处理和分析二维和三维图形数据。
最小分割算法可以用于图形数据分割和分离，以便更好地分析和处理图形数据。
这对于图像处理、计算机视觉和计算机动画等领域都是非常重要的。
3.最小分割算法的实现方式最小分割算法有多种实现方式。
其中比较常用的基于最大流的实现方式。
在这种实现方式中，最小分割算法使用网络最大流算法求解网络流平衡问题。
它通过不断增加网络中的流量来寻找最小分割成本。
基于最大流的最小分割算法的步骤如下：步骤1：将源节点和汇节点之间的最小流量设置为0。
步骤2：使用最大流算法在网络中找到最大的流量。
步骤3：把具有最大流量的路径上的流量从网络中移除。
步骤4：重复步骤2和步骤3直到源节点和汇节点不再连通。
步骤5：寻找沿着连接源节点和汇节点的路径的最小割，以找到最小分割成本。
4.总结最小分割算法是一种用于将某个问题分成多个子问题并找到最小的分割成本的算法。
数据结构最短路径算法数据结构是计算机科学中非常重要的概念之一，它涉及到了组织和管理数据的方法和原则。
数据结构为我们提供了一种组织和存储数据的方式，以便于在算法中使用和操作数据。
在实际的计算机应用中，我们经常需要在图、网络、地图等复杂结构中找到最短路径。
因此，设计高效的最短路径算法是数据结构中一个重要的问题。
最短路径算法是一种计算从一个节点到另一个节点最短路径的方法。
最短路径算法的应用非常广泛，例如，在网络路由中，一个路由器需要找到从源节点到目标节点的最短路径，以便将数据包转发到目标节点；在地图导航中，我们需要找到从出发地到目的地的最短路径，以便为用户提供最佳的导航方案。
最短路径算法有许多不同的实现方法，每种方法都基于不同的数据结构和算法原理。
下面介绍几种常见的最短路径算法以及它们使用的数据结构。
1. Dijkstra算法：Dijkstra算法是最常用的最短路径算法之一、它基于图的广度优先（BFS）和贪心算法的思想，用于计算一个节点到所有其他节点的最短路径。
Dijkstra算法使用优先队列数据结构来维护每个节点的最短路径估计值，并根据估计值进行节点的选择和更新。
该算法的时间复杂度为O((V+E)logV)，其中V是节点数量，E是边数量。
2. Bellman-Ford算法：Bellman-Ford算法是另一种常见的最短路径算法。
它基于图的深度优先（DFS）和动态规划的思想，可以处理有负权边的图。
Bellman-Ford算法使用一个一维数组来保存每个节点的最短路径估计值，并使用松弛（relax）操作来更新节点的最短路径。
它的时间复杂度为O(VE)，其中V是节点数量，E是边数量。
3. Floyd-Warshall算法：Floyd-Warshall算法是一种用于计算所有节点对之间最短路径的算法。
它基于动态规划的思想，适用于有向图和无向图的最短路径问题。
Floyd-Warshall算法使用一个二维数组来保存任意两个节点之间的最短路径，并通过计算中间节点，逐步更新最短路径。
最短路径算法最短路径算法是一类用来求解最短距离、最低成本路线的算法，它是很重要的应用性算法之一。
本算法旨在在一些类图形（GG）网络中找到两个顶点之间的最短路径，这种网络必须适合某种最短路径算法，如果GG网络不能很容易地被求解，仍然可以以一定比例增大网络，从而使之满足最短路径的求解要求。
最短路径算法有许多种，其中最常用的有贝尔曼—福德算法（贝尔曼—福特算法）和迪杰斯特拉算法（Dijkstra's Algorithm）。
这两种算法都是由一个名叫“道·塞夫·贝尔曼”的德国数据处理专家在20世纪50年代初发明的。
贝尔曼—福德算法应用条件较广，可以求解任意类型网络的最短路径，并且可以在常数时间内完成。
而迪杰斯特拉算法只在GG网络上才能实施，且复杂度比贝尔曼—福德算法高。
贝尔曼—福德算法（也称福德算法）是求解最短路径问题的经典算法，它可以用来求解任意复杂网络两点间最短路径问题。
福德算法的思想是，对于图G=(V,E)中每个顶点，自底向上进行推导，将其分为两步：第一步，构造顶点的松弛树；第二步，搜索最短路径。
主要有以下几步：1、初始化：令v∈V，令d(v)=∞、v(v)=∅，令V0={v1}，有任一源点v；2、松弛：重复以下步骤至V0=V：a）对V0内任一顶点vt，改进d(vt)；b）对所有顶点vn∉V0，改进d(vn)；c）将使d变小的顶点vd加入V0；3、搜索最短路径：找出最短路径，如d(u)<∞，u就存在于最短路径树上，由它的v(u)到达；4、结束：当得到V0=V时，算法结束。
另外，迪杰斯特拉算法（Djkstra's Algorithm）也是一种常用的最短路径算法，为了求解图上任意两点之间的最短路径，提出了一个算法。
特别适用于GG网络。
具体的算法步骤如下：1、初始化：取一给定节点作为源节点，用一个标志数组S[v]（v为网络中节点）存放已求出最短路径的节点，用一个数组D[v]存放源节点到节点v的最短路径长度，D[v]初始化为有向边 <u,v>的权值；2、遍历：找到D[v]中的最小值min，找到此min值对应的节点v1，即可将v1加入到数组S中，表示此节点v1的最短路径已求出；3、更新：将以v1为中间点的<u,v>的有向边的权重值加上D[v1]作为新的最短路径长度乘于 D[v] 中取出；4、重复：重复步骤2、3，直至D[v]中所有值均被取出；5、结束：若所有节点都被取出，则表示最短路径求解完成，算法结束。
求最短路径树的一个新算法
最近，一项有趣的算法——最短路径树算法得到了广大网
友的关注。
该算法通过引入不同的计算机网络拓扑结构，使用
特定技术来求解最短路径问题，被认为是网络规划中的一种省
事办法。
最短路径树算法是一种基于图结构的计算机网络拓扑结构，主要是利用节点间的连接结构来进行数据搜索、传输和路由转
发工作。
该算法可以大大缩短搜索或路由的时间，快速计算出
最短的路径或者最短的路径树，从而可以显著改善网络拓扑的
性能。
为了充分利用该算法的优势，我们提出了一种新的最短路
径树算法，可以在单线程或多线程模式下实现更高效的网络传输。
新算法通过构建一个有向多边图，具有节点权重的无向图，根据不同的路径的权重，动态的更新路径权重，确定最短路径树，在传输和路由转发过程中大幅减少传输时间。
此外，为了实现并行计算，新算法还会采取双指针的分段
处理方法，从而更有效地实现多线程最短路径树运算，尽可能
地减少网络拓扑时间开销。
通过使用新算法，网络拓扑数据能
够快速进行更新，依据节点间连接结构动态判断并合理地构建
最短路径树，实现更高效和更可靠的网络拓扑规划和传输服务。
简述几种常用的最短路径算法摘要：随着社会的发展，最短路径问题在现实生活中占据的地位越来越重要。
求解这一类问题的方法有很多，包括Floyd算法、Dijkstra算法、Bellman-Ford算法、动态规划算法和智能优化算法。
其中较为常用的是Floyd算法、Dijkstra算法和Bellman-Ford算法。
本文将简单介绍这三种最短路径算法，通过比较各种方法的优劣使对其有更进一步的认识和学习。
关键字：最短路径；最短路径算法；Floyd算法；Dijkstra算法；Bellman-Ford算法随着计算机科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。
也正因为最短路径问题在实际生产生活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。
1.最短路径概述最短路径问题是指在一个赋权图的两个节点之间找出一条具有最小权的路径，这是图论的描述，也是图论中研究的一个重要问题。
现实生活中我们可以看到这些最短路径问题的例子，公交车辆的最优行驶路线和旅游线路的选择等；军事领域中也有应用，作战部队的行军路线等问题就与寻找一个图的最短路径密切相关，因此对最短路径问题的深入研究和广泛应用具有重要意义和实用价值。
在线路优化问题中，如果优化指标与路程的相关性较强，而和其他因素相关性较弱时，即以最短路程为准则，则考虑转化为最短路径问题。
比如军事行军线路选取时，假如从出发地到目的地之间有多种线路可以选取，危险指数在预测概率相等时，就要考虑最短路径问题。
2.最短路径算法概述最短路径算法问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
算法具体的形式包括：确定起点的最短路径问题- 即已知起始结点，求最短路径的问题。
确定终点的最短路径问题- 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。
在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
软件设计算法知识点软件设计算法是指在软件开发过程中，为了解决特定问题而设计的一系列计算步骤和规则。
它们用于优化程序的效率、资源利用和解决各种计算问题。
本文将介绍几个常见的软件设计算法知识点。
一、排序算法排序算法是一种将一组数据按照特定规则进行排列的算法。
在软件设计中，排序算法经常用于对数据进行排序和查找。
下面介绍两种常见的排序算法。
1.1 冒泡排序冒泡排序是一种简单的排序算法，它通过重复地交换相邻元素来排序。
具体步骤如下：（1）比较相邻的两个元素，如果第一个元素大于第二个元素，则交换它们的位置；（2）重复步骤1，直到所有元素都已排序。
冒泡排序的时间复杂度为O(n^2)，其中n为待排序的元素个数。
1.2 快速排序快速排序是一种高效的排序算法，它基于分治的思想。
具体步骤如下：（1）选择一个基准元素；（2）将数组分成两部分，使得左边的元素都小于基准元素，右边的元素都大于基准元素；（3）递归地对左右两部分进行快速排序。
快速排序的时间复杂度为O(nlogn)，其中n为待排序的元素个数。
二、查找算法查找算法是一种在数据集合中查找特定元素的算法。
在软件设计中，查找算法经常用于在大量数据中快速检索目标元素。
下面介绍两种常见的查找算法。
2.1 二分查找二分查找是一种对有序数组进行查找的算法，它通过将目标值与数组中间元素进行比较，从而缩小查找范围。
具体步骤如下：（1）确定数组的中间元素；（2）如果中间元素等于目标值，则查找成功；（3）如果中间元素大于目标值，则在数组的左半部分继续查找；（4）如果中间元素小于目标值，则在数组的右半部分继续查找；（5）重复步骤2至步骤4，直到找到目标元素或查找范围为空。
二分查找的时间复杂度为O(logn)，其中n为数组的元素个数。
2.2 哈希查找哈希查找是一种通过哈希函数将目标值映射到数组索引的查找算法，它具有快速定位目标值的优点。
具体步骤如下：（1）构建哈希表，将目标值通过哈希函数映射到数组索引；（2）如果哈希表中对应索引位置为空，则查找失败；（3）如果哈希表中对应索引位置不为空，则进行线性查找，直到找到目标元素或查找范围为空。
最短路径算法及应用最短路径算法通常基于图的表示，其中图由节点和边组成。
每个节点代表一个位置，每条边代表两个位置之间的连通关系。
每条边都有一个权重，表示该路径的长度、成本或时间等。
最短路径算法的目标是找到从起始节点到目标节点的最短路径，使得路径上所有边的权重之和最小。
最短路径算法有多种实现方法，包括迪杰斯特拉算法、贝尔曼-福特算法和A*算法等。
迪杰斯特拉算法是一种广泛使用的算法，它适用于无负权边的图。
该算法通过维护一个候选集合，逐步选择离起始节点最近的节点，并更新与其相邻节点的最短路径。
该过程重复直到找到到目标节点的最短路径。
另一种常见的最短路径算法是贝尔曼-福特算法，该算法适用于存在负权边的图。
它通过反复迭代图的所有边来不断更新每个节点的最短路径估计值。
该算法的一个特点是，它可以处理存在负权环的图，并且可以检测到这种情况。
A*算法是一种常用于路径规划的启发式算法。
它根据每个节点的预估成本（通常使用启发函数）来选择下一个要探索的节点。
该算法通过评估每个节点的实际距离加上启发式函数的估计距离，来选择最有希望导致最短路径的节点。
1.路径规划：最短路径算法可以被用于规划最短的路径，以避开交通拥堵，节约时间和成本。
2.交通网络优化：最短路径算法可以用于优化交通网络，找到使整个网络中车辆流量最小的路径。
3.通信网络路由：在通信网络中，最短路径算法可以被用于确定数据包传输的最短路径，以最大程度地减少延迟和拥塞。
4.GPS导航：GPS导航系统使用最短路径算法来计算最短和最快的路径，以引导驾驶员到目的地。
5.配送服务：在配送服务领域，最短路径算法可以被用于确定最佳的交付序列，以减少总运输时间和成本。
6.网页排名：在引擎中，最短路径算法可以被用于计算网页之间的关联程度，以确定网页的排名和结果排序。
总而言之，最短路径算法是图论中重要的算法之一，被广泛应用于各种领域。
通过找到最短路径，这些算法可以帮助我们节约时间、成本和资源，并优化各种系统的性能。
数据结构的应用的最小生成树算法与最短路径算法数据结构的应用：最小生成树算法与最短路径算法在计算机科学中，数据结构是指组织和存储数据的方式。
数据结构广泛应用于算法设计和问题解决中，其中最小生成树算法和最短路径算法是两个关键的应用之一。
本文将就这两个算法进行详细介绍与分析。
一、最小生成树算法最小生成树算法用于解决无向图中选择一棵具有最小权重的生成树的问题。
生成树是指一个无向图的子图，它包含图中的所有顶点，但是只包含足以构成一棵树的n-1条边。
最小生成树算法的目标是找到权重之和最小的生成树。
1. Kruskal算法Kruskal算法是一种常用的最小生成树算法。
它的基本思想是按照边的权重递增顺序选择边，并且如果加入该边会形成回路，则不加入该边。
算法步骤：（1）将所有边按照权重从小到大进行排序。
（2）初始化一个空集合，用于存放生成树的边。
（3）遍历排序后的边，如果加入该边不会形成回路，则将该边加入生成树集合。
（4）重复步骤3直到生成树包含n-1条边。
Kruskal算法的时间复杂度为O(ElogE)，其中E为边的数量。
该算法常用于解决网络设计、电路布线等问题。
2. Prim算法Prim算法也是一种常用的最小生成树算法。
与Kruskal算法不同的是，Prim算法以顶点为基础，每次选择与当前生成树距离最近的顶点加入生成树。
算法步骤：（1）选择任意一个顶点作为起始点，并将该顶点加入生成树。
（2）对于生成树之外的顶点，计算其与生成树上顶点的边的权重，并找到其中权重最小的边对应的顶点。
（3）将权重最小的边添加到生成树，并将对应的顶点加入生成树。
（4）重复步骤2和步骤3直到生成树包含n-1条边。
Prim算法的时间复杂度为O(n^2)，其中n为顶点的数量。
该算法常用于解决通信网络、电力网络等问题。
二、最短路径算法最短路径算法用于解决在图中找到两个顶点之间的最短路径的问题。
最短路径可以根据边的权重来定义，也可以根据边的长度、时间等其他因素来定义。
算法最短路径最短路径算法是一种在图中寻找两个节点之间最短路径的方法。
它在许多实际应用中都有广泛的应用，比如导航系统、网络路由和物流规划等。
本文将介绍几种常见的最短路径算法，并对它们的原理和应用进行详细解析。
一、Dijkstra算法Dijkstra算法是最短路径算法中最常用的一种。
它通过不断更新起始节点到其他节点的距离，逐步找到最短路径。
具体步骤如下：1. 初始化起始节点的距离为0，其他节点的距离为无穷大。
2. 选择距离起始节点最近的节点，并标记为已访问。
3. 更新与该节点相邻节点的距离，如果经过该节点到达相邻节点的距离更短，则更新距离。
4. 重复步骤2和3，直到所有节点都被访问过或者没有可更新的节点。
Dijkstra算法的时间复杂度为O(V^2)，其中V为节点的数量。
它适用于没有负权边的图，可以求解单源最短路径问题。
二、Bellman-Ford算法Bellman-Ford算法是一种可以处理带有负权边的图的最短路径算法。
它通过对所有边进行松弛操作，逐步逼近最短路径。
具体步骤如下：1. 初始化起始节点的距离为0，其他节点的距离为无穷大。
2. 对所有边进行V-1次松弛操作，其中V为节点的数量。
3. 检查是否存在负权环，如果存在，则说明图中存在无穷小的最短路径，算法结束。
Bellman-Ford算法的时间复杂度为O(VE)，其中V为节点的数量，E为边的数量。
它适用于解决单源最短路径问题，并且可以处理带有负权边的图。
三、Floyd-Warshall算法Floyd-Warshall算法是一种可以求解任意两个节点之间最短路径的算法。
它通过动态规划的思想，逐步更新节点之间的距离。
具体步骤如下：1. 初始化节点之间的距离矩阵，如果两个节点之间有直接边，则距离为边的权重，否则为无穷大。
2. 对于每一个节点k，遍历所有节点对(i, j)，如果经过节点k的路径比直接路径更短，则更新距离矩阵中的值。
3. 重复步骤2，直到所有节点对的距离都被更新。
数据结构中的最小割算法解析最小割算法是一种用于在图中找到最小割（最小割是指将图分成两个部分，使得两部分之间的边集权重之和最小）的有效方法。
在数据结构领域，最小割算法是一种重要的算法，被广泛应用于网络流问题、图像分割和社交网络分析等领域。
本文将详细解析最小割算法的原理、应用场景和具体实现。
一、最小割算法原理最小割算法的核心原理基于网络流的概念和图的割。
在图论中，网络流是指在一个带有容量限制的图中，从源节点到汇节点的流量传输问题。
而割是将图中的顶点分为两个不相交的集合，并将这两个集合分别称为源集合和汇集合，边的权重被称为割的容量。
最小割算法通过寻找图中的割，使得割的容量最小来达到最小割的目标。
最小割算法有多种具体实现方法，其中最著名的算法是Ford-Fulkerson算法和Edmonds-Karp算法。
Ford-Fulkerson算法通过不断寻找增广路径，即从源节点到汇节点的一条路径，使得路径上的边容量可以增加，从而提高流量。
而Edmonds-Karp算法则通过BFS（广度优先搜索）寻找增广路径，具有更高的效率。
二、最小割算法的应用场景最小割算法在实际应用中有广泛的应用场景，主要包括以下几个方面：1. 网络流问题：最小割算法被广泛应用于网络流问题中，如最大流问题、最小费用最大流问题和最大权闭合子图问题等。
通过寻找最小割，可以在网络中找到最大的流量或最小的流量。
2. 图像分割：最小割算法可以将图像分割为多个区域，从而实现图像语义分割、边缘检测和目标识别等应用。
3. 社交网络分析：最小割算法可以应用于社交网络中的群体发现、社区发现和信息传播等领域。
通过寻找最小割，可以将社交网络分割为不同的社区，从而更好地理解和分析社交网络的结构和特征。
三、最小割算法的具体实现最小割算法的具体实现与选择的算法密切相关。
在这里，我们以Ford-Fulkerson算法为例进行介绍。
1. Ford-Fulkerson算法：a. 初始化流量网络，设置初始流量为0。
1000-9825/2003/14(05)0885© 2003 Journal of Software 软件学报Vol.14, No.5 一类实际网络中的最小截算法∗张宪超+, 万颖瑜, 陈国良(中国科学技术大学计算机科学与技术系,安徽合肥 230027)(国家高性能计算中心(合肥),安徽合肥 230027)Approaches to the Minimum Cut Problem in a Class of Practical NetworksZHANG Xian-Chao+, WAN Ying-Y u, CHEN Guo-Liang(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China) (National High Performance Computing Center at Hefei, Hefei 230027, China)+ Corresponding author: E-mail: xczhang081@Received 2002-04-12; Accepted 2002-09-11Zhang XC, Wan YY, Chen GL. Approaches to the minimum cut problem in a class of practical networks. Journal of Software, 2003,14(5):885~890./1000-9825/14/885.htmAbstract: The minimum cut problem between two distinguished nodes in a undirected planar network with limited capacities on both nodes and edges is discussed. The traditional method reduces the node-edge-capacity problem to an only-edge-capacity probl em. But this method does not maintain the planarity of a planar network, so the special qualities of planar networks can not be used. The traditional algorithm runs in time O(n2log n). In this paper, approaches that fully use the planarity of planar networks are presented. For an s-t network in which the source and the sink are on a same face, the minimum cut problem to the shortest path problem in a planar graph is reduced, thus an algorithm that runs in time O(n) is obtained. For a common planar network, a nother method that reduces the node-edge-capacity problem to an only-edge-capacity problem is presented. This reduction method does not destroy the planarity of a planar network, so that the problem can be solved in time O(n log n).Key words: combinatorial optimization; network optimization; maximum flow; minimum cut; planar graph摘 要: 讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n2log n)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问∗ Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1999032700 (国家重点基础研究发展规划(973))第一作者简介: 张宪超(1971－),男,辽宁朝阳人,博士,主要研究领域为网络优化,组合优化,算法设计与分析,并行分布式计算.886Journal of Software 软件学报 2003,14(5)题在O (n log n )时间内获得解决.关键词: 组合优化;网络优化;最大流;最小截;平面图中图法分类号: TP301 文献标识码: A 最小截问题是一个经典的组合优化问题.它和其对偶问题——最大流问题是计算机科学和运筹学等领域的重要内容,在电力、交通、通信、计算机网络等领域有着广泛的应用.文献[1]对此作了很好的总结.对一般网络中的最小截,目前最好算法的时间复杂度为O (nm log(n 2/m )),其中n 为网络的节点数,m 为边数[2~4].由于在交通、通信、VLSI 等许多应用领域中存在大量平面网络[5],平面网络中的问题被广泛地进行了研究[5~12].通过开发平面网络的特殊性质,可以得到比一般算法更快的算法.对源和汇共面的平面网络(称为s -t 网络),可以在)(n O 时间内获得最小截[12].对一般的平面网络,现在最好的时间复杂度为)log (n n O [5].目前,在最小截和最大流问题的研究中只考虑了网络的边有容量的情况.在实际的网络中,边和节点都会有容量的限制.由于可以通过把网络中有容量的节点分裂成一条边的简单方法,把节点和边都有容量的网络中的最小截问题转化为仅边有容量的问题[1,13,14],因此对一般网络来说,只需考虑仅边有容量就可以了.但是对于平面网络来说,这种转化不能保持网络的平面性[14].这样,对于平面网络中节点和边都有容量的问题,目前最好算法的时间复杂度为)log (2n n O (即))/log((2m n nm O [3],注意到平面网络中)(n O m =).本文在仅边有容量的平面网络中的最小截问题算法的启发下,得到了节点和边都有容量的无向平面网络中的最小截算法.在s -t 网络中,把最小截问题转化为平面图中的两点间的最短路径问题,这样,利用文献[12]中)(n O 时间的平面图最短路径算法,可以在)(n O 内计算出最小截.对一般的平面网络,得到了一个新的把节点和边都有容量的问题转化为仅边有容量的问题的方法,新的转化方法保持了网络的平面性.这样,利用文献[5]中仅边有容量的问题的算法,可以使问题在)log (n n O 时间内获得解决.1 问题描述和预备知识定义1. 本文所指的网络是一个无向加权图),(E V G =,其中V 为G 的节点集合,E 为边集合.在G 中指定两个节点s 和t ,分别称为源和汇.其他节点称为中转节点.中转节点v 上的权0)(≥v c 称为v 的容量.边E j i e ∈=),(上的权),(j i c 称为该边的容量.G 称作网络的底图.在不混淆的情况下,直接用底图代表该网络.定义2. 可以嵌入平面且使任意两条边互不交叉的图称为平面图.底图为平面图的网络称为平面网络.一个平面图G 嵌入到另一个平面中可以把平面划分成若干个区域,每个区域称为G 的一个面,其中有一个无限的面,称为外面.若平面网络G 中的源s 和汇t 在同一个面上,则称它为s -t 网络.定义3. 令A 为有向边}),(|,{E j i A j i ∈∈〉〈的集合.称从集合A 到实数集R 上的函数f :A →R 为网络G 上的一个流,若以下条件成立:∀〈i ,j 〉∈A , 0≤f (〈i ,j 〉)≤c (i ,j ), (1)∀i ∈V −{s ,t },∑∑∈〉〈∈〉〈≤〉〈=〉〈Aj i A i k i c j i f i k f ,,)(),(),(, (2) 则称相应的∑∈〉〈〉〈A t i t i f ,),(为流f 的流量.最大流是指具有最大流量的流.定义4. 集合},{t s V E C −∪⊂称为网络G 的一个截,若G 中任意一条从s 到t 的路径(s -t 路径)经过C 的一个元素.截C 中元素容量的和称为该截的容量.容量最小的截称为最小截.仅由边构成的截称为边截.定理1(最大流-最小截定理)[1,13,15].网络G 中的最大流量等于它的最小截的容量.最大流-最小截定理说明了最大流和最小截问题是一对对偶问题.2 用带链对偶图中的截环表示原图中的截网络G 中的一个截截断了G 中任意一条s -t 路径.注意到:命题1. 如果在平面中用一个环把两个点s 和t 分开,则它可以截断平面上任何一条从s 到t 的路径(如图1张宪超 等:一类实际网络中的最小截算法887所示).命题1是拓扑学中的一个基本结论.我们希望利用这一性质,找到可以代表平面网络中截的环.定理2[16]. 设v 是平面图G 的任意一个节点,可以把G 嵌入到一个平面,使v 在外面上.根据定理2,总可以把平面网络G 嵌入到一个平面,使源s 在外面上.以下总考虑网络的这种平面嵌入. 首先考虑节点没有容量的网络.在这种网络中,最小截只在边截中出现.定义5. 对仅边有容量的平面网络G ,构造G 的对偶图G ′.对任意边G e ∈,定义e 的对偶边e ′的权值)()(e c e c =′,作为e ′的长度.称G ′中包围原图G 的汇t 的环为边截环,如图2所示(加粗部分代表一个边截和相应的边截环).Fig.1 A circle in the plane cut any s -t path Fig.2 Graph G and its dual graph G ′图1 平面上任何一个环截断任意一条s -t 路径 图2 图G 和它的对偶图G ′定理3[8]. G 中的边截和G ′中的边截环是一一对应的,且每个边截环的长度等于相应边截的容量.因此,G 中的最小截的容量等于G ′中最短的边截环的长度.定理3是许多仅边有容量平面网络中的最小(边)截算法的基础.我们希望在节点和边都有容量的平面网络中得到类似的结论.对节点和边都有容量的网络，如果希望用平面中的“环”来代表网络中的截,则这些“环”不仅有可能从边上截断网络中所有从s 到t 的路径,还有可能从节点处截断这些路径.为此,对节点和边都有容量的网络G ,先构造它的对偶图的G ′.在G ′的基础上定义一个新图G ′′:在G ′中加入G 的所有中转节点;对任一中转节点},{t s V v −∈,它包含在G ′的一个面v f 中,在v 和v f 的所有边界节点之间连一条边,定义这些边的长度为2)(v c (如图3所示).定义6. 按照上述规则得到的图G ′′仍为平面图,称它为G 的带链对偶图,新加入的边称为链.类似边截环的定义,称G ′′中包围原图汇t 的环为截环.定理4． G 中最小截的容量等于G ′′中最短的截环的长度.证明:一方面,对G ′′中的任一截环C ′′上的边,建立如下的对应关系:若该边是一条普通的边,取它在G 中的对偶边和它对应.若该边是一条链,则环C ′′中必还有一条链和它相连于G 中的一个节点.取该节点和这两条链对应.这样,截环C ′′就和G 中边集合和节点集合的并集的一个子集E V C ∪⊂取得了一个对应关系.注意到G 中的任一条s-t 路径必经过C 中的一个元素,故C 是G 中的一个截,它的容量是截环C ′′的长度.另一方面,对G 中的任意一个截C ,若C 是一个边截,则由定理3,可以在G ′中找到一个边截环,也就是G ′′中 Fig.3 Primal graph G and its chained-dual graph G ″ 图3 原图G 和它的带链对偶图G ″888 Journal of Software 软件学报 2003,14(5)的一个截环,它的长度为C 的容量.若C 是一个包含节点的截,对于C 中的每个元素,若它是一条边,则它对应于G ′中的一条边;若它是一个节点,则它对应于G ′中的一个面.下面说明所有这些边和面在G ′中构成一个包围汇t 的“环”.由截的定义可知,C 截断了所有s-t 路径.每条s-t 路径总是先从源s 出发,经过截C ,再到达汇t .我们把从s 到C 那条子路径上,和C 中的某个节点或边相关联的边称为C 的入边;把在从C 到t 的那条子路径上,与C 中的某个节点或边相关联的边称为C 的出边.考虑C 中某节点v ,如果用所有与v 相关联的出边代替v ,则这些出边和C 中其他元素一起构成一个新的截.依次类推,把C 中所有的节点都用相应的出边代替,则可以得到一个全部由边构成的边截.由定理3可知,这个边截对应于G ′中的一个边截环,称它为C 的出边截环.在这个出边截环中,与截C 中的一条边e 对应的部分就是该边在G ′的对偶边e ′;与C 中某节点v 对应的部分为v 的所有出边的对偶边,它们是G ′中和节点v 对应的面f v 的边界的一部分.因此,在G ′中,与原图的截C 中的所有元素对应的边和面构成了一个包围汇t 的“环”,称这个“环”为G ′中的一个超截环,如图4所示(加粗部分代表相应的出边截环).对于超截环中的一个面,它通过一个节点(或一条边)和超截环中的另外一个元素相连,不妨称该节点(或该边的两个端点)为键点.对每个这样的面f v ,在它的每个键点和它所对应的原图节点v 之间连上一条链.这样可以得到G ′′中的一组截环(如图5Fig.4 A super-cut-circle Fig.5 The super-cut-circle in Fig.4 determinestwo cut-circles图4 一个超截环 图5 图4的超截环确定了两个截环 这样,我们说明了对G ′′中的任一截环,可以在G 中找到一个截,它的容量等于该截环的长度;而对于G 中的任一截,可以找到G ′′中的一组截环,它们的长度为该截的容量.于是得出结论:G 的最小截的容量等于G ′′中最短的截环长度.£ 定理4说明了原图G 最小截问题可以转化为它的带链对偶图中最短截环问题. 3 s -t 网络中的最小截算法 s-t 网络有一个特殊的性质,即它允许边),(t s 的存在而不破坏网络的平面性.下面总假设边),(t s 是存在的.若),(t s 不存在,可以在网络中加上一条边),(t s 并令它的容量为0,这样不会影响网络中的最小截的容量. 下面考虑s-t 网络G 的带链对偶图G ′′中的截环.注意到一个截环要截断G 中所有的s-t 路径,因此每个截环都包含了边),(t s 的对偶边,记为),(t s ′′,它截断边),(t s (如图6所示).由于),(t s ′′是所有截环的公共边.在这些截环中去掉边),(t s ′′,则每个截环的剩余部分在张宪超 等:一类实际网络中的最小截算法 889G ′′中构成一条从s ′到t ′的路径.因此,最短截环问题就可以转化为求从s ′到t ′的最短路径问题.构造一个平面图G 的对偶图G ′需要)(n O 时间.在对偶图G ′的基础上构造带链对偶图G ′′需要)(n O 的时间.利用文献[12]中的算法,可以在)(n O 的时间内计算平面图中两点间的最短路径.定理5. 可以在)(n O 时间内求出节点和边都有容量限制的s-t 网络中的最小截.4 在一般平面网络中求最小截对源和汇不在同一面上的平面网络,s 和t 之间是不存在边的.在这样的网络的带链对偶图中直接计算长度最小的截环是比较困难的.幸运的是,目前已经有了很有效的求解仅边有容量的网络中的最小截(最大流)算法,因此这里希望把节点和边均有容量的网络中的最小截问题转化为仅边有容量的网络中的问题.定理3指出,一个网络中的边截和它的对偶图中的边截环是一一对应的.因此,不但可以用长度最小的边截环来求得最小边截,反过来同样可以用最小边截来求长度最小的边截环.考虑网络G 的带链对偶图G ′′,如果再构造它的对偶图G 1,则相对于G 1来说,G ′′中的所有截环都是边截环.只要求出G ′′的对偶图G 1的最小边截,就可以求得G ′′中长度最小的截环,也就求出了原图G 的最小截.到此为止,我们已经找到了在节点和边都有容量的一般平面网络G 中求最小截的方法,即它可以转化为另一个仅边有容量的平面网络G 1中的最小边截问题.我们希望找到G 1和G 的关系,从而得到更简单的转化方法.引理1. 任意给定平面图中的一个节点,与它相关联的所有边的对偶边在对偶图中构成一个环.证明:与一个节点关联的所有边把平面分割成若干个区域,这些区域都是对偶图的节点.注意到在对偶图中,这些区域中所有两个相邻的区域之间都存在一条边,因此这些边构成一个环. □ 定义7. G ′′中所有与原图G 的中转节点v 相关联的链将v 所对应的面f v 又分成若干个区域,不妨称为f v 的子面.由引理1可知,这些链的对偶边在G 1中构成一个环,称为链环,每个子面构成了链环的一个节点.注意到每个子面都以G ′′中一个非链边为边界,因此在G 1中,链环的每个节点和一条非链边的对偶边相关联.在G ′′中,原图G 的源s 和汇t 所对应的面f s 和f t 没有被分割,它们分别对应于G 1中的两个节点,s 1和t 1.这样,我们就建立了G 和G 1的对应关系:G 中的每条边对应于G 1中的一条边,它们的容量相等;G 的每个中转节点对应于G 1中的一个链环,链环上每条边的容量为该节点容量的一半;G 的源和汇分别对应于G 1中的两个节点,它们分别作为G 1图7 带链对偶图G ″及其对偶图G 1定义8. 上述与原网络G 有相同最大流量的网络G 1称为原网络的等量网络． 若原网络G 的节点数为n ,则它的等量网络G 1的节点数为)(n O ,且可以在)(n O 时间内构造G 1.注意到原网络中截的元素和相应等量网络中边截的元素有明确的对应关系,结合前面的讨论,有:定理6. 可以在)log (n n O 时间内求得一个节点和边都有容量的一般平面网络中的最小截． 890 Journal of Software 软件学报 2003,14(5) 5 结 论对平面网络来说,传统的解决节点和边都有容量的最小截问题的方法不能保持其平面性,计算复杂度很高,为)log (2n n O .本文给出了可以利用网络平面性的方法,把s -t 网络和一般平面网络上节点及边都有容量的最小截问题的计算时间复杂度分别降低到)(n O 和)log (n n O .本文的方法可以计算网络中的最小截或最大流的流量.在一些应用中还需要计算网络中的最大流函数.如何把等量网络中的最大流函数转化为原网络中的最大流函数,是一个十分有意义的问题.对此,文献[17]中提供的伪流算法具有一定的启发性.References :[1] Ahujia RK, Magnanti TL, Orlin JB. Network Flows: Theory, Algorithms and Applications. Prentice-Hall, 1993.[2] Goldberg AV. Recent developments in maximum flow algorithms. In: Proceedings of the 6th Scandinavian Workshop on AlgorithmTheory. Stockholm, 1998.[3] Goldberg AV, Tarjan RE. A new approach to the maximum flow problem. Journal of the Association for Computing Machinery,1988,35(4):921~940.[4] Zhang XC. Study on maximum flow problem algorithms [Ph.D.Thesis]. Hefei: University of Science and Technology of China,2000 (in Chinese with English abstract).[5] Weihe K. Maximum (s ,t )-flows in planar network in O (|V |log|V |) time. Journal of Computer and System Sciences, 1997,55(3):454~475.[6] Itai A, Shiloach Y. Maximum flows in planar networks in planar networks. SIAM Journal of Computing, 1979,8(1):135~150.[7] Hassion R. Maximum Flow in (s ,t ) planar networks. Information Processing Letters, 1981,13(3):107.[8] Reif JH. Minimum s -t cut of a planar undirected network in O (nlog 2n ) time. SIAM Journal of Computing, 1982,12(1):71~81.[9] Hassion R, Johnson DB. An O (nlog 2n ) algorithm for maximum flow in undirected planar networks. SIAM Journal of Computing,1985,14(3):612~624.[10] Johnson DB. Parallel algorithms for minimum cuts and maximum flows in planar networks. Journal of the Association forComputing Machinery, 1987,34(4):950~967.[11] Frederickson GN. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal of Computing, 1987,16(6):1004~1022.[12] Klein RSB, Rauch-Henzinger M, Subramanina S. Faster shortest-path algorithms for planar graphs. Journal of Computer andSystem Sciences, 1997,55(3):3~23.[13] Granot F, Hassion R. Multi-Terminal maximum flows in node -capacited networks, Discrete Applied Mathematics, 1986,13(1):157~163.[14] Bondy JA, Murty USR. Graph Theory with Applications. North-Holland, 1977.[15] Ford LR, Fulkerson DR. Maximum flow through a network. Canadian Journal of Mathematics, 1956,8:399~404.[16] Wang SH. Graph Theory and algorithms. Hefei: University of Science and Technology of China Press, 1994 (in Chinese).[17] Hochbuam D. The pseudoflow algorithm and the pseudo flow-based simplex for the maximum flow problem. In: Proceedings of theInteger Programming and Combinatorial Optimization the 6th International Conference (IPCO). Houston: 1998. 325~337. 附中文参考文献:[4] 张宪超.网络最大流问题算法研究[博士学位论文].合肥:中国科学技术大学,2000.[16] 王树禾.图论及其算法.合肥:中国科技大学出版社,1994.。
