ハッセ図（有向グラフによる順序関係の表現）

有向グラフ

以下では有向グラフ（directed graph）と呼ばれる概念を用いて順序関係を視覚的に表現する方法を解説します。

有向グラフそのものを、\begin{equation*}
D
\end{equation*}で表記することとします。有向グラフは以下の3つの要素から構成される概念です。

有向グラフ\(D\)を構成する1つ目の要素は頂点集合（set of vertices）であり、これを、\begin{equation*}V\left( D\right)
\end{equation*}で表記します。頂点集合\(V\left( D\right) \)の要素を頂点（vertex）と呼び、それを、\begin{equation*}v
\end{equation*}で表記します。\(v\in V\left(D\right) \)です。

有向グラフ\(D\)を構成する2つ目の要素は弧集合（set of arcs）であり、これを、\begin{equation*}A\left( D\right)
\end{equation*}で表記します。弧集合\(A\left( D\right) \)の要素を弧（arc）と呼び、それを、\begin{equation*}a
\end{equation*}で表記します。\(a\in A\left(D\right) \)です。

有向グラフ\(D\)を構成する3つ目の要素は、それぞれの弧に対して、頂点を成分とする順序対を1つずつ定める写像\begin{equation*}\psi _{D}:A\left( D\right) \rightarrow V\left( D\right) \times V\left(
D\right)
\end{equation*}であり、これを接続関数（incidence function）と呼びます。接続関数\(\psi _{D}\)が弧\(a\in A\left( D\right) \)に対して定める順序対が\(\left(v_{1},v_{2}\right) \in V\left( D\right) \times V\left( D\right) \)であることを、すなわち、\begin{equation*}\psi _{D}\left( a\right) =\left( v_{1},v_{2}\right)
\end{equation*}が成り立つことを、\begin{equation*}
\psi _{D}\left( a\right) =v_{1}v_{2}
\end{equation*}と表記できるもの定めます。このとき、弧\(a\)は頂点\(v_{1}\)を頂点\(v_{2}\)と結ぶ（join \(v_{1}\)to \(v_{2}\)）と言うとともに、頂点\(v_{1}\)を弧\(a\)の始点（tail）と呼び、もう一方の頂点\(v_{2}\)を弧\(a\)の終点（head）と呼びます。また、弧の始点と終点を総称して端点（ends）と呼びます。弧の端点は異なる点である必要はありません。弧の始点と終点を区別しない場合、弧のことを辺（edge）と呼びます。

有向グラフ\(D\)は以上の3つの要素からなる概念であり、そのことを、\begin{equation*}D=\left( A\left( D\right) ,E\left( D\right) ,\psi _{D}\right)
\end{equation*}で表記します。

有向グラフを図として描画する際には、頂点を点とみなし、弧をその始点から終点へ伸びる有向線分とみなします。

例（有向グラフ）

有向グラフ\(D\)の頂点集合\(V\left( D\right) \)と弧集合\(A\left( D\right) \)が、\begin{eqnarray*}V\left( D\right) &=&\left\{ 1,2,3,4\right\} \\
A\left( D\right) &=&\left\{ a,b,c,d,e,f,g\right\}
\end{eqnarray*}であるとともに、接続関数\(\psi _{D}:A\left( D\right) \rightarrow V\left(D\right) \times V\left( D\right) \)は、\begin{eqnarray*}\psi _{G}\left( a\right) &=&12,\quad \psi _{G}\left( b\right) =21,\quad
\psi _{G}\left( c\right) =32,\quad \psi _{G}\left( d\right) =43, \\
\psi _{G}\left( e\right) &=&41,\quad \psi _{G}\left( f\right) =42,\quad
\psi _{G}\left( g\right) =44
\end{eqnarray*}を満たすものとします。この有向グラフ\(D\)を以下に図示しました。

ハッセ図

