「有向グラフって？隣接行列って？」【幾何学の基礎シリーズ】グラフ理論編その4

本記事の内容
有向グラフ
隣接行列
皆様のコメントを下さい！
結

本記事の内容

本記事は「有向グラフとは何か？」「隣接行列とは何か？」について解説する記事です。

本記事を読むにあたり、グラフと路について知っている必要があるため、以下の記事も合わせて御覧ください。

↓「グラフとは何か？」の記事

↓「路とは何か？」の記事

有向グラフ

まず、有向グラフについて解説します。

「有向グラフ」を一言で。

シンプルなコンセプトです。
有向グラフとは

すべての辺に向きが与えれたグラフのこと。

です。

ここで注意なのが、今まで考えてきた無向グラフというのは、辺に向きが”無い”のではなくて(字面ではそうですが)、各辺に対して2つの向き(往復で2つ)を持つようなグラフです。
全ての辺に対して、その辺が持つ2つの向きの内、どちらか1つを選んだグラフのことを有向グラフといいます。

何が言いたいか、というと

無向グラフは、向きがないグラフではない。

ということです。

「有向グラフ」を数学的に表現します。

有向グラフとはいえ、グラフですので、「グラフとは何か？」という問と”ほぼ”同じ答えです。

有向グラフ

集合$V,E^o$に対して、$V$と$E^o$の対$X^o=(V,E^o)$が以下を満たすとき$X^o$は有向グラフ(directed graph)であるという。

$V\cap E^o=\emptyset$
写像$i^o:E^o\to V\times V$が存在する。

ここで、$i^o(e)=\left( o(e),t(e)\right)\ (e\in E^o)$とすることで、$o:E^o\to V$、$t:E^o\to V$を得ます。
ちなみに、$X^o$やら$i^o$やら$E^o$やらの$o$はoriented(日：方向づけられた)のoです。

一般のグラフと何が違うんですか？

一般のグラフの説明と何が違うか、という話をします。
一般のグラフとは以下でした。

グラフ

集合$V,E$に対して、$V$と$E$の対$X=(V,E)$が以下を満たすとき$X$はグラフであるという。

$V\cap E=\emptyset$
次の性質を満たす写像$i:E\to V\times V$、$\iota:E\to E$が存在する。

$\iota^2\left(=\iota\circ\iota \right)={\rm id}_E\quad$(ただし、${\rm id}_E$は$E$の恒等写像)
任意の$e\in E$に対して以下が成り立つ。

詳しくは【幾何学の基礎シリーズ】グラフ理論編その1をご覧ください。

端的に何が違うか、というと「$\iota:E\to E$が存在しない。」という点が違います。
むしろ、一般のグラフはこの$\iota:E\to E$が存在すると仮定しているため全ての辺の向きに逆向きがあることが保証されています。
その逆向きの存在を保証している写像$\iota:E\to E$が存在しない、というのが有向グラフです。

無向グラフから有向グラフを作る事ができます。

この章の最初に、有向グラフは

すべての辺に向きが与えれたグラフのこと。

と述べました。
そして、無向グラフは向きが存在しないのではなくて、往復の2つの方向があり、有向グラフはこの2方向の内1つの方向を選んだグラフだ、と述べました。

故に、無向グラフから有向グラフを作り出すことが出来ます。
「2つある向きのうち、片方を選んだグラフが有向グラフなんだからそりゃそうだよね」というシンプルな話です。

この主張を数学的にまとめると以下です。

命題1.

グラフ$X=(V,E)$に対して、 $$ E^o\cup \overline{E^o}=E,\quad E^o\cap \overline{E^o}=\emptyset $$ となるような$E^o\subset E$を取れば、$X^o=(V,E^o)$は有向グラフである。ただし、 $$ \overline{E^o}=\left\{\bar{e}\in E\middle| e\in E^o\right\} $$ である。

命題1.の証明

これはもはや証明する必要がないような感じです。
というのも、$X=(V,E)$はグラフなので、以下を満たすような写像$i:E\to V\times V$、$\iota:E\to E$が存在しています。

$\iota^2\left(=\iota\circ\iota \right)={\rm id}_E\quad$(ただし、${\rm id}_E$は$E$の恒等写像)
任意の(e\in E)に対して
$$
\iota(e)\neq e,\quad i\left(\iota(e)\right)=\tau\left(i(e)\right)
$$
が成り立つ。

そして、$E^o\subset E$ですから、$i^o:E^o\to V\times V$を$i$の$E^o$への制限として定めれば$X^o=(V,E^o)$が有向グラフです。

命題2.の証明終わり

隣接行列

次に、有向グラフを行列に対応させることを考えます。
結論を言ってしまえば、有向グラフの頂点の繋がり方を表す行列が隣接行列です。

隣接行列のイメージ

