隣接行列（行列による順序関係の表現）

隣接行列（行列を用いた二項関係の表現）

実数を長方形に配列したもの\begin{equation*}
M=\begin{pmatrix}
m_{11} & m_{12} & \cdots & m_{1n} \\
m_{21} & m_{22} & \cdots & m_{2n} \\
\cdots & \cdots & \cdots & \cdots \\
m_{m1} & m_{m2} & \cdots & m_{mn}\end{pmatrix}\end{equation*}を\(\mathbb{R} \)上の行列と呼びます。行列\(M\)を構成する個々の実数\begin{equation*}m_{ij}\quad \left( i=1,\cdots ,m;\ j=1,\cdots ,n\right)
\end{equation*}を行列の\(ij\)成分と呼びます。これは行列\(M\)の第\(i\)行、第\(j\)列に現れる実数です。行列\(M\)が\(m\)個の行と\(n\)個の列を持つ場合、\(m\times n\)行列と呼びます。

行の個数と列の個数が一致する行列、すなわち\(n\times n\)行列\begin{equation*}M=\begin{pmatrix}
m_{11} & m_{12} & \cdots & m_{1n} \\
m_{21} & m_{22} & \cdots & m_{2n} \\
\cdots & \cdots & \cdots & \cdots \\
m_{n1} & m_{n2} & \cdots & m_{nn}\end{pmatrix}\end{equation*}を次数\(n\)の正方行列と呼びます。正方行列の成分の中でも、行番号と列番号が一致する成分\begin{equation*}m_{11},m_{22},\cdots ,m_{nn}
\end{equation*}を\(M\)の対角成分と呼びます。

集合\(A\)上の二項関係\begin{equation*}R\subset A\times A
\end{equation*}が与えられた状況を想定します。加えて、\(A\)は有限集合であるものとし、その成分を、\begin{equation*}A=\left\{ a_{1},a_{2},\cdots ,a_{n}\right\}
\end{equation*}と表記します。その上で、任意の\(i,j\in \left\{ 1,\cdots,n\right\} \)について、\begin{equation*}m_{ij}=\left\{
\begin{array}{cc}
1 & \left( if\ \left( a_{i},a_{j}\right) \in R\right) \\
0 & \left( if\ \left( a_{i},a_{j}\right) \not\in R\right)
\end{array}\right.
\end{equation*}を\(ij\)成分として持つ次数\(n\)の正方行列を定義し、これを、\begin{equation*}M_{R}
\end{equation*}で表記します。これを二項関係\(R\)に関する隣接行列（adjacency matrix）と呼びます。

順序関係の隣接行列

集合\(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*}とシンプルに表記できるものと定めます。

順序関係\(\leq \)もまた二項関係であるため、順序関係\(\leq \)が定義された集合\(A\)が有限集合である場合、隣接行列\(M_{\leq }\)を用いて順序関係\(\leq \)を表現できます。

順序関係の隣接行列はどのような性質を備えているのでしょうか。

条件\(\left( a\right) \)は、二項関係\(\leq \)の隣接行列\(M_{\leq }\)の対角成分はいずれも\(1\)であることを意味します。また、条件\(\left(b\right) \)は、二項関係の隣接行列\(M_{\leq }\)において対称的な位置にある2つの成分の少なくとも一方が\(0\)であることを意味します。また、条件\(\left( b\right) \)は、\begin{equation*}\forall i,j\in \left\{ 1,\cdots ,n\right\} :\left( i\not=j\Rightarrow
m_{ij}\cdot m_{ij}=0\right)
\end{equation*}と必要十分です。つまり、二項関係の隣接行列\(M_{\leq }\)において対称的な位置にある2つの成分の積は\(0\)になるということです。

演習問題