【数学】隣接行列の理解をなんとなくじゃないものにする【グラフ理論】

【数学】隣接行列の理解をなんとなくじゃないものにする【グラフ理論】

はじめに

コジマです。

IPA試験で隣接行列の問題が出たということで、グラフ理論の話を少ししてみようかと思います。

あの問題見ましたが、隣接行列わからなくても規則性から推測して解くことも可能だったかと思います。

グラフとは?

いっぱい話したいことはあるけどなるべく端折ります。
隣接行列を理解するために

グラフとは以下の関係を持つ図形のことを言います。

  • 頂点
  • 接続関数

\(頂点の集合をV(G),辺の集合をE(G),接続関数をI_G(e),グラフをGと表します。\)

グラフを扱う数学の分野を「グラフ理論」と言います。
有名なところだと路線図なんかグラフ理論を使ってます。

グラフは例を見た方がわかりやすいです。(手書きゴメン)

\(V(G)は頂点の集合です。\)
\(E(G)は辺の集合です。\)
\(I_Gは接続関数です。\)

接続関数は辺を変数として、それに接続する2頂点を表します。

\(\Psi\)で表すこともありますが、私の持ってる本では\(I\)で表しているのでそれに則ります。
参考書籍はこちら

隣接行列とは

隣接行列と名前は難しそうでも何も気にする必要はないです。
大体の場合は辺のあるところを1にすればいいだけです。

でも正確にはそうじゃないので、書いておきますね。

隣接行列の定義
\(グラフGの頂点がn個あるとき,頂点v_i,v_jを結ぶ辺の本数をij要素に持つn次の正方行列\)
を言います。

ここも参考になります。
https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-02.pdf#search=’%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96+%E9%9A%A3%E6%8E%A5%E8%A1%8C%E5%88%97′

今回の例の場合、隣接行列Aはこのように書けます。

\(v_1とv_2が繋がってるから1本繋がってるから1\)
\(v_1とv_3が繋がってるから1本繋がってるから1\)
\(v_1とv_4が繋がってるから1本繋がってるから1\)

ということです。
見るとわかるのですが、対角成分に対して対象になります。

ここまで分かれば基本情報の午前問は余裕で取れるのではないでしょうか。

隣接行列は以下の性質を持つことがわかります。

  • 辺が繋がってるところは1になる
  • 対角成分は0になる
  • 対角成分に対して対象になる

これは単純グラフについてのみ成り立ちます。
そうならない場合というのも紹介しようかと思います。

ちょっとだけ深い話

これからは余談です。
こんなグラフを考えてみます。


頂点と辺と接続関数の関係を満たしているので紛れもなくグラフなんですけど、少し様子が違います。

  1. \(e_3とe_4がだぶってる\)
  2. \(e_7がv_5だけに繋がってる\)

ということがわかります。
1のように同じ接続を持つ辺を多重辺、2のように自分自身に繋がる辺をループといいます。
単純グラフというのは多重辺とループを持たないグラフを言います。

このグラフの接続行列を考えてみます。

このようになります。

すると、先ほど挙げた接続行列のうち

  • 辺が繋がってるところは1になる
  • 対角成分は0になる

の性質を満たさなくなります。

あくまで、先ほど挙げた隣接行列の性質は
多重辺とループを持たない単純グラフについてのみ成り立つ性質であることを覚えておきましょう。
試験で出たら見直し楽になると思います。

さらに、隣接行列の対称性は有向グラフ重み付きのグラフの場合に失われることになりますが、
ここまでは触れないでおくので気になる方は調べてみてくださいね。

さいごに

まとめ

  • 隣接行列は辺で繋がった頂点同士の関係を表したもの
  • 対角成分に対して対象になり、繋がってるところは1、繋がってないところは0
  • 上の性質は多重辺とループを持たない単純グラフの時に成り立つ

数学系の記事もエンジニアに必要とされる時代が来るか〜〜〜???

なんて思いつつ自分も数学がすごいできるわけじゃないので日々精進です。

この記事を面白いまたは役に立ったと思ってくれた方は是非私のTwitter(@kojimanotech)を
フォローしてくれたらうれしいです!

以上、コジマでした。


数学カテゴリの最新記事