順序のはなし・その3

今日扱うのは「前順序」(preorder) です. (しつこいようですが「全順序」の typo ではないです.)


私の事情で今日は短めにします. 細かいところは端折りますが内容は漏らさずに書くので, 質問などあればコメントや Twitter ( http://twitter.com/cocoatomo ) の方へお気軽にどうぞ.

前順序の定義

さていつも通り定義から入りましょう.

  1. どんな a でも a ≦ a
  2. a ≦ b かつ b ≦ c ならば a ≦ c


昨日の「半順序」から2つ目のルールが消えている形ですね.「a ≦ b かつ a ≧ b でも a = b とは言えない」という性質の順序です.「全順序」よりも弱い「半順序」と比べてさらに弱い順序ということですね.

前順序の例

かなり条件の緩い順序なので, いい加減な比較をしている例を出せば良いことになります.


例えばグループごとの人数で順序付けをする場合,「5人のグループの方が4人のグループよりも大きい」ということは言えますが,「どちらのグループも5人のグループだから同じグループだ」と言うのは違和感がありますね.

グループのメンバーが異っているのにそれらを一緒くたに扱うところに違和感があるのでしょう.「グループの人数」という観点のみで比較しているため,「グループのメンバー」という細かいところまで把握できていないのです. こういう「大雑把な比較」が前順序です.

明日以降

さて, 最初に挙げたネタが尽きたわけですが, 順序に絡めてグラフの話をしていこうと思います.「BFS」「DFS」「topological sort」あたりを取り上げる予定です.

「圏と絡めた順序の話とかも紹介できたらいいなぁ」とも思ってますが, 自分の勉強のペース次第です^-^;

おまけ

最近, 太郎の「男女」が「順序」の歌にしか聞こえません.

♪先生, 男子が列を乱して並びません
先生, 女子がおしゃれな順序でもめています

うるさい, 並べ, 整列結果を乱すな