【摘 要】
：
最小饱和流问题就是求具有最小值的饱和流.此问题起源于紧急疏散和交通阻塞的研究,并且已知是一个NP-困难问题.本文探讨两个特殊情形：一个限定问题是寻求给定截集的最小饱和流
【机 构】
：
河南工业大学理学院,同济大学电子与信息工程学院
【基金项目】
：
The National Natural Science Foundation of China（11101383,61373106）, the Natural Science Foundation of Henan Province（2010B110006）
论文部分内容阅读
最小饱和流问题就是求具有最小值的饱和流.此问题起源于紧急疏散和交通阻塞的研究,并且已知是一个NP-困难问题.本文探讨两个特殊情形：一个限定问题是寻求给定截集的最小饱和流,一个松弛问题是寻求最小双向容量截集.对于前者,通过构造一个辅助网络AN（S）及运用最大流算法,建立一个多项式时间算法,并证明其复杂性是O（n3）.对于后者,通过构造一个单向网络N′,将问题转化为一个最小容量截问题.但是这个新网络N′可能包含负容量的弧,一般不易求解.当单向网络N′是平面网络时,我们建立了多项式时间算法.
其他文献
培养诚信、求真、创新、严谨、自律、坚韧的思想品德和人格,一向是高校学风建设中崇高的社会道德期望.而目前学习动力不足、专业思想不稳、抄袭作弊风盛行、课堂纪律松懈、沉
本文研究一类特殊相依随机序列-离散指数分布序列，利用随机序列似然比与相对熵概念作为刻画随机序列相依性的随机性度量，借助B-C引理与纯分析方法，给出了离散指数分布序列无规则
我国<广告法>及相关工商行政法规对部分商品的广告作出了限制性规定.如中央电视台的<关干电视广告应注意的几个问题>第十条就规定中央电视台不播香烟广告和行医广告;现行广告
在加油站经常会看到"禁止打手机"的标识,但很多人采取无所谓的态度,就算工作人员上前劝阻也会置若罔闻.
1选用壮苗,合理密植栽植的苗木要求是品种纯正、枝芽健壮、根系发达、无病虫害、苗高1.2m以上、干粗1cm以上的2年生成苗,苗木必须新鲜,无失水现象.按2m×4m或2m×3m