ハッセ図

順序理論において、ハッセ図（/ ˈhæsə /、ドイツ語: [ ˈhasə ] ）は、有限半順序集合を推移的還元図の形で表すために用いられる数学的図の一種である。具体的には、半順序集合に対して、${\displaystyle (S,\leq )}$1つは、${\displaystyle S}$平面上の頂点として、その頂点から上向きに伸びる線分または曲線を描画します。${\displaystyle x}$別の頂点へ${\displaystyle y}$いつでも${\displaystyle y}$カバー${\displaystyle x}$（つまり、いつでも${\displaystyle x\neq y}$、${\displaystyle x\leq y}$そして、${\displaystyle z}$と異なる${\displaystyle x}$そして${\displaystyle y}$と${\displaystyle x\leq z\leq y}$これらの曲線は互いに交差しても構いませんが、端点以外の頂点に接してはなりません。このような図は、頂点にラベルを付けることで、その部分順序を一意に決定します。

ハッセ図はヘルムート・ハッセ（1898～1979）にちなんで名付けられました。ギャレット・バーコフによれば、ハッセが効果的に使用したことからそのように呼ばれています。^{[ 1 ]}しかし、ハッセがこれらの図を最初に使用したわけではありません。ハッセより前の例として、アンリ・ギュスターヴ・フォークトによる1895年の著作に見られます。^{[ 2 ] [ 3 ]}ハッセ図は元々、部分的に順序付けられた集合を手作業で描画するための技法として考案されましたが、最近ではグラフ描画技術を使用して自動的に作成されています。^{[ 4 ]}

一部の資料では、「ハッセ図」という語句は異なる意味を持ちます。それは、グラフの描画とは無関係に、半順序集合の被覆関係から得られる有向非巡回グラフです。 ^{[ 5 ]}

ハッセ図は有限半順序集合を扱うためのシンプルで直感的なツールですが、「良い」図を描くのはかなり難しいことがわかっています。その理由は、一般的に、与えられた半順序集合に対してハッセ図を描く方法は数多く存在するからです。順序の最小要素から始めて、より大きな要素を段階的に描いていくという単純な手法では、多くの場合、非常に悪い結果になります。順序の対称性や内部構造が容易に失われてしまうのです。

以下の例は、この問題を説明しています。包含関係で順序付けられた4要素集合の冪集合を考えてみましょう。${\displaystyle \subseteq }$以下に、この部分順序を表す4つの異なるハッセ図を示します。各部分集合には、特定の要素が部分集合に含まれているか（1）、含まれていないか（0）を示すバイナリ符号化でラベル付けされたノードがあります。

最初の図は、冪集合が次数付き半順序集合であることを明確に示しています。2番目の図は同じ次数構造を持っていますが、一部の辺を他の辺よりも長くすることで、4次元立方体が2つの3次元立方体の組み合わせによる和集合であり、同様に正四面体（抽象的な3次元多面体）が2つの三角形（抽象的な2次元多面体）を結合したものであることを強調しています。3番目の図は、構造の内部対称性の一部を示しています。4番目の図では、頂点が4×4のグリッド状に配置されています。

半順序が、2つの辺が交差しないハッセ図として描ける場合、その被覆グラフは上方平面であると言われる。上方平面性および交差のないハッセ図の構成に関する多くの結果が知られている。

• 描画する部分順序が格子である場合、順序次元が最大で 2である場合に限り、交差なしで描画できます。 ^{[ 6 ]}この場合、順序次元を実現する 2 つの線形順序における要素の位置からデカルト座標を導出し、描画を反時計回りに 45 度回転させることで、交差のない描画を見つけることができます。
• 半順序が最小要素を最大で 1 つ持つか、最大要素を最大で 1 つ持つ場合、非交差ハッセ図を持つかどうかを線形時間でテストできます。 ^{[ 7 ]}
• 複数の始点と終点を持つ半順序が交差のないハッセ図として描画できるかどうかを判定することはNP完全である。 ^{[ 8 ]}しかし、半順序の推移的縮小の連結点と3連結成分の数でパラメータ化すれば、交差のないハッセ図を見つけることは固定パラメータで扱いやすい。 ^{[ 9 ]}
• 半順序の要素のy座標が指定されている場合、そのような図が存在するならば、それらの座標割り当てを尊重する交差のないハッセ図を線形時間で見つけることができます。 ^{[ 10 ]}特に、入力半順序集合が次数付き半順序集合である場合、各頂点の高さがそのランクに比例する交差のないハッセ図が存在するかどうかを線形時間で判定できます。

ソフトウェアエンジニアリング／オブジェクト指向設計では、ソフトウェアシステムのクラスとこれらのクラス間の継承関係は、ハッセ図の一種であるクラス図を用いて表現されることが多い。クラス図では、クラスを接続するエッジは実線で描かれ、スーパークラスの端には開いた三角形が描かれる。

• ウィキメディア・コモンズにある関連メディア：
  • ハッセ図（ギャラリー）
  • ハッセ図（カテゴリ）
• ワイスタイン、エリック W.、「ハッセ図」、MathWorld