由渠道设计问题引出的有向图上最小树形图问题的解法

在1]中首先提出求一般有向图的最小树形图的计算方法。以后,在2]中,对于一类特殊的有向图,即等双回路图,指出了1]中的方法可以改进,使得计算的速度可以加快。 在最小树形图的实际应用中,渠道设计问题是一个重要的方面,1]与2]中都以此问题作为最小树形图问题的实际背景之一。本文将指出,对于由渠道设计问题引出的有向图上求最小树形图问题,可以用一种更简单的、推广起来也可能是更容易的方法来解决。