さいごにはじめにコジマです。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次の正方行列\)を言います。ここも参考になります。今回の例の場合、隣接行列Aはこのように書けます。\(v_1とv_2が繋がってるから1本繋がってるから1\)\(v_1とv_3が繋がってるから1本繋がってるから1\)\(v_1とv_4が繋がってるから1本繋がってるから1\)ということです。見るとわかるのですが、対角成分に対して対象になります。ここまで分かれば基本情報の午前問は余裕で取れるのではないでしょうか。隣接行列は以下の性質を持つことがわかります。辺が繋がってるところは1になる対角成分は0になる対角成分に対して対象になるこれは単純グラフについてのみ成り立ちます。ならない場合というのも紹介しようかと思います。深い話これからは余談です。こんなグラフを考えてみます。頂点と辺と接続関数の関係を満たしているので紛れもなくグラフなんですけど、少し様子が違います。\(e_3とe_4がだぶってる\)\(e_7がv_5だけに繋がってる\)ということがわかります。1のように同じ接続を持つ辺を多重辺、2のように自分自身に繋がる辺をループといいます。単純グラフというのは多重辺とループを持たないグラフを言います。このグラフの接続行列を考えてみます。すると、先ほど挙げた接続行列のうち辺が繋がってるところは1になる対角成分は0になるの性質を満たさなくなります。先ほど挙げた隣接行列の性質は多重辺とループを持たない単純グラフについてのみ成り立つ性質であることを覚えておきましょう。試験で出たら見直し楽になると思います。隣接行列の対称性は有向グラフや重み付きのグラフの場合に失われることになりますが、ここまでは触れないでおくので気になる方は調べてみてくださいね。さいごにまとめ隣接行列は辺で繋がった頂点同士の関係を表したもの対角成分に対して対象になり、繋がってるところは1、繋がってないところは0上の性質は多重辺とループを持たない単純グラフの時に成り立つ数学系の記事もエンジニアに必要とされる時代が来るか〜〜〜???なんて思いつつ自分も数学がすごいできるわけじゃないので日々精進です。この記事を面白いまたは役に立ったと思ってくれた方は是非私のTwitter(@kojimanotech)をフォローしてくれたらうれしいです!以上、コジマでした。微分をやっていきたいと思います。SES企業を卒業し、新たなステップへ踏み出した。WordPress.。