はじめに
コジマです。
IPA試験で隣接行列の問題が出たということで、グラフ理論の話を少ししてみようかと思います。
あの問題見ましたが、隣接行列わからなくても規則性から推測して解くことも可能だったかと思います。
グラフとは？
いっぱい話したいことはあるけどなるべく端折ります。
隣接行列を理解するために
- 頂点
- 辺
- 接続関数
\(頂点の集合をV(G),辺の集合をE(G),接続関数をI_G(e),グラフをGと表します。\)
グラフを扱う数学の分野を「グラフ理論」と言います。
有名なところだと路線図なんかグラフ理論を使ってます。
例
グラフは例を見た方がわかりやすいです。(手書きゴメン)
接続関数は辺を変数として、それに接続する2頂点を表します。
隣接行列とは
隣接行列と名前は難しそうでも何も気にする必要はないです。
大体の場合は辺のあるところを1にすればいいだけです。
でも正確にはそうじゃないので、書いておきますね。
\(グラフGの頂点がn個あるとき,頂点v_i,v_jを結ぶ辺の本数をij要素に持つn次の正方行列\)
を言います。
今回の例の場合、隣接行列Aはこのように書けます。
ということです。
見るとわかるのですが、対角成分に対して対象になります。
ここまで分かれば基本情報の午前問は余裕で取れるのではないでしょうか。
隣接行列は以下の性質を持つことがわかります。
- 辺が繋がってるところは1になる
- 対角成分は0になる
- 対角成分に対して対象になる
これは単純グラフについてのみ成り立ちます。
そうならない場合というのも紹介しようかと思います。
ちょっとだけ深い話
これからは余談です。
こんなグラフを考えてみます。
頂点と辺と接続関数の関係を満たしているので紛れもなくグラフなんですけど、少し様子が違います。
- \(e_3とe_4がだぶってる\)
- \(e_7がv_5だけに繋がってる\)
ということがわかります。
1のように同じ接続を持つ辺を多重辺、2のように自分自身に繋がる辺をループといいます。
単純グラフというのは多重辺とループを持たないグラフを言います。
このグラフの接続行列を考えてみます。
このようになります。
すると、先ほど挙げた接続行列のうち
- 辺が繋がってるところは1になる
- 対角成分は0になる
の性質を満たさなくなります。
あくまで、先ほど挙げた隣接行列の性質は
多重辺とループを持たない単純グラフについてのみ成り立つ性質であることを覚えておきましょう。
試験で出たら見直し楽になると思います。
さらに、隣接行列の対称性は有向グラフや重み付きのグラフの場合に失われることになりますが、
ここまでは触れないでおくので気になる方は調べてみてくださいね。
さいごに
- 隣接行列は辺で繋がった頂点同士の関係を表したもの
- 対角成分に対して対象になり、繋がってるところは1、繋がってないところは0
- 上の性質は多重辺とループを持たない単純グラフの時に成り立つ
数学系の記事もエンジニアに必要とされる時代が来るか〜〜〜？？？
なんて思いつつ自分も数学がすごいできるわけじゃないので日々精進です。
この記事を面白いまたは役に立ったと思ってくれた方は是非私のTwitter(@kojimanotech)を
フォローしてくれたらうれしいです！
以上、コジマでした。
