WIIS

教材一覧
教材一覧
教材検索
RELATION

ハッセ図(有向グラフと順序)

目次

次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

有向グラフ

以下では有向グラフ(directed graph)と呼ばれる概念を用いて順序関係を視覚的に表現する方法を解説します。有向グラフを\(D\)などアルファベットの大文字で表記します。有向グラフを構成する1つ目の要素は頂点(vertex)と呼ばれる要素からなる集合であり、これを頂点集合(set of vertices)と呼びます。有向グラフ\(D\)の頂点集合を\(V\left( D\right) \)で表記します。有向グラフを構成する2つ目の要素は(arc)と呼ばれる要素からなる集合であり、これを弧集合(set of arcs)と呼びます。有向グラフ\(D\)の弧集合を\(A\left( D\right) \)で表記します。頂点集合と弧集合は互いに素であるものと仮定します。つまり、\begin{equation*}V\left( D\right) \cap A\left( D\right) =\phi
\end{equation*}です。有向グラフを構成する3つ目の要素は、それぞれの弧に対して頂点を成分とする順序対を1つずつ定める写像であり、これを接続関数(incidence mathrmtion)と呼びます。有向グラフ\(D\)の接続関数を\(\psi _{D}:A\left( D\right) \rightarrow V\left( D\right)\times V\left( D\right) \)で表記します。その上で、接続関数\(\psi _{D}\)が弧\(a\)に対して定める順序対が\(\left(v_{1},v_{2}\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\)が与えられているものとします。つまり、\(A\)上に定義された二項関係\(\leq \)は反射律反対称律に加えて推移律を満たすということ、具体的には、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left( x\leq y\wedge y\leq
x\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*}が成り立つということです。半順序集合\(A\)を視覚的に表現するために有向グラフを利用したいところですが、具体的にどうすればよいでしょうか。

半順序集合\(A\)が与えられたとき、それを有向グラフの頂点集合とみなした上で、2つの頂点\(x,y\in A\)について、\begin{equation*}x\leq y
\end{equation*}が成り立つ場合には始点\(x\)から終点\(y\)へ伸びる弧が存在するものとみなす、という方針のもとで半順序集合を有向グラフとして表現できます。ただし、以下で順番に解説するように、半順序の性質を上手く利用することにより、図示すべき情報量を減らすことができます。

まず、半順序\(\leq \)は反射律を満たすため、有向グラフの頂点\(x\in A\)を任意に選んだとき、始点と終点がともに\(x\)であるような弧(このような弧をループと呼ぶ)が必ず存在します。したがって、それぞれの頂点から伸びるループを有向グラフから削除しても問題ありません。言い換えると、半順序\(\leq \)の反射律より、有向グラフにおいてそれぞれの頂点からループが伸びていることは確定しているため、それらをわざわざ描く必要はないということです。

2つの異なる頂点\(x,y\in A\)に関して\(x\leq y\)が成り立つものとします。つまり、有向グラフにおいて\(x\)から\(y\)へ伸びる弧が存在するということです。加えて、\(x\leq z\)と\(z\leq y\)をともに満たす\(x,y\)とは異なる頂点\(z\in A\)が存在するものとします。つまり、有向グラフにおいて\(x\)から\(z\)へ伸びる弧と\(z\)から\(y\)へ伸びる弧がともに存在するということです。ただし、半順序\(\leq \)の推移律より、\(x\leq z\)と\(z\leq y\)が成り立つ場合には\(x\leq y\)が成り立つことが確定しているため、以上の条件が満たされる場合、\(x\)から\(y\)へ伸びる弧をわざわざ描く必要はありません。言い換えると、半順序\(\leq \)の推移性より、2つの異なる頂点\(x,y\)について\(x\leq y\)が成り立つ場合には、\(x\leq z\)と\(z\leq y\)をともに満たす\(x,y\)とは異なる頂点\(z\)が存在しない場合にのみ、\(x\)から\(y\)へ伸びる弧を描けば十分であるということです。

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

以上の方針のもと、半順序集合から得られる図をハッセ図(Hasse diagram)と呼びます。以下が具体例です。

例(ハッセ図)
集合\(A=\left\{ 1,2,3,4\right\} \)上に大小関係\(\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*}が成り立つため、これを有向グラフとして描くと以下を得ます。

図:有向グラフ
図:有向グラフ

ただ、\(\leq \)は反射律と推移律を満たすため、ハッセ図において以下の情報\begin{equation*}1\leq 2,\quad 2\leq 3,\quad 3\leq 4
\end{equation*}だけを描写すれば十分です。加えて、\(\leq \)のもとでより小さい頂点をより下方へ描くことになります。すると以下のハッセ図が得られます。

図:ハッセ図
図:ハッセ図

 

演習問題

問題(ハッセ図)
集合\(A=\left\{ 1,2,3,4,5\right\} \)上に定義された二項関係\(R\)が、\begin{eqnarray*}R &=&\{\left( 1,1\right) ,\left( 1,3\right) ,\left( 1,4\right) ,\left(
1,5\right) ,\left( 2,2\right) ,\left( 2,3\right) ,\left( 2,4\right) ,\left(
2,5\right) , \\
&&\left( 3,3\right) ,\left( 3,4\right) ,\left( 3,5\right) ,\left( 4,4\right)
,\left( 5,5\right) \}
\end{eqnarray*}で与えられているものとします。\(R\)が半順序であることを示すとともに、\(R\)をハッセ図を用いて表現してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(ハッセ図)
集合\(A=\left\{ 1,2,3,4,6,12,24\right\} \)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x|y
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x|y\)は\(y\)が\(x\)の倍数であることを表します。\(R\)は半順序です。\(R\)をハッセ図を用いて表現してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

半順序
n次元空間上の標準的順序

n次元空間上に定義される標準的順序と呼ばれる二項関係は半順序である一方で全順序ではありません。

半順序
半順序(半順序集合)

反射律、反対称律、推移律を満たす二項関係を半順序や順序などと呼びます。また、半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素以下であると言います。半順序を定義した上で、半順序の具体例を提示します。

半順序
狭義半順序(狭義半順序集合)

非対称律と推移律を満たす二項関係を狭義半順序や狭義順序などと呼びます。また、狭義半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素より小さいと言います。狭義半順序を定義した上で、狭義半順序の具体例を提示します。

半順序
半順序と狭義半順序の関係

半順序から狭義半順序を生成する方法や、逆に、狭義半順序から半順序を生成する方法を解説するとともに、両者の間に成立する関係を紹介します。

全順序
全順序(全順序集合)

反射律、反対称律、推移律、完備律を満たす二項関係、すなわち完備律を満たす半順序を全順序や線型順序などと呼びます。全順序を定義した上で、全順序の具体例を提示します。

全順序
全順序と狭義全順序の関係

全順序から狭義全順序を生成する方法や、逆に、狭義全順序から全順序を生成する方法を解説するとともに、両者の間に成立する関係について解説します。

全順序
順序部分集合

順序集合A上に定義されている順序のもとで、Aの非空な部分集合Xが順序集合になっている場合、XをAの順序部分集合と呼びます。

全順序
整列順序関係(整列集合)

全順序集合の任意の非空な部分集合が最小限を持つ場合、このような全順序集合を整列集合と呼びます。また、整列集合上に定義された全順序を整列関係と呼びます。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

関係