ハッセ図
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/30 10:11 UTC 版)
ハッセ図（ハッセず、英: Hasse diagram）は、数学における有限半順序集合を単純に図示する方法のひとつで、半順序の推移簡約を描いたものである。具体的には有限半順序集合 (S, ≤) があるとき、S の個々の元を頂点とし、x < y で、かつ x < z < y となるような z が存在しない場合にのみ x から y に上向きの線（辺）を描く（ここで二項関係 < は全ての x について (x, x) という元を ≤ から除くことで得られる）。 この場合、「 y は x を被覆する」または「 y は x の immediate successor（直接の後続）である」という[1]。さらに、各辺が両端の頂点以外を通らないように頂点を配置する必要がある。このような図（頂点にはラベルが付属するものとする）は半順序を一意に特定し、任意の有限な半順序では推移簡約が一意に定まる[2]。ただし、図における元の配置の仕方は様々なものが考えられ、ひとつの順序集合に対して見た目の異なるハッセ図が多数存在することになる。
- ^ Birkhoff 1967, p. 4.
- ^ 無限な半順序は推移簡約を持つとは限らない。各元には必ず immediate successor がなければならない。実数の区間 [0, 1] を考えてみればよい。
- ^ Birkhoff (1948, p. 6)とSchröder (2016, p. 6)を参照。
- ^ Birkhoff 1948, p. 6.
- ^ 例えば、Di Battista & Tamassia (1988) や Freese (2004) を参照
ハッセ図
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/11 02:16 UTC 版)
P を有限集合とし、「<」を P 上の狭義の半順序とするとき、以下のようにして P を自然に単純有向グラフと見なせる： 頂点：P の元 a ∈ P から b ∈ P への辺がある ⇔ a < b であり、しかも a < c < b を満たす c ∈ P が存在しない （すなわち b は a を被覆している） この有向グラフを図示したものをハッセ図という。 ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。例えばこの図で {x} と {x, y, z} は比較可能だが、{x} と {y} は比較不能である。また単集合の族 {{x}, {y}, {z}} は反鎖である。さらに {x} は {x, z} によって被覆されるが、{x, y, z} には被覆されない。 なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に (V, E) を閉路を持たない有限な単純有向グラフとすると、V 上に以下の順序を入れることで V を半順序集合と見なせる： a < b ⇔ a から b への道がある したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。
※この「ハッセ図」の解説は、「順序集合」の解説の一部です。
「ハッセ図」を含む「順序集合」の記事については、「順序集合」の概要を参照ください。
- ハッセ図のページへのリンク