$A=\left( a_{ij}\right)$行列と有向グラフ$X^o=(V,E^o)$とを以下の規則で対応させます。

頂点の集合$V$は$\{1,\dots,n\}$に対応させる。
$a_{ij}>0$のとき、そしてこのときのみ、$i$を始点とし、$j$を終点とする有向辺が存在する。

このように規則を定めることで、行列がグラフと対応付けられます。

例2. 次の行列に対する有向グラフを図示してみます。

$$
B=
\begin{pmatrix}
0&0&0&0.7\\
0.1&0.2&0&0\\
0&0.4&0&0.5\\
0.2&0&0.2&0.8\\
\end{pmatrix}
$$

$a_{11}=0$により、$1$という名前のついた頂点を始点、$1$という名前のついた頂点を終点とする有向辺が存在しません。
すなわち、頂点$1$にはループ辺が存在しません。
$a_{12}=0$により、$1$という名前のついた頂点を始点、$2$という名前のついた頂点を終点とする有向辺が存在しません。
$a_{13}=0$も$a_{12}$と同じ。
$a_{14}=0.7>0$により、$1$という名前のついた頂点を始点、$4$という名前のついた頂点を終点とする有向辺が存在します。
$a_{21}=0.1>0$により、$2$という名前のついた頂点を始点、$1$という名前のついた頂点を終点とする有向辺が存在します。
$a_{22}=0.1>0$により、$2$という名前のついた頂点を始点、$2$という名前のついた頂点を終点とする有向辺が存在します。
すなわち、頂点$2$にはループ辺が存在します。
$a_{23}=0$も$a_{12}$と同じ。
$a_{24}=0$も$a_{12}$と同じ。
$a_{31}=0$も$a_{12}$と同じ。
$a_{32}=0.4>0$により、$3$という名前のついた頂点を始点、$2$という名前のついた頂点を終点とする有向辺が存在します。
$a_{33}=0$も$a_{12}$と同じ。
$a_{34}=0.5>0$により、$3$という名前のついた頂点を始点、$4$という名前のついた頂点を終点とする有向辺が存在します。
$a_{41}=0.2>0$により、$4$という名前のついた頂点を始点、$1$という名前のついた頂点を終点とする有向辺が存在します。
$a_{42}=0$も$a_{12}$と同じ。
$a_{43}=0.2>0$により、$4$という名前のついた頂点を始点、$3$という名前のついた頂点を終点とする有向辺が存在します。
$a_{44}=0.8>0$により、$4$という名前のついた頂点を始点、$4$という名前のついた頂点を終点とする有向辺が存在します。
すなわち、頂点$4$にはループ辺が存在します。

以上のことをまとめると、グラフは以下です。

実は、$B$の正体が上記のグラフの隣接行列です。

で、隣接行列って何ですか？

先程行ったのは、行列に対してグラフを対応付ける、ということでした。
逆に、有限な有向グラフ$X^o$に付随する行列を構成することが出来ます。
これが隣接行列です。

隣接行列

有限な有向グラフ$X^o=(V,E^o)$に対して、$V$に番号付けして、頂点の集合を$V=\{1,\dots,n\}$とする。$i,j\in V$に対して、

$a_{ij}=i$を始点、$j$を終点とする有向辺の数

と定め、$A=\left(a_{ij} \right)$とおく。この行列を有限な有向グラフ$X^o$に付随する隣接行列(adjacency matrix)という。

要するに、隣接行列というのはグラフの頂点の繋がり方を表現している行列のことです。
上記の

$a_{ij}=i$を始点、$j$を終点とする有向辺の数

を数式で書けば、
$$
a_{ij}=\left|\{e\in E^o\middle|o(e)=i,\ t(e)=j\}\right|
$$
です。

補足

隣接行列のところで、「$V$に番号付けして、頂点の集合を$V=\{1,\dots,n\}$とする。」と書きました。
実は、厳密に考えるとこれはちょっと説明が足りていません。
以前の記事で、グラフ$X=(V,E)$の頂点の集合$V$と辺の集合$E$は、$V\cap E=\emptyset$を満たしさえすれば何でも良いわけで、$V$を椅子、$E$を机の集合としても良い、という話をしました。
この立場にたてば、仮に$V$を椅子の集合とした場合、$V=\{1,\dots,n\}$とは厳密にはなりえません。
しかし、机やら椅子やらを○個、○脚と数えるように、「モノ」に対して「数」を全単射で対応させることが出来ます。
つまり、「$V$に番号付けして、頂点の集合を$V=\{1,\dots,n\}$とする。$i,j\in V$に対して、」という文言を厳密に書くとすれば、

$\left|V\right|=n$のとき、全単射$\varphi:V\to\{1,\dots,n\}$が存在する。このとき$i,j\in\varphi\left( \{1,\dots,n\}\right)$に対して、

