きっかけ
今年の基本情報技術者試験に隣接行列の問題が出題されました。
ちょうど読んでいた蟻本にグラフの説明が載っていたので、まとめてみました。
グラフとは
物や状態といった対象同士の結びつき方を表すための表現法。
グラフは頂点（ノード）と辺（エッジ）からなります。
辺に向きがないグラフを無向グラフ、辺に向きがあるグラフを有効グラフといいます。
#隣接行列と無向グラフ
隣接行列では｜V｜×｜V｜の二次元配列ｇでグラフを表現します。g[i][j]はi番目の頂点とj番目の頂点の関係を表すことができます。
無向グラフの場合は「i番の頂点とj番目の頂点が辺で結ばれているか」の情報さえあればいいので、g[i][j]とg[j][i]の値を頂点iと頂点jが辺で結ばれているなら１、そうでなければ０となることで無向グラフを表現します。
有向グラフでは頂点から頂点へ方向を表すため、g[i][j]＝g[j][i]とはならない。
⇒無向グラフではg[i][j]＝g[j][i]となります。
行列に対角線を引くと対象になり、同じ内容になります。
例 4×4の隣接行列
| i \ j | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 |
| 2 | 1 | 0 | 1 | 1 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 0 | 1 | 0 | 0 |
例 上記の無向グラフ
#令和元年秋期 基本情報技術者試験 午前問３
【問題】
ノードとノードの間にエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列を対応させて、ノード間にエッジが存在する場合は１で、エッジが存在しない場合は０で示す。
【解き方】
左からノードの繋がりを確認して、不正解を除外していく。
・[b][c]=[c][b]=1、[b][d]=[d][b]=1より、ノードｂはノードｃとｄに繋がっている。
⇒ 選択肢：ア 不正解
・[c][d]=[d][c]=1、[c][e]=[e][c]=1より、ノードcはノードｂ以外にｄとeに繋がっている。
⇒ 選択肢：イ 不正解
・ノードｄはｂとｃ以外に繋がりはない。
⇒ 選択肢：エ 不正解
⇒ 答え 選択肢：ウ
読んでいた本
[プログラミングコンテストチャレンジブック [第2版]](https://www.amazon.co.jp/dp/B00CY9256C/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1"プログラミングコンテストチャレンジブック [第2版]")
最後に
前回より間が空きましたが、今回が２回目の記事になります。
時間があれば、実際にプログラミングをしてから記事を加筆します。
記事の内容に誤りや問題等がありましたら、訂正します。
よければコメントお願いします。