基本情報技術者試験 令和元年度 秋季 午前 問3
データ構造におけるグラフ、無向グラフ、有向グラフ、隣接行列についての問題。
--------------------------
令和元年度 秋期 午前 問3
ノードとノードの間のエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列に対応させて、ノード間にエッジが存在する場合は 1 で、エッジが存在しない場合は 0 で示す。
--------------------------
解説
データ構造におけるグラフの問題。
データ要素であるノード（節点、点）とそのノード間のつながりを示すエッジ（辺、線）でデータ構造を示すもの。
この問題の場合、ノードは a や b 、エッジはそれらを繋ぐ線で表現されている。
a や b が電車の駅名であれば、路線図の様になる（エッジがある ＝ 線路が直接つながっている）。
グラフで表現しているデータ構造は、隣接行列でも表現できる。
上は問題文の隣接行列に色々と書き込んだもの。
問題文には "ノードを隣接行列の行と列に対応させて、ノード間にエッジが存在する場合は 1 で、エッジが存在しない場合は 0 で示す" とある。
- 青色で協調している行を見れば、ノード a とその他のノード ( b ～ f ) との間にエッジが存在するかがわかる。1 になっている部分は a - b のみなので、ノード a はノード b とのみエッジをもっている。
- 橙色で協調している行を見れば、ノード d とその他のノード( a, b, c, e, f ) との間にエッジが存在するかがわかる。1 になっている部分は d - b と d - c なので、ノード d はノード b および ノード c とエッジをもっている。
- 各ノードは自分自身とはエッジをもたないため、赤線部分は全て 0 になる。また、この行列は赤線で対称になっている。この問題は無向グラフ（向きが無い）なので、"a から見た b との繋がり" と "b から見た a との繋がり" が等価になる。有向グラフ（向きが有る）の場合、一方通行のようなエッジが存在するので等価とはならず、赤線で対称にはならなくなる。
どの選択肢もノード a はノード b とのみエッジをもっているので、ノード a に関しては正しい。
ノード d を見ると、ノード b とノード c とのみエッジをもつ選択肢はウのみである。
ということで、正解は選択肢ウになる。
ちなみに、有向グラフの場合はノード間のエッジが向きをもつ矢印の様になるので、以下のようなグラフと隣接行列になる（はず）。
橙色の部分、a から見た b は 1 になるが、b から見た a は 0 となっている。
これは a → b という向きをもつエッジを表現している。
前後の問題はこちら。
