【離散数学】ハッセ図とは?書き方を分かりやすく解説!

ハッセ図
先生
先生

ハッセ図の書き方が分からないっす…

ハッセ図って最初はどうやって書けばいいのかよくわからないですよね。

今回はハッセ図の書き方が分からなくて困っている方のために、ハッセ図を軽く説明した後、その書き方について簡単に説明しました。

ぜひ最後までご覧ください!

初学者におすすめの離散数学の参考書4選

ハッセ図とは?

ハッセ図は「順序を図で表して、視覚的に関係が簡単に分かるようにしたもの」です。

順序に関しては「半順序と全順序を分かりやすく解説!」の最初で解説しているのでぜひご覧ください。

簡単な例

例えば、集合$A=\{1,2,3,4,5,6,7,8\}$として、「$aRb$=$a$は$b$を割り切る」と定義された集合$A$上の二項関係$R$を考えましょう。

この関係$R$を使うと、次のようないくつかの式を作ることが出来ます。

$$1R2, 1R3, …, 1R8$$

$$2 R 4 R 8$$

$$2 R 6, 3 R 6$$

でも、これって何を表しているのかよく分かりませんし、数字同士の関係が見えにくいですよね。

そこでハッセ図の出番です!

先生
先生

上の順序関係をハッセ図で表すと次のように書けます。

くるる
くるる

一目で数字間の関係が分かるっすね!

それでは、このハッセ図の書き方を説明していきます!

先生
先生

ハッセ図の書き方講座1

先ほどのハッセ図の書き方を説明します。要素が数字のハッセ図なら大体同じ感じでやれば書けます。

ステップ1 一段目の数字を書く

ハッセ図は下から上に向かって書いていきます。上に上がれば上がるほど、関係が薄くなると考えればいいでしょう。

まず、一番下の一段目の数字が何かを考えなければなりません。

集合$A=\{1,2,3,4,5,6,7,8\}$として、「$aRb$=$a$は$b$を割り切る」と定義された$A$上の二項関係$R$を考えているわけですが、「$1$」は他の数字を全て割り切ります。

ということは、他の数字全てと繋げることが出来るのです。てことは、一段目に来そうですよね?だから、

こんな感じになってるんだろうな~と予想を付けることが出来ます。

大分フワッとした説明ですが、何となく感覚は分かると思います。

ステップ2 一段目の数字と連結出来る数字を全て連結する

一段目の「$1$」に連結出来る数字を全て連結していきます。連結というのは、$aRbRc$というように、関係$R$でいくつかの数字を繋げることを指します。今回の例では

$$1 R 2 R 4 R 8$$

$$1 R 3 R 6$$

$$1 R 5$$

$$1 R 7$$

という4つの式が出来ます。

一番枝が長くなるように連結しましょう。$1R2R6$という式を作ることもできますが、$1R2R4R8$の方が長くなるので、後者を採用するのです。

また、基本的には辞書式で数字を繋げていきます。つまり、$1R2$の次は、$1R3$ということです。

そして、この4式に従って、上向きにハッセ図の枝を伸ばしていきます。結果が次の図になります。

見やすくするために、横の数字は揃えましょう。

ステップ3 残りの線を書く

ステップ2で書いた図は実は足りない部分があります。$2R6$という順序を足さなければならないのです。すると、

というハッセ図になり、これが完成図です。

このように、引き忘れている線がないかをしっかり確認するようにしましょう。

ポンタ
ポンタ

なるほどね!

ハッセ図の書き方講座2

さて、数字のハッセ図を説明してきましたが、実は「集合」のハッセ図も存在するのです。

例えば、次のような集合の集合$B$を考えましょう。

そして、集合$B$上の関係「$\subseteqq$」を考えます。この関係$\subseteqq$においては、

$$\{a\} \subseteqq \{a,b\} \subseteqq \{a,b,c\}$$

$$\{b\} \subseteqq \{b,c\} \subseteqq \{a,b,c\}$$

というような順列を作ることができます。それらを基にハッセ図を作ると、

こんな感じになります。

このハッセ図の書き方を説明します。

先生
先生

ステップ1 一段目の集合を書く

集合$B$の要素で、「$\phi$」は一番要素数の少ない集合です。だから絶対に$\phi \subseteqq other$という形になります。

なので、「$\phi$」が一番下に来ることは簡単に予想できるでしょう。つまり、次のような図になるはずです。

ステップ2 一段目の集合と連結出来る集合を全て連結する

関係$\subseteqq$を使うと、

$$\phi \subseteqq \{a\} \subseteqq \{a,b\} \subseteqq \{a,b,c\}$$

$$\phi \subseteqq \{b\} \subseteqq \{b,c\} \subseteqq \{a,b,c\}$$

$$\phi \subseteqq \{c\} \subseteqq \{c,a\} \subseteqq \{a,b,c\}$$

という3つの式を作れます。この3式が表す関係をハッセ図に書き足すと、

となります。

ステップ3 残りの線を書く

関係$\subseteqq$を使うと、

$$\phi \subseteqq \{a\} \subseteqq \{c,a\}$$

$$\phi \subseteqq \{b\} \subseteqq \{a,b\}$$

$$\phi \subseteqq \{c\} \subseteqq \{b,c\}$$

という3式も作れることが分かります。よって、この3式が表す関係をハッセ図に書き足すと、

となり、ハッセ図の完成です。

まとめ

ハッセ図を長々と説明してきましたが、実際に書いてみればすぐに書けるようになります。ここで説明したやり方でなくとも、自分の書きやすいやり方でやればいいと思います。

・ハッセ図は「順序を図で表して、視覚的に関係が簡単に分かるようにしたもの」

・ハッセ図は下から上に書く

・上に行くほど、関係の薄い要素になる

二項関係
おすすめの参考書

初学者におすすめな参考書を調査してまとめてみました。良かったら参考にしてください。

初学者におすすめの離散数学の参考書4選

コメントを残す

CAPTCHA


PHP Code Snippets Powered By : XYZScripts.com