集合\(A\)上に定義された二項関係\(\leq \)が半順序であることとは、\(\leq \)が反射律、反対称律、そして推移律\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq
x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq
z\right) \Rightarrow x\leq z\right] \end{eqnarray*}を満たすことを意味します。これらの性質に加えて、完備律\begin{equation*}
\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{equation*}を満たす場合、\(\leq \)を全順序と呼びます。以降の議論は、半順序と全順序の双方を対象としています。そこで、半順序と全順序を総称して順序と呼ぶこととします。集合\(A\)上に順序\(\leq \)が定義されている場合、それらの組\begin{equation*}\left( A,\leq \right)
\end{equation*}を順序集合と呼びます。ただし、順序\(\leq \)が定義されていることが文脈から明らかである場合、順序集合を、\begin{equation*}A
\end{equation*}とシンプルに表記できるものと定めます。順序集合を視覚的に表現するために有向グラフを利用したいところですが、具体的にどうすればよいでしょうか。

順序集合\(\left( A,\leq \right) \)が与えられたとき、集合\(A\)を有向グラフの頂点集合とみなします。その上で、任意の2つの頂点\(x,y\in A\)について、以下の関係\begin{equation*}x\leq y\Leftrightarrow \text{始点}x\text{から終点}y\text{へ伸びる弧が存在する}
\end{equation*}を満たすものとして弧と接続関数をそれぞれ定義すれば、半順序集合を有向グラフとして表現できます。

例（有向グラフとしての半順序）

以下の集合\begin{equation*}
A=\left\{ 1,2,3,4\right\}
\end{equation*}上に通常の大小関係\(\leq \)が定義されているものとします。大小関係は全順序であるため\(\left( A,\leq \right) \)は全順序集合です。大小関係の定義より、\begin{eqnarray*}1 &\leq &1,\quad 1\leq 2,\quad 1\leq 3,\quad 1\leq 4 \\
2 &\leq &2,\quad 2\leq 3,\quad 2\leq 4, \\
3 &\leq &3,\quad 3\leq 4, \\
4 &\leq &4
\end{eqnarray*}が成り立ちます。この全順序集合を有向グラフ\(D\)として表現します。頂点集合は、\begin{equation*}V\left( D\right) =A=\left\{ 1,2,3,4\right\}
\end{equation*}であり、弧集合は、\begin{equation*}
A\left( D\right) =\left\{
a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7},a_{8},a_{9},a_{10}\right\}
\end{equation*}であり、接続関数\(\psi_{D}:A\left( D\right) \rightarrow V\left( D\right) \times V\left( D\right) \)は、\begin{eqnarray*}\psi _{G}\left( a_{1}\right) &=&11,\quad \psi _{G}\left( a_{2}\right)
=21,\quad \psi _{G}\left( a_{3}\right) =13,\quad \psi _{G}\left(
a_{4}\right) =14, \\
\psi _{G}\left( a_{5}\right) &=&22,\quad \psi _{G}\left( a_{6}\right)
=23,\quad \psi _{G}\left( a_{7}\right) =24, \\
\psi _{G}\left( a_{8}\right) &=&33,\quad \psi _{G}\left( a_{9}\right) =34,
\\
\psi _{G}\left( a_{10}\right) &=&44
\end{eqnarray*}を満たします。この有向グラフ\(D\)を以下に図示しました。ただし、弧の名称を省略しています。

有向グラフを利用すれば順序集合を視覚的に表現できることが明らかになりました。さらに、以下で解説するように、順序の性質を上手く利用することにより、図示すべき情報量を減らすことができます。

順序集合\(\left( A,\leq \right) \)を有向グラフとして表現しようとしている状況を想定します。さて、順序\(\leq \)は反射律\begin{equation*}\forall x\in A:x\leq x
\end{equation*}を満たすため、有向グラフの頂点\(x\in A\)を任意に選んだとき、始点と終点がともに\(x\)であるような弧（このような弧をループと呼びます）が必ず存在します。つまり、順序集合を有向グラフとして表現する場合、それぞれの頂点からループが伸びていることは確定しているため、それらをわざわざ描く必要はありません。

