K-通道流的改进算法

设G=(N,A,u)是一个顶点集为N,弧集为A,始点为s∈A,终点为t∈N,有限容量向量u={u_(ij):(i,j)∈A}及正整数K的网络。一个基本K-通道流是从始点到终点t∈N的发送K个单位流,使得在每个弧上的流是0或1。一个K-通道流是一个从s到t的流,使得这个流可以表示成基本K-通道流的非负线性组合的流。因此,K-通道流问题是求解从s到t不仅要满足顶点平衡(s和t除外)和弧的容量限制下通常的最大流问题,而且这个流必需满足沿着K条弧不交的s-t路发送。给出了另一个解决K-通道流问题组合算法,分析了这个改进算法的时间复杂性。     

多通道流的几种算法

G=(N,A,u)是一个有始点s和终点t的有向网络,每条弧的容量限制为uij.多通道流问题是求解从始点s到终点t不仅要满足顶点平衡(始点和终点除外)和弧的容量限制下通常的最大流问题,而且这个流必需满足沿着K条弧不交的s-t路发送.它对通信领域、网络领域、军事领域和科学领域有许多重要意义,是计算机科学和运筹学领域的研究内容.经20多年来的研究和发展,多通道流问题已经形成几种不同的算法,本文主要对这几种算法进行总结和归纳.     

三类特殊弦图的Kirchhoff指标

连通图G的两个顶点i和j之间的电阻距离rij定义为通过用单位电阻来代替G中的每条边而构造出的电网络N中节点i和j之间有效电阻的阻值.Kirchhoff指标Kf(G)定义为G中所有点对之间的电阻距离之和.根据图的Laplacian谱理论,得到了由一些完全图按特定方式粘贴构造而成的三类弦图的Kirchhoff指标的计算公式.