一类半序图的最小对比次数

排序问题中求最小对比次数的问题最原始的提法是:给了n个对象(例如n个球),它们的某一个数字指标(例如重量)大小各不相等,但究竟谁大谁小需要通过“对比”来确定,每次对比只能在任意指定的两个对象之间进行,对比结果知道了它们的大小次序,问题是:最少要通

MINIMAL NUMBER OF COMPARISONS OF ONE KIND OF PARTIAL ORDERED GRAPHS

We can decide by comparison the relative weights of a given number of objects so that we will know which one of any two of them is heavier than the other. Suppose some relationships among them are given, this situation can be expressed by a partial ordered graphs, such as In order to put the given objects in a complete order it is necessary to do a series of comparisons. What is the minhnal number of comparisons for a given partial ordered graph that will make it become a complete ordered one? In this paper, we will give the answer to the question for the partial ordered graph shown in Graph 2.