ハッセ図のソースを表示

[[File:Hasse diagram of powerset of 3 no greatest or least.svg|right|250px]]
'''ハッセ図'''（ハッセず、[[英語|英]]: Hasse diagram）は、[[数学]]における有限[[半順序集合]]を単純に図示する方法のひとつで、半順序の{{仮リンク|推移簡約|en|transitive reduction}}を描いたものである。具体的には有限半順序集合 (''S'', ≤) があるとき、''S'' の個々の元を頂点とし、''x'' &lt; ''y'' で、かつ ''x'' &lt; ''z'' &lt; ''y'' となるような ''z'' が存在しない場合にのみ ''x'' から ''y'' に上向きの線（辺）を描く（ここで[[二項関係]] &lt; は全ての ''x'' について (''x'', ''x'') という元を ≤ から除くことで得られる）。
この場合、「 ''y'' は ''x'' を'''{{仮リンク|被覆関係|en|covering relation|label=被覆}}'''する」または「 ''y'' は ''x'' の immediate successor（直接の後続）である」という{{sfn|Birkhoff|1967|p={{google books quote|id=ePqVAwAAQBAJ|page=4|4}}}}。さらに、各辺が両端の頂点以外を通らないように頂点を配置する必要がある。このような図（頂点にはラベルが付属するものとする）は半順序を一意に特定し、任意の有限な半順序では推移簡約が一意に定まる<ref>無限な半順序は推移簡約を持つとは限らない。各元には必ず immediate successor がなければならない。実数の区間 [0, 1] を考えてみればよい。</ref>。ただし、図における元の配置の仕方は様々なものが考えられ、ひとつの順序集合に対して見た目の異なるハッセ図が多数存在することになる。

ハッセ図はドイツの数論学者[[ヘルムート・ハッセ]]（1898年–1979年）に因んで名付けられている。これはハッセが部分体や拡大体がなす半順序集合を図示するために効果的に活用したからである<ref>{{harvtxt|Birkhoff|1948|p=6}}と{{harvtxt|Schröder|2016|p={{google books quote|id=66oqDAAAQBAJ|page=6|6}}}}を参照。</ref>。しかし、ハッセが最初にこの図を使ったわけではなく、少なくとも {{harvtxt|Vogt|1895}} では既にこの図が使われている{{sfn|Birkhoff|1948|p=6}}。ハッセ図は半順序集合を手で図示する技法として生まれたが、最近では[[グラフ描画]]技法を使って自動的に描くことができる<ref>例えば、{{harvtxt|Di Battista|Tamassia|1988}} や {{harvtxt|Freese|2004}} を参照</ref>。

「ハッセ図」という言葉は、個々のグラフの描画とは関係なく、抽象概念としての[[有向非循環グラフ]]の推移簡約を指すこともある。ただし、本項目ではこの意味では使わない。

== 例 ==
* { ''x'', ''y'', ''z'' } の[[冪集合]]には[[部分集合|包含]]による半順序があり、次のようなハッセ図で表される。

[[ファイル:Hasse diagram of powerset of 3.svg|center|250px|]]

* 60の全約数の[[集合]] ''A'' = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 } には、[[約数|整除性]]による半順序があり、次のようなハッセ図で表される。

[[ファイル:Lattice of the divisibility of 60.svg|center|250px]]

* 集合 { 1, 2, 3, 4 } には全部で15の[[集合の分割|分割]]があり、細分 (refinement) による半順序があり（より細かい分割の方が小さいとする）、次のようなハッセ図で表される。

[[ファイル:Lattice of partitions of an order 4 set.svg|center|250px]]

=== Bruhat order  ===
全ての[[コクセター群]] (''W'', ''S'') にはいくつかの半順序があり、これらをまとめて '''Bruhat order''' と呼ぶ。それらの定義は、生成系 ''S'' における被約語 (reduced word) に基づく。強い Bruhat order において、元 ''w'' が元 ''y'' より大きいとは、''y'' の被約語をプレフィックスとする ''w'' の被約語が存在する場合である。この順序についてのハッセ図は (''W'', ''S'') の[[ケイリーグラフ]]と一致する。[[対称群]] ''S''<sub>''n''</sub> の場合、ケイリーグラフは[[置換多面体]]である。''n''=3 なら、ハッセ図は1つの頂点が一番上にあり、1つの頂点が一番下にある（正）[[六角形]]となる。