有向グラフの2つの異なる頂点\(x,y\in A\)に関して、\begin{equation}x\leq y \quad \cdots (1)
\end{equation}が成り立つものとします。つまり、有向グラフにおいて\(x\)から\(y\)へ伸びる弧が存在するということです。加えて、\begin{equation}x\leq z\wedge z\leq y \quad \cdots (2)
\end{equation}を満たす\(x,y\)とは異なる頂点\(z\in A\)が存在するものとします。つまり、有向グラフにおいて\(x\)から\(z\)へ伸びる弧と\(z\)から\(y\)へ伸びる弧がともに存在するということです。順序\(\leq \)は推移律\begin{equation*}\forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow
x\leq z\right] \end{equation*}を満たすため、\(\left( 2\right) \)が成り立つ場合には\(\left( 1\right) \)が成り立つことが確定しているため、\(\left( 1\right) ,\left( 2\right) \)がともに成り立つ場合、\(x\)から\(y\)へ伸びる弧をわざわざ描く必要はありません。逆に言うと、2つの異なる頂点\(x,y\)について\(\left( 1\right) \)が成り立つ一方で\(\left( 2\right) \)を満たす第3の頂点\(z\)が存在しない場合にのみ、\(x\)から\(y\)へ伸びる弧を描けばよいということになります。

有向グラフの2つの異なる頂点\(x,y\in A\)に関して、\begin{equation*}x\leq y
\end{equation*}が成り立つものとします。つまり、有向グラフにおいて\(x\)から\(y\)へ伸びる弧が存在するということです。順序\(\leq \)は反対称律\begin{equation*}\forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \end{equation*}を満たすため、このとき、\begin{equation*}
y\leq x
\end{equation*}は成り立ちません。つまり、有向グラフにおいて\(y\)から\(x\)へ伸びる弧は存在しないということです。言い換えると、有向グラフにおいて2つの異なる頂点\(x,y\)が弧によって接続されている場合、その弧は1本だけであることが保証されます。そこで、「有向グラフにおいてすべての弧は下から上へ伸びる」というルールを採用した上で、2つの異なる頂点\(x,y\)について\(x\leq y\)が成り立つ場合に\(x\)を\(y\)よりも下部へ描けば、有向グラフにおいて弧の矢印をわざわざ描く必要はありません。

改めて整理しましょう。順序集合\(\left( A,\leq \right) \)を有向グラフとして表現する際には、以下の方針にしたがうことにより有向グラフに記載すべき情報を減らすことができます。

1. 任意の頂点\(x\in A\)について、\(x\leq x\)を図示する必要はない。
2. 3つの異なる頂点\(x,y,z\in A\)について、\begin{equation*}x\leq y\wedge x\leq z\wedge z\leq y\end{equation*}が成り立つ場合には、\(x\leq y\)を図示する必要はない。
3. 2つの異なる頂点\(x,y\in A\)について、\(x\leq y\)が成り立つ場合には、\(x\)を\(y\)よりも下部に描く。弧の矢印は不要。

以上の方針のもと、順序集合から得られる図をハッセ図（Hasse diagram）と呼びます。

例（ハッセ図）

以下の集合\begin{equation*}
A=\left\{ 1,2,3,4\right\}
\end{equation*}上に通常の大小関係\(\leq \)が定義されているものとします。大小関係は全順序であるため\(\left( A,\leq \right) \)は全順序集合です。大小関係の定義より、\begin{eqnarray*}1 &\leq &1,\quad 1\leq 2,\quad 1\leq 3,\quad 1\leq 4 \\
2 &\leq &2,\quad 2\leq 3,\quad 2\leq 4, \\
3 &\leq &3,\quad 3\leq 4, \\
4 &\leq &4
\end{eqnarray*}が成り立ちます。先に確認したように、この全順序集合を有向グラフ\(D\)として表現したものが以下の図です。

ただし、先の議論を踏まえると、以下のループ\begin{equation*}
1\leq 1,\quad 2\leq 2,\quad 3\leq 3,\quad 4\leq 4
\end{equation*}を省略することができます。また、\begin{equation*}
1\leq 2,\quad 1\leq 3,\quad 2\leq 3
\end{equation*}が成立しているため\(1\leq 3\)を省略でき、\begin{equation*}1\leq 2,\quad 1\leq 4,\quad 2\leq 4
\end{equation*}が成立しているため\(1\leq 4\)を省略でき、\begin{equation*}2\leq 3,\quad 3\leq 4,\quad 2\leq 4
\end{equation*}が成立しているため\(2\leq 4\)を省略できます。したがって、図示すべき情報は、\begin{equation*}1\leq 2,\quad 2\leq 3,\quad 3\leq 4
\end{equation*}だけです。加えて、\(\leq \)のもとでより小さい頂点をより下方へ描くことになります。すると、以下のハッセ図が得られます。

演習問題