n個のものを、そのうちの2つのものの順序関係から一列に並べたいと考えています。
たとえば、
6つのものA,B,C,D,E,Fがあったとき、
A<B,B<C,C<D,D<E,E<F
という5つの二項関係(制約)がわかれば、
A<B<C<D<E<Fという並びが一意に決まります。
しかし、同じように制約の数が5つでも、
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ベストアンサー
- 回答日時:
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
- 回答日時:
結局ソートするのと同じなので, 完全に決定するには ceil(log_2 (n!)) 回の比較が必要, つまり同数の関係が必要とな
ります. 但し, 実際にはもっと多くの関係が必要になることがあります.この回答への補足
ただ、お伺いしたいのは、どのような条件を満たす二項関係が得られた時に、比較回数が少なくなるのかということなのです。
たとえば、(n-1)個の関係で並びが決まる場合というのは、(n-1)個の関係の集合が、どのような条件を満たすからなのでしょうか?
回答ありがとうございます。
確かにソート問題と同様とも考えられますね。そうすると、平均してnlognのオーダの回数の比較で並べ替えができることになりますね。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 政治 個人的に、憲法改正案を考えてみました。 意見を聞かせてください。 特に、9条(第2章 - 戦争の放棄 3 2023/02/22 22:08
- 数学 並べ方は何通りありますか。 2 2023/04/05 20:50
- 政治 私が考えた憲法9条改正案はどうですか? 11 2022/12/03 15:37
- 数学 すべての自然数とすべての実数を1対1で対応させる(すべての実数を一列に並べる)方法について 3 2023/05/26 17:14
- 高校 数学、円順列について。 時計回りに並べるとはどういう意味ですか? 例えば A D ◯ B C という 4 2022/09/05 23:32
- Excel(エクセル) DATEDIFで作成した勤務年数の並べ替えがうまくいかない 3 2023/07/31 17:09
- 政治 個人的に、憲法改正案を考えてみました。 意見を聞かせてください。 特に、9条(第2章 - 戦争の放棄 4 2023/02/19 14:34
- 電気・ガス・水道業 簡易専用水道の定期清掃について 3 2023/03/26 16:36
- 数学 群数列の問題がわかりません。どなたか教えてください… 【問題文】 1から順に自然数を並べて, 下のよ 2 2022/03/28 18:55
- Visual Basic(VBA) Excel のユーザー定義関数でソルバーが動作しない 1 2022/09/05 19:51
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
らせん階段の手すりの長さ
-
どうやって1本の直定規だけで30...
-
比と分数
-
中学入試の算数
-
0と1を組み合わせて出来る長さ1...
-
円の中心点のもとめかた
-
ケーキの9等分
-
重さを長さに変換する方法はあ...
-
回転移動
-
小数以下の位について
-
周の長さは同じなのに面積が違...
-
1から9までの番号をつけた9枚の...
-
0.1は10パーセントなら1.0は何...
-
数学のリアリティ
-
VBAで各列の"+"と"o"の合計数を...
-
測量図で、周囲の長さを算出す...
-
【数学】反比例、逆数、逆比例...
-
上三角行列同士をかけたときの...
-
2x−4yの3倍から、x+3yの4倍を...
-
nCk=(n-1)C(k-1)+(n-1)Ck証明
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報