== 動機 ==
半順序集合 (''S'', ≤) を視覚的に表現しようとした場合、どうすればよいだろうか? まず S の個々の元を頂点する[[グラフ理論|グラフ]]を描き、''u'' ≤ ''v'' という関係をグラフ内の辺 (''u'', ''v'') で表すとする。

このようにしてグラフを描いてみると、非常に混みあったグラフになる。実際、そのグラフには冗長な情報が多すぎる。半順序の必要条件は次の通りである。
*''a'' ≤ ''a'' （反射律）
* ''a'' ≤ ''b'' かつ ''b'' ≤ ''c'' なら ''a'' ≤ ''c'' （推移律）
* ''a'' ≤ ''b'' かつ ''b'' ≤ ''a'' なら ''a'' = ''b'' （反対称律）

さて、元々のグラフを考えてみると、まず ''u'' ≤ ''u'' という反射律が成り立つことから、ノード毎に (''u'', ''u'') というループが存在する。

そこで、より細かい[[集合の分割]]がより小さいとする半順序集合 ({1,2,3,4}, ≤) についてループを除外したグラフを作る。すると次のようなグラフが得られる。
[[ファイル:Lattice of partitions of an order 4 set redundant.svg|center|250px]]

しかし、このグラフでも冗長な情報がまだ存在する。半順序の必要条件には、推移律がある。上のグラフでは (''a'',''c'')、(''a'',''b'')、(''b'',''c'') という辺が描かれている。この場合 (''a'',''c'') という辺は他の2つの辺から存在を推測できるため、描く必要はない。

以上から、[[推移関係]]と[[反射関係]]を考慮して残った関係だけを辺として描く。すると、「例」の節の3つ目の図が得られる。

== 被覆関係 ==
記号的には、ハッセ図の全ての辺は ''x'' &lt; ''y'' という関係の (''x'', ''y'') の形であり（上述したようにループを排除するため条件が厳しくなっている）、''x'' &lt; ''z'' &lt; ''y'' となるような ''z'' は存在しない（推移律による辺を除外するためのもう1つの規則）。

この関係を「[[被覆関係]]」(cover relation)と呼び、ハッセ図はこの関係を使って定義されることが多い。半順序は、被覆関係の[[推移閉包]]である。

したがって ''S'' のハッセ図は、''y'' が ''x'' を被覆するような全ての順序対 (''x'', ''y'') の集合と定義することもできる。すなわち、ハッセ図は被覆関係の逆で識別することもできる。

== 「よい」ハッセ図 ==
ハッセ図は有限な半順序集合を扱う単純で直観的なツールであるが、「よい」図を描くのはやや難しい。実際、与えられた半順序集合についてハッセ図はいろんな形で描くことができる。単純な技法としては、最も小さい元を出発点として徐々に大きい方に向かって描いていくという方法があるが、これで生成される図はあまりよいとは言えず、対称性や順序の内部構造が容易に失われてしまう。

ここでは、集合 ''S'' = {''a'', ''b'', ''c'', ''d''} の[[冪集合]]を例として考える。すなわち、''S'' のあらゆる[[部分集合]]の集合 <math>\mathcal{P}(S)</math> である。冪集合は部分集合の包含関係 <math>\subseteq</math> で容易に順序付けできる。この順序を描いた3種類のハッセ図を以下に示す。

{| style="margin: 0 auto;"
| [[File:Hypercubeorder binary.svg|215px|]] ||&nbsp;&nbsp;&nbsp;|| [[File:Hypercubecubes binary.svg|300px|]] ||&nbsp;&nbsp;&nbsp;|| [[File:Hypercubestar binary.svg|229px|]]
|}