となるわけです。
このように、全単射が存在するが故に、2つの集合を同一と捉え、厳密には等しくないものを同一視する、ということが数学ではよくあります。

例3. 次の有限な有向グラフの隣接行列を求めてみます。

頂点が4つあるので、隣接行列は$(4,4)$型です。

$a_{11}$
$1$と名前がついた頂点にはループ辺が1つ存在するので、$a_{11}=1$です。
$a_{12}$
始点を$1$、終点を$2$とする有向辺は存在しないので$a_{12}=0$です。
$a_{13}$
始点を$1$、終点を$3$とする有向辺が1つ存在するので$a_{13}=1$です。
$a_{14}$
始点を$1$、終点を$4$とする有向辺は存在しないので$a_{14}=0$です。
$a_{21}$
始点を$2$、終点を$1$とする有向辺が1つ存在するので$a_{21}=1$です。
$a_{22}$
$2$と名前がついた頂点にはループ辺が存在しないので、$a_{22}=0$です。
$a_{23}$
始点を$2$、終点を$3$とする有向辺は存在しないので$a_{23}=0$です。
$a_{24}$
始点を$2$、終点を$4$とする有向辺が2つ存在するので$a_{21}=2$です。
$a_{31}$
始点を$3$、終点を$1$とする有向辺は存在しないので$a_{31}=0$です。
$a_{32}$
始点を$3$、終点を$2$とする有向辺は存在しないので$a_{32}=0$です。
$a_{33}$
$3$と名前がついた頂点にはループ辺が1つ存在するので、$a_{33}=1$です。
$a_{34}$
始点を$3$、終点を$4$とする有向辺は存在しないので$a_{34}=0$です。
$a_{41}$
始点を$4$、終点を$1$とする有向辺は存在しないので$a_{41}=0$です。
$a_{42}$
始点を$4$、終点を$2$とする有向辺は存在しないので$a_{42}=0$です。
$a_{43}$
始点を$4$、終点を$3$とする有向辺が1つ存在するので$a_{43}=1$です。
$a_{44}$
$4$と名前がついた頂点にはループ辺が存在しないので、$a_{22}=0$です。

以上をまとめると、このグラフの隣接行列は
$$
\begin{pmatrix}
1&0&1&0\\
1&0&0&2\\
0&0&1&0\\
0&0&1&0\\
\end{pmatrix}
$$
です。

隣接行列の転置行列

隣接行列の転置行列について考えてみます。
$A=\left( a_{ij}\right)$の転置行列$A^\top$は$a_{ji}$を$(i,j)$成分にもつ行列です。
これを隣接行列の視点で見てみると、始点を$j$、終点を$i$とするグラフの隣接行列担っています。
故に、隣接行列の転置行列は有向グラフの全ての有向辺を逆向きにした有向グラフの隣接行列を指しています。

命題4.

有向グラフ$X^o$の隣接行列を$A=\left( a_{ij}\right)$とする。このとき、$X^o$の有向辺の向きを全て逆向きにして得られる有向グラフ${X^o}^\top$の隣接行列は、$A^\top$である。

命題4.の証明

${X^o}^\top$の隣接行列を$B=\left( b_{ij}\right)$とします。
このとき、$b_{ij}$は${X^o}^\top$において、$i$から$j$に向かう有向辺の数です。
これは$X^o$において$j$から$i$に向かう有向辺の数です。
故に、$a_{ji}=b_{ij}$となり、証明完了です。

命題4.の証明終わり

皆様のコメントを下さい！

筆者が幾何学を専攻しようと思ったきっかけが本シリーズのグラフ理論ですが、それよりも前から幾何学模様が好きでした。
キレイだなあ、と思っていました。
思えば、小学校、中学校のころから図形の問題は得意でした。

一方で、中学生の頃は比例や１次関数が大の苦手でした。
「全然分からん」という感じでした。
にもかかわらず、高校に入り、微分積分を勉強するととたんに一番得意な分野になりました(高校生の時は)。

皆様は小中で得意だったことと高校で得意だったことは変わりましたか？
是非コメントで教えて下さい！

結

今回は、有向グラフ、隣接行列について解説しました。
それぞれ

有向グラフ：全ての辺に1つの向きが定まっているグラフ。
隣接行列：グラフの頂点の繋がり方を表す正方行列。

です。

次回は隣接行列の既約、可約と強連結について解説します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ３日以内にお答えします。
もし直ちに回答が欲しければその旨もコメントでお知らせください。直ちに対応いたします。

この記事の内容をより詳しく知りたい方は以下の書籍を御覧ください！

コメントをする

Warning: Undefined variable $req in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 32

Warning: Undefined variable $commenter in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34

Warning: Trying to access array offset on value of type null in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34

Warning: Undefined variable $aria_req in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34