论文部分内容阅读
以油气收集系统设计为背景,研究如下的网络优化问题,在一个加权有向图G中,根点r代表收集中心,其他顶点代表具有给定容量的油井,每条边的权表示运输距离。问题是求G的一个支撑树,满足容量约束,使得到r的传输半径最小。主要结果是问题的NP-困难性证明及等容量情形的多项式时间算法。同时,讨论一般情形的精确算法及启发式算法。