左端の図は最も単純な描き方をした場合に近い。5層になっていて、各層にある頂点は、元の数が等しい部分集合に対応している。下から2層目は元が1つの集合に対応するが、個々の頂点にどれを具体的に割り当てるかは様々な組合せがあるものの、これらを具体的に割り当てるとそれより上の層は自動的に固定される。図の複数の頂点のラベル付けをどのようにしても元の半順序が表せるため、これは自己同型の例でもある（特に断らない限り、[[辞書式順序]]を仮定することが推奨される）。

上の例は同じ順序についての異なるハッセ図を示しており、それぞれが元となる数学的構造の異なる面を反映している。左端の図は頂点の層ごとに元の数が対応している。右端の図はその構造の内部対称性を強く反映している。最後に真ん中の図は2つの立方体を繋いだような形になっており、冪集合 2<sup>''S''</sup> と [[:en:product order<!-- [[:ja:直積順序]] とリンク -->|product order]] 2 &times; 2<sup>{''a'', ''b'', ''c''}</sup> の間の関係を強調したものとなっている。

よりよい図を描くための様々な[[アルゴリズム]]が考案されているが、今のところよい図を描くには人間が介在した方がよい。もっとも、その人間もハッセ図を描くには一種の技量を必要とする。

== ポリトープ ==
ハッセ図は[[ポリトープ]]の組合せ的構造（頂点、辺、面などの階層）を図示するのに非常に役立つ。抽象ポリトープ論においては、ハッセ図（より正確には半順序集合）こそがポリトープである。

== 脚注・出典 ==
{{reflist}}

== 参考文献 ==
* {{citation |first=Garrett |last=Birkhoff |authorlink= |title=Lattice Theory |edition=Revised |publisher=[[アメリカ数学会|American Mathematical Society]] |year=1948|series=American Mathematical Society Colloquium Publications |volume=25|mr=0029876 |zbl=0033.10103 }}.
* {{citation|first=Garrett|last=Birkhoff|title=Lattice Theory|url={{google books|ePqVAwAAQBAJ|plainurl=yes}}|edition=Third|publisher=American Mathematical Society|year=1967|series=American Mathematical Society Colloquium Publications|volume=25|mr=0227053|zbl=0153.02501}}.
* {{citation |first1=G. |last1=Di Battista |first2=R. |last2=Tamassia |author2-link= |title=Algorithms for plane representation of acyclic digraphs |journal=Theoretical Computer Science |volume=61 |year=1988 |pages=175–178}}.
* {{citation |first=Ralph |last=Freese |contribution=Automated lattice drawing |title=Concept Lattices |publisher=Springer-Verlag |series=Lecture Notes in Computer Science |volume=2961 |pages=589–590 |year=2004}}. 詳しいプレプリントがオンラインで入手可能: [http://www.math.hawaii.edu/~ralph/Preprints/latdrawing.pdf].
* {{citation|first=B.|last=Schröder|title=Ordered Sets: An Introduction with Connections from Combinatorics to Topology|edition=Second|year=2016|url={{google books|66oqDAAAQBAJ|plainurl=yes}}|publisher=Birkhäuser|isbn=978-3-319-29786-6|mr=3469976|zbl=06560023}}
* {{citation |first=Henri Gustav |last=Vogt |publisher=Nony |year=1895 |page=91 |title=Leçons sur la résolution algébrique des équations|url={{google books|7Se7b8vjyVEC|plainurl=yes|page=91}}}}.

== 関連項目 ==
* [[束 (束論)|束論]]

==外部リンク==
{{Commonscat|Hasse diagrams}}
*[http://www.win.tue.nl/ida/demo/c1s1ja.html Hasse diagrams of divisors]
*[https://archive.is/20130426013300/www.flickr.com/photos/hexadecimal_time/2418492457/ Hasse diagram of logical connectives] ([[論理演算]])
*[http://www.math.northwestern.edu/~mlerma/courses/cs310-04w/notes/dm-relations.pdf How to draw hasse diagrams of binary relations]
*[http://mathworld.wolfram.com/HasseDiagram.html "Hasse Diagram" on MathWorld]

{{DEFAULTSORT:はつせす}}
[[Category:順序構造]]
[[Category:ダイアグラム]]
[[Category:グラフ描画]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]