半序集的碰撞数与分层深度贪婪算法  

THE BUMP-NUMBER AND THE DLG ALGORITHM FOR THE POSET

作　　者：舒辉四[1] 李慰萱[1] 

机构地区：[1]长沙铁道学院科研所

出　　处：《高校应用数学学报（A辑）》1994年第4期435-442,共8页Applied Mathematics A Journal of Chinese Universities(Ser.A)

摘　　要：设Ｐ＝（Ｘ，≤）是一个半序集．本文在关于碰撞数的深度贪婪算法的基础上，直接证明了对任意的Ｐ存在一个最优的ＤＬＧ扩张；给出了ＤＬＧ半序集的定义，并证明了半序集Ｐ是ＤＬＧ半序集的一个充分条件；最后给出了ＤＬＧ扩张算法．Let P= (X,≤) be an ordered set, based on the depth-greedy algorithm with respect to the bump number, a more restricted algorithm called depth-layer-greedy algorithm (DLG algorithm) is introduced. It is shown directly that there always exists an optimal extension in the set of extensions obtained by DLG algorithm. An ordered set P is called a DLG order if all DLG extensions of P is optimal.A sufficient condition in terms of forbidden suborders for an ordered set to be a DLG order is given. An algorithm to construct a DLG extension of ordered sets are included.

关 键 词：半序集 碰撞数 深度贪婪算法 

分 类 号：O158[理学—数学]