平面图中的多商品流

本文讨论了源汇对间添加一条边后所得的网络图为平面网络图的情况下,如何求有可行流存在的网络中的多商品流,提出了求解多商品流的多项式时间算法,其运算复杂度函数为O{(n k-1)nlnn[|E(Q_(1e,max))|-1]}。作为此算法的应用,讨论了运输网系统如何合理安排商品的流量及流向的问题。