n個のものを一列に並べるための制約条件

質問

n個のものを、そのうちの２つのものの順序関係から一列に並べたいと考えています。

たとえば、
６つのものA,B,C,D,E,Fがあったとき、
A<B,B<C,C<D,D<E,E<F
という５つの二項関係（制約）がわかれば、
A<B<C<D<E<Fという並びが一意に決まります。

しかし、同じように制約の数が５つでも、
A<B,A<C,A<D,A<E,A<F
という制約であれば、
A<{B,C,D,E}という並びしかわかりません。

n個のものの二項関係は全部で、nC2 = n(n+1)/2個あって、
そのすべてがわかり、無矛盾であれば並べられます。

また、初めの例のように、最低で(n-1)個の二項関係で並べられることもあります。

いったい、どのような二項関係がいくつわかれば、並びを一意に決めることができるのでしょうか？

回答No.2

31415926 · ベストアンサー

n個のものがあり，二項関係が最初にいくつか
与えられているとします．

そしてA_1<A_2<...<A_k なる二項関係の列のことを
「長さkの鎖」と呼ぶことにし，また
A_1<A_2<...<A_k<A_1 となる二項関係の列
(つまり最初と最後が同じものになるような二項関係の列)
のことを「サイクル」と呼ぶことにしましょう．
(これらの名前は今，私が勝手につけたものです)

するとサイクルがなくて，長さnの鎖があれば
並びを一意に決めることができます
(長さnの鎖で大小関係を決めればよい．サイクルが
ないので，それに矛盾する二項関係は存在しない．)

そして，結論ですが，逆に
「並びが矛盾なく一意に決まるとすれば，
サイクルは存在せず，また長さnの鎖が存在する」
ということが言えます．

証明の感じをいいます．
まず矛盾がないことから
サイクルが存在しないことがいえます．
また，並びが一意に決まるということから
1番目小さいもの　A_1,
2番目に小さいもの　A_2, ...
n番目に小さいもの　A_n
が決まっているわけですが，
「A_1がA_2より小さいこと」は他の関係からは
出ませんから(つまりA_1<.....<A_2と間が開くことは
ありえない)，A_1<A_2という二項関係は最初から
ないといけません．同様にA_i<A_{i+1}も最初から
ないといけないので，結局長さnの鎖があることに
なります．

特に，質問にありました
A<B,B<C,C<D,D<E,E<F
みたいなものは絶対に含まれなければならない
という結論になりました．

お礼

明解なご回答ありがとうございます。

n個のものの二項関係の集合が、
「A_1<A_2<...<A_nという長さnの鎖を含む」
ことが並びが一意に定まるための条件ですね。

二項関係の集合が含む、鎖の長さの最大値がk(<n)の時は、残り(n-k)の部分をつなぐ鎖が得られればよいということが、よくわかりました。

補足

サイクルに関する話も、大変参考になりました。
ありがとうございます。

回答No.1

Tacosan

結局ソートするのと同じなので, 完全に決定するには ceil(log_2 (n!)) 回の比較が必要, つまり同数の関係が必要となります. 但し, 実際にはもっと多くの関係が必要になることがあります.

お礼

回答ありがとうございます。

確かにソート問題と同様とも考えられますね。そうすると、平均してnlognのオーダの回数の比較で並べ替えができることになりますね。

補足

ただ、お伺いしたいのは、どのような条件を満たす二項関係が得られた時に、比較回数が少なくなるのかということなのです。

たとえば、(n-1)個の関係で並びが決まる場合というのは、(n-1)個の関係の集合が、どのような条件を満たすからなのでしょうか？