きっかけ

今年の基本情報技術者試験に隣接行列の問題が出題されました。
ちょうど読んでいた蟻本にグラフの説明が載っていたので、まとめてみました。

グラフとは

物や状態といった対象同士の結びつき方を表すための表現法。
グラフは頂点（ノード）と辺（エッジ）からなります。

辺に向きがないグラフを無向グラフ、辺に向きがあるグラフを有効グラフといいます。

隣接行列と無向グラフ

隣接行列では｜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版]")

最後に

前回より間が空きましたが、今回が２回目の記事になります。
時間があれば、実際にプログラミングをしてから記事を加筆します。

記事の内容に誤りや問題等がありましたら、訂正します。

よければコメントお願いします。

きっかけ

グラフとは

隣接行列と無向グラフ

令和元年秋期 基本情報技術者試験 午前問３

読んでいた本

最後に

令和元年秋期　基本情報技術者試験　午前問３　