最优箭线图的判定与唯一性

统筹图又叫计划网络图或箭线（工程）图．任给一个有限偏序集（简称序集，其元素叫做工序或作业），要绘制它的一个最优统筹图（含虚工序数最少者）是一个尚未解决的困难问题．本文给出了一个判定一序集存在唯一最优箭线图的充分条件以及绘制这类序集的最优箭线图的方法；并指出：若Ｐ一个序集满足Ｗ－ｆｒｅｅ和Ｍ－ｆｒｅｅ，则Ｐ的最优箭线图唯一且可在多项式时间内作出．

The Judgement and Uniqueness of Optimal Arrow Diagram

Given a finite partially ordered set (poset), the elements of which are called tasks, it is a hard problem to construct its optimal PERT network, the one with the smallest number of dummy tasks. In this paper it is presented a method for constructing the optimal arrow diagram for a type of posets which are W free or M free with height 2. It is also shown that: if a poset P is W free and M free, then the optimal arrow diagram of P is unique, which can be constructed in a polynomial time.