基本情報技術者試験 - 令和4年6月修了 - 問4

問題

ノードとノードの間のエッジの有無を,隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合,グラフで表現したものはどれか。ここで,ノードを隣接行列の行と列に対応させて,ノード間にエッジが存在する場合は1で,エッジが存在しない場合は0で示す。

ア
イ
ウ
エ

正解と解説

正解ウ
分野テクノロジ系 › 基礎理論 › 基礎理論 › 応用数学

解説

「隣接行列」は、グラフのノード(頂点)同士がエッジ(辺)でつながっているかどうかを、行列で表したものです。行と列に同じノードを並べて、行のノードと列のノードの間にエッジがあれば1、なければ0を書きます。

読み取る手順は、行ごとに1が書かれている列を探し、その行のノードと列のノードの間にエッジがあると考えるだけです。問題の隣接行列を、行ごとに読み取ります。

行のノード1が書かれている列エッジ
aba-b
ba、c、db-a、b-c、b-d
cb、d、ec-b、c-d、c-e
db、cd-b、d-c
ec、fe-c、e-f
fef-e

無向グラフでは、「bからaへ」と「aからbへ」が同じエッジなので、隣接行列は対角線を軸にして左右対称になります。対角線上がすべて0なのは、ノード自身へのエッジ(ループ)がないことを表します。重複をまとめると、エッジはa-b、b-c、b-d、c-d、c-e、e-fの6本です。

この6本のエッジだけでできているグラフを探します。各選択肢のグラフには、次の違いがあります。

× ア(図の1つ目)b-cのエッジがなく、行列にはないd-eのエッジがあります。
× イ(図の2つ目)c-dのエッジがなく、行列にはないd-eのエッジがあります。
○ ウ(図の3つ目)a-b、b-c、b-d、c-d、c-e、e-fの6本がすべて一致しています。
× エ(図の4つ目)6本のエッジはそろっていますが、行列にはないd-eのエッジが余分にあります。
同一問題 : 〔令3修1問3〕〔令1秋問3〕
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる