最大流

摘要： 最大流是一个重要的图计算问题,很多实际场景中如城市车流量和排水管道的排水量等问题若转化为最大流问题可以得到有效的解决.已有工作从多个角度对最大流问题进行了探讨,但仍存在一些问题.针对一些分布式图计算系统进行图分割计算复杂度较高,多次计算存在大量冗余工作等问题,提出基于GraphChi框架的大规模图最大流加速算法.根据原图中的割点构建覆盖图,给定源点和汇点后确定覆盖图中唯一路径,在GraphChi框架上并行求解覆盖图路径上各子图的最大流,找到各子图最大流的最小值即为原图的最大流值.在美国路网数据集的测试结果表明,提出的算法可显著缩短大规模图的最大流计算时间并且空间复杂度较低,有很好的加速效果.

摘要： 以力导向为基础的解析型算法如今越来越多地被应用到FPGA布局问题当中去,二次线性规划算法便是其中一种,其使用数学的方法求解拉力模型矩阵,以得到理论的最优解.但在实际的算法实现当中,二次线性规划虽体现出了其较快求解的特性,其解却存有重叠的问题,尚需进一步合法化以解决重叠问题.现有的合法化过程一般较为随意,并无系统性算法,导致最终解质量下降.文章将合法化过程加以抽象,转化为最大流算法的问题,以求得最优合法的解.

摘要： 本文以水资源运输的最优方案为例,通过从实际问题中抽象出网络图,将实际问题转化为最大流问题并应用数据结构中的图论知识和管理运筹学中的Ford-Fulkerson标号法作为算法依据,最终解决问题。

摘要： 针对最短增广链算法一开始选取增广路径的随意性,给出了一种在单源、单汇网络中通过层弧容量比来求解网络最大流的新算法.该改进算法的思想是运用宽度优先搜索的方法,在改进的分层剩余网络中找到与汇点相邻接且容量最大的弧(称为关键弧),再选择含有关键弧的最短增广路径,根据制定的规则,从而有序地进行流值增广,直至没有可增广的路径终止.在BA无标度网络中进行实验,发现新算法的效率略高于最短增广链算法,且能把关键弧的容量更加合理地分配给上一层弧,提高了最大流的流值.

摘要： 通过分析最短增广链算法中好的一面是对顶点分层的理念,不足之处在于需要反复构建分层剩余网络造成算法步骤的繁琐,并且在构建了比原网络更轻易发现增广链的分层剩余网络后,在选取增广链时还是存在随机性,这就导致了某些增广链的丢失,使得最终流值偏小的结果.针对这一现象,提出了一种重置顶点下标的最大流改进算法.该算法首先根据每个顶点在整个网络图中所处位置的重要程度制定相应规则,然后对顶点下标按照此规则重新编号,使得网络图更加清晰直观,从而避免了最短增广链算法中反复构造分层剩余网络图的缺陷.而且新算法还增加了寻找增广链的方法用以规避随机性的缺陷,这也为后面寻找增广链有规可循节约了时间.最后通过数值实例仿真实验证明了新算法的简易性和准确性.

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

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

摘要： 最短增广链算法构建分层剩余网络后,在面临多条相同弧数增广链且其中顶点有重合的情况下,会因寻找增广链时未考虑增广顺序而导致流值丢失.针对该问题,提出一种网络图中包含交叉顶点的最大流改进算法.该算法保留最短增广链算法的分层理念,仍在分层剩余网络中寻找增广链,在此基础上增加寻找增广链的规则,即优先搜索与源点关联且容差最小的顶点作为下一步推进点,确定一条增广链后即考虑与上一条有重合的顶点所在的增广链进行增广.实例分析与BA无标度网络建模仿真结果表明,与最短增广链算法相比,该算法得到的最大流值更准确,并且效率相当.

摘要： 为了降低不同学者实体之间的共享特征(如机构、发表会议等)给同名区分带来的影响,提出一种基于网络最大流的同名区分算法.该算法将论文实体及其特征融合成一张网络图,根据特征节点的被共享程度设定不同的容量,再计算论文节点间的最大流量,并基于最大流量进行层次聚类.实验结果表明:该算法在精准率和召回率上有较为均衡的表现,具有较好的综合性能.

摘要： BA无标度网络是现实中常见的网络,在该网络中,任意两节点之间有极大可能存在多条路径,若用Ford-Fulkerson算法寻找增广链,效率不高且步骤繁杂.同时,在当今大数据时代背景下,随着网络规模的增加,提高算法效率成为解决大规模网络最大流问题的关键.为了改善以上不足,文中在最短增广链算法的基础上作了一些改进,提出了最短增广链改进算法.该算法基于最短增广链算法,删除原网络中没有起作用的弧;在分层剩余网络中删除的饱和弧,相应的在原网络中删除该弧,降低构建剩余网络和分层剩余网络的复杂性,从而优化最短增广链算法.实验结果表明,在BA无标度网络中该算法与最短增广链算法的计算结果相同,并且运行效率比最短增广链算法有所提高.

摘要： 在Ford-Fulkerson 算法以及最短增广链算法的基础上作了改进,给出了一种求解最大流问题的"筛选"算法.该算法避免了标号过程同时也避免了将网络流初始化,而是在求最大流之前先筛选出已饱和的弧并将其归入终止弧,然后再在剩下的弧中逐步寻找可增广链,直至得到最大流,此外该算法是在一个图上完成的,这样可以节省许多画图时间,同时该方法增强了算法的直观性和可控性,易于实现.

摘要： 针对多个中继端的协作网络，给出了网络最大流的矩阵算法。当中继端的一些相互协作并组成一个虚拟整体时，能改变该路径上的等效流量和网络的路由，从而改变整个网络的最大流。rn 当某些中继不能正常工作时，通过选择一些等效路由来替代，从而使系统具有较好的抗毁性。系统仿真结果表明，通过适当的对中继分组，能增加网络的最大流。rn 同时，能使得网络具有良好的稳健性。

摘要： 无向平面单位容量网络中的最大流问题在VLSI设计等领域中有广泛的应用.针对无向平面单位容量网络的特点, 给出这类网络中一个O(n)时间的最大流算法, 比一般平面网络中O(nlog n)时间的最大流算法快log n倍.

摘要： 该文研究的弧在网络流中的作用，介绍了临界点与临界值的概念，并且定义了一个新参数；极限容效。通过实例说明，该参数在实践中有着重要的应用价值。

摘要： 该文研究的弧在网络流中的作用，介绍了临界点与临界值的概念，并且定义了一个新参数；极限容效。通过实例说明，该参数在实践中有着重要的应用价值。

摘要： 该文研究的弧在网络流中的作用，介绍了临界点与临界值的概念，并且定义了一个新参数；极限容效。通过实例说明，该参数在实践中有着重要的应用价值。

摘要： 该文研究的弧在网络流中的作用，介绍了临界点与临界值的概念，并且定义了一个新参数；极限容效。通过实例说明，该参数在实践中有着重要的应用价值。

摘要： 该文研究的弧在网络流中的作用，介绍了临界点与临界值的概念，并且定义了一个新参数；极限容效。通过实例说明，该参数在实践中有着重要的应用价值。

摘要： 该文研究的弧在网络流中的作用，介绍了临界点与临界值的概念，并且定义了一个新参数；极限容效。通过实例说明，该参数在实践中有着重要的应用价值。

摘要： 本发明公开了一种基于最大流算法的FPGA布局合法化方法，涉及FPGA技术领域，该方法按照FPGA的初始布局状态确定各个线网的线长，对初始布局状态进行抽象建立剩余图并利用线长对剩余图中由非法节点和空置位置之间的关系抽象形成的有向边进行赋值作为边的花费，基于最小花费最大流算法对所述剩余图进行求解得到各个非法节点的合法位置，并将各个非法节点摆放至对应的合法位置处即能完成布局合法化；该方法将最大流算法应用于二次线性规划算法的合法化部分，使原本不具有导向性的合法化流程变得具有导向性，并在一定程度上提高了最终解的质量，使得合法化后的线长更短、布局结果更优。

摘要： 本发明公开了一种基于最大流算法进行拥挤区域展开的力导向布局方法，涉及FPGA布局技术领域，该方法在利用力导向布局算法模型进行解析式算法迭代过程中，阶段性的选取布局拥挤度高的目标区域进行抽象建立剩余图并赋值，基于最小花费最大流算法对剩余图进行求解，使得全局布局在满足退出条件之前，可重布节点就当前布局状态下所处的位置得到一个合法的迭代位置，通过在迭代位置处添加对可重布节点的虚拟加力点进行牵引可以使可重布节点有往合法的迭代位置移动的趋势，从而可以导向性的加速拥挤区域展开速度，从而减少解析式算法的迭代次数，减少运行时间，提高布局效率。

摘要： 本发明公开了一种计算天然气放空管道最大流速的自适应约束方法，属于天然气管道设计技术领域。该方法包括以下步骤：步骤一，收集放空管道的基础数据；步骤二，计算放空管道最大流速所需的流体热物性参数；步骤三，建立放空管路水力、热力参数计算模型；步骤四，求解水力、热力参数计算模型，得到放空管道出口最大流速Vmax；步骤五，计算放空天然气的声速Vs，当Vmax>Vs时，引入放空管道最大流速约束方程，调整放空管道出口流量或压力约束值，直到0.999≤Vmax/Vs≤1.0时停止。本发明能够限制天然气放空管道最大流速不超过当地声速，从而避免了常规天然气放空管道流速计算方法中出现的超声速流动情况，为天然气放空管道的设计提供了可靠的依据。

摘要： 本发明涉及信息技术领域，公开一种基于最小费用最大流的负载均衡的多服务迁移方法及系统，该方法包括：根据边缘服务器的地理位置以及连接关系，构建网络拓扑图；计算每一对边缘服务器间的最短路径距离，并生成最短路径距离矩阵；建立最小费用最大流模型，对模型进行求解得到最小费用最大流，并将服务结点放置在对应的边缘服务器结点上；更新每个服务的访问信息，调整边缘服务器结点连至终结点的边的权值，并更新服务结点在边缘服务器结点上的位置；实时的监控和统计访问信息并在其变化率超过设定阈值时，调整其对应的服务结点和边缘服务器结点。本发明使得虚拟服务在边缘结点上的放置得更均衡且灵活可调，保证了对用户的快速响应，提升服务质量。

摘要： 本发明公开了一种基于最大流速先验信息的频域时空图像测速方法，包括：假设水深与表面流速成正比例关系，计算断面最大水深和测速线水深；利用当前水位下断面最大流速先验值计算测速线的最大流速先验值；计算测速线的尺度变换因子，并根据频域时空图像测速法的逆变换确定时空图像频谱主方向的搜索区间；在搜索区间内搜索幅度谱极坐标投影的极值，将对应角度作为测速线的频域主方向估计值，并根据频域时空图像测速法的正变换计算测速线的流速值。本发明可以有效滤除野外复杂光照、水流及气象条件下倒影、耀光、紊流、雨雾、遮挡等环境噪声对时空图像测速法的干扰，从而抑制测量粗大误差，显著改善低流速及高流速测量的稳定性和可靠性。

摘要： 本发明涉及考虑最大流和信息物理耦合的综合能源系统站选址方法，属于能源枢纽站选址技术领域，包括以下步骤：将目标区域信息网拓扑结构、信息传输设备信息以及信息节点设备信息输入到已搭建的信息网模型中，建立信息处理中心选址综合评价指标；将电力系统拓扑结构和电力系统节点信息输入到已搭建的综合能源系统模型中，建立储能电站选址综合评价指标；将目标区域电动汽车需求容量输入到已搭建的电动汽车充换电站模型以及电网模型中，建立电动汽车充换电站选址评价指标；将天然气管网供应评估最大流量，冷热管网计算最短管道距离，建立冷热气管网综合评价指标。通过此种方式多角度、多方面的情况综合考虑，优选出最佳节点。

摘要： 本发明公开一种基于软间隔支持向量机的车载容迟网网络编码最大流设定方法，主要解决在车载容迟网中，如何使源节点某一分代网络编码数据获得最大流。其实现方案是：通过浮动车数据，计算车载容迟网每个单元路段节点的最小度概率，确定每个单元路段节点的连通概率；以单元路段节点间的连通概率和单位路段节点密度作为软间隔支持向量机预测模型的输入，判断路段节点是否具有连通性，确定它是否作为车载容迟网动态网络拓扑图中的边；利用安德伍德交通模型计算路段车流量和数据流量，把数据流量作为车载容迟网动态拓扑图边的权重；确定动态拓扑图后，源节点某一分代网络编码数据的最大流为车载容迟网动态拓扑图的最小割。本发明保证源节点数据进行网络编码后，可获得最大的数据传输速度，提高了网络链路的容量，可用于车载容迟网络。

摘要： 本发明公开了一种基于最大流的电网弹性建模及量化评估方法，本发明首先评估方法本发明一方面引入最大流思想综合考虑元件易损特性与系统结构特征，建立了实时衡量飓风对配电系统造成损害的脆弱性模型；另一方面统筹考虑系统供电恢复时间最短和供电量提升最快的目标，利用PERT/CPM算法求解最优故障恢复次序，并依据最大流值评估系统的恢复性能，最后以IEEE‑30节点网络为例模拟了飓风袭击下系统的损坏和修复过程，验证了该方法的可行性与有效性，结果表明该方法有助于识别系统关键元件，并使系统在最短时间内恢复系统供电。

摘要： 本公开教导了一种用于估计通过热交换器的最大流的方法和设备。更具体地，本公开集中于通过用于加热、通风和/或空气调节的装置的热交换器的最大流。一种限制通过阀（1）的流的方法，包括：读取来自流传感器（5a，5b）的信号的时间序列；从信号的时间序列产生流速的时间序列；产生值的平均序列；通过利用下阈值（13）替换低于下阈值（13）的值来产生值的第一有界序列；通过利用等于上阈值（15）的值替换超过上阈值（15）的值来产生值的第二有界序列；通过将移动最大值滤波器（17）应用于第二有界序列来产生最大流速；读取设定点信号（9）；将设定点信号（9）限制到最大流速；从受限的设定点信号产生致动信号；将致动信号传输到致动器（7）。

摘要： 本发明公开了一种基于最大流理论的电‑气耦合系统关键线路辨识方法，基于最大流理论，结合复杂网络理论，改进了传统的线路介数，克服了假设综合能源系统节点间能量或功率总是沿着节点间最短路径传播的不足，考虑了综合能源系统的所有可能传输路径，更符合综合能源系统的特征。同时从线路的结构重要性和状态重要性两方面考虑，建立了反映线路结构中心性和传输承载能力的线路综合重要度指标，使综合能源系统关键线路的辨识更精确、更可靠，为综合能源系统关键线路的辨识提供了的新的思路和方法。本发明除用于综合能源系统关键线路的辨识外，还可推广用于热力系统、交通系统、物流系统及其他大型复杂系统的关键线路辨识，具有广泛的应用价值。