最短增广路算法改进最大流问题运行时间证明的修正

最大流问题在工程计算机原理与通信系统、应用数学以及社会和军事等领域有着广泛的应用.利用最短增广路算法可以有效改进最大流问题的运行时间,提高计算效率.本文是对最短增广路算法改进最大流问题运行时间证明过程的部分修正.

网络优化的最大利润问题及其增广路算法

仿照最小费用最大流问题的物理意义,将网络上的费用参数转化成为一种利润参数,提出一个最大利润流问题,并建立了该问题的数学规划模型;给出一个求解该问题的最大利润增广路算法,该算法能快速有效地求得该问题的最优解及目标函数值。用示例对算法的求解过程进行了演示,结果表明该算法比一般的线性规划方法更加的方便,且直观得多。

一种新的增广路径最大流算法

本文提出一种新的增广路径最大流算法,关键顶点可行分量算法(KPFC),引入关键顶点机制,将其去除,从而求出网络图的可行分量,再在可行分量中寻找增广路,从而简化路径寻找的难度,替代反向边机制,有效降低算法复杂度。

用独立通路法确定矿井通风网络的极值流

确定矿井通风网络极值流的常用算法有Ford-Fulkerson法、Edmonds-Karp法和Dinic法。所谓独立通路就是采用深度优先搜索法在找通路的过程中,后面的通路至少要含有一条前面的通路所不含有的分支。独立通路法确定网络的极值流,就是利用找独立通路的思想来找增广路,找增广路时每次至少有一个分支达到饱和。从网络的源点开始进行寻边,找分支的可增广量为最大的出边,将该出边的末节点作为新的寻边始节点,继续找可增广量最大的出边,该搜索过程一直到所寻找的分支的末节点为网络的汇点为止,一条增广路即一条通路确定完毕,将该通路中分支的最小增广量作为通路的增广量对通路的各分支进行增广。增广后至少有一条分支达到饱和,删除饱和分支,用导出的网络继续找新的增广路并增广。

最大流问题的DNA计算两阶段法

给出了最大流问题的DNA计算两阶段法:第一阶段采用路序问题DNA算法得到包括所有增广路的路集,算法有两点改进,即采用等码长编码和不进行排序,这减少了生化实验时间.第二阶段算法思路是:设置一个逐步减小的增量Δ,对每个确定的Δ值从第一阶段得到的路集中寻找并增广容量不小于Δ值的增广路,对整数容量网络,当Δ<1时获得最大流.证明了算法的正确性和复杂性,并指出在以增广路为基础的最大流算法中,本算法复杂度最低,这说明DNA计算和电子计算相结合的巨大优势.

人力资源多维分配问题的混合算法

针对已有多维分配问题求解算法复杂、耗时长及精度低等问题,本文将二部图中寻求最优匹配的方法进行推广,运用试分配、饱和路调整和增广路调整对多维分配问题的最优解进行搜索,提出了求解人力资源多维分配问题的最小零面优先分配混合算法和随机试分配混合算法,对算法的有效性进行了理论证明,并分析了算法的时间和空间复杂度;同时通过这两种混合算法对初始零元素数不同的代价矩阵求解时间的计算,以及与Lagrangian松弛算法和剪枝法的耗时、精度的对比,分别得到了两种混合算法的适用性和高效性,最后通过算例验证了算法的有效性。

有向网络中无环最小饱和流问题及其算法

假设网络的初始流为零流,以最大堵塞截面为准堵塞截面,找出从源点到汇点的包含准堵塞截面弧最多的有条件最长增广路对网络进行增流,直至网络达到饱和,并对该算法进行了复杂性分析。利用该算法对多个网络进行论证,结果表明利用有条件最长增广路算法计算出的最小饱和流值与仿真计算以及与双向增流算法计算得到的结果基本相同,增流次数大大减少,且求解的结果避免了在封闭环路中的流量流动,进一步优化了最小饱和流值。

连续时间网络上的最小费用流问题

建立了连续时间网络上的最小费用流问题的数学模型 ;证明了连续时间网络中的增广流的存在性定理和最优性定理 ;

求邻接对集的一个有效算法(英文)

图的一个邻接对集是指由其互不相交的相邻边对构成的边的子集，且去掉这些相邻边对后，所得之图是连通的．本文提供了求最大邻接对集的一个有效算法。

最大分数 f -因子的注记

假设图G存在分数f-因子,则把其拥有最多边数的分数f-因子称为G的最大分数f-因子.在两个不同分数f-因子中定义符号交错路和调整操作,证明可以通过有限次调整操作使得两个分数f-因子通过它们对应的示性函数的转变而相互转变.定义增广路,并且证明关于示性函数h的分数f-因子是最大分数f-因子的充分必要条件是G中不存在关于示性函数h的增广路.

省级邮政通信网能力的研究（二）

省级邮政通信网能力的研究（二）石家庄邮政高等专科学校赵栓亮五、数学模型的解法我们前面给出的省级邮政通信网能力网络模型，实际上是一个个多个发点和多个收点的网络最大流问题。为求出网络的最大流，首先将有向网络图进行如下变换。所有的点Ｓｉ（ｉ＝１，２，３…ｎ...

网络流和棒球赛淘汰问题

1996年9月10日,《旧金山纪事报》的体育版上登载了《巨人队正式告别NL西区比赛》一文,宣布了旧金山巨人队输掉比赛的消息。当时,圣地亚哥教士队凭借80场胜利暂列西区比赛第一,旧金山巨人队只赢得了59场比赛,要想追上圣地亚哥教士队,至少还得再赢21场比赛才行。然而,根据赛程安排,巨人队只剩下20场比赛没打了,因而彻底与冠军无缘。有趣的是,报社可能没有发现,其实在两天以前,也就是1996年9月8日。

最大流算法在小型园区网络中的应用

本文以我校校园网为例,利用最大流算法,可以计算出我校网络在当前的主干设备所具有的硬件性能条件下,能够承载的最大出口链路带宽[1],并结合实际使用情况,找出能够满足用户上网需求的最小带宽,以此来得到一个出口带宽的上限和下限,能够为单位节约不必要的链路租赁开支。

工程施工中运输网络优化方案

施工工地运输方案的优化设计可以归结为 :按施工期要求设计运输线路或验证已有线路通行能力 ,计算总线路中影响提高流量的关键路段 ,取得最小费用最大流 .本文运用图论理论这一数学工具把实际问题抽象为有向网络 ,进而建立数学模型 .此方法理论上严密 ,解题步聚直观清晰 ,对水利、公路、水路、铁路等其它运输系统有普遍意义 .