グラフ理論

Introduction

sorry, this page is Japanese only.

いよいよ私も三回生になり、グラフ理論の授業が始まりました。ということで、グラフ理論の基本的な定義を書いていこうと思います。

最後に説明する隣接行列については実装を行いましたので、以下の記事もよろしければご覧ください。

隣接行列の実装

グラフのイメージ
グラフ理論のグラフとは高校数学で習う二次関数などとは違います。
例えば駅などを創造してください。各駅間に線路が通っていますね。このような、駅、線路の集まりのことをグラフといいます。次の絵で確認してもらえるとイメージしやすいかと思います。

このようなものをグラフといいます。グラフは二点間がどうつながっているかだけを保存し、実際の距離や位置関係は保存しません。

このような向きのない（各駅を行き来でき、一方通行ではない）グラフを無向グラフをいいます。反対に向きのある（一方通行しかできない）グラフを有向グラフといいます。

グラフの定義

グラフではある空でない集合E,Vを考えます。Eの要素をedge(辺）、Vの要素をvertex(頂点)といいます。

ここで以下のような写像を考えます。

$$g:E \rightarrow V \times V$$

この時(E,V,g)で定義される空でない空間のことをグラフといいます。

写像で捉えるグラフ

写像gというのは、Eの要素、つまり辺を対応する(始点、終点)というV×Vの集合の要素に送ります。gは写像ですので、写像の定義より、Eのどの要素の始点と終点が対応していることになります。つまり、辺がどこにもつながっていないということはあり得ません。反対にすべてのV×Vの要素がEの要素のどれかに対応しているのであればgは全射になります。

隣接行列

隣接行列とはどのvertexと、どのvertexがつながっているかを行列で表します。例を見るのが理解するのには早いと思うので、例を挙げて説明します。

上のグラフのイメージで出てきたグラフの例を考えましょう。隣接行列は以下のようになります。

$$　\[ 

adj = \left(

\begin{array}{cccccc}

0 & 1 & 0 & 0 & 1 & 0 \\

1 & 0 & 1 & 1 & 0 & 0 \\

0 & 1 & 0 & 1 & 0 & 0 \\

0 & 1 & 1 & 0 & 0 & 0 \\

1 & 0 & 0 & 0 & 0 & 1 \\

0 & 0 & 0 & 0 & 0 & 1 \\

$$

石山駅 -> 一列目

山科駅 -> 二列目

京都駅 -> 三列目

三条京阪 -> 四列目

米原駅 -> 五列目

大垣駅 -> 六列目

として、[n,m]ではnの駅からmの駅へ線路がつながているのであれば1、そうでなければ0をとります。これが隣接行列です。

Reference

https://ja.wikipedia.org/wiki/グラフ理論