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

問題

隣接行列Aで表されるグラフはどれか。ここで,隣接行列とは,n個の節点から成るグラフの節点ViとVjを結ぶ枝が存在するときは第i行第j列と第j行第i列の要素が1となり,存在しないときは0となるn行n列の行列である。

ア
イ
ウ
エ

正解と解説

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

解説

「グラフ」は、点(節点)と、点同士を結ぶ線(枝)で、ものの関係を表したものです。例えば、駅を節点、駅同士をつなぐ線路を枝と見れば、路線図もグラフの一種です。

グラフを図ではなく数で表す方法の一つが「隣接行列」です。節点がn個のとき、n行n列の表を作り、節点ViとVjが枝で結ばれていれば第i行第j列に1、結ばれていなければ0を書きます。問題の定義では、枝に向きがないので、第i行第j列と第j行第i列は必ず同じ値になります。

行列を読むときは、行ごとに「その節点がどの節点と結ばれているか」を調べます。

  1. 第1行は0,1,1,0なので、V1はV2とV3に結ばれています。
  2. 第2行は1,0,0,1なので、V2はV1とV4に結ばれています。
  3. 第3行は1,0,0,1なので、V3はV1とV4に結ばれています。
  4. 第4行は0,1,1,0なので、V4はV2とV3に結ばれています。

枝は、V1-V2、V1-V3、V2-V4、V3-V4の4本で、4つの節点がちょうど四角形の形につながるグラフです。また、各行の1の個数は、その節点につながる枝の本数を表します。この行列ではすべての行が2個なので、どの節点にも枝が2本ずつ出ています。選択肢の図でも、枝の本数を数えると見分けやすくなります。

× アア(1番目の図)は、V1の枝がV4への1本だけです。第1行の1が1個になるので、行列と合いません。
× イイ(2番目の図)は、すべての節点が互いに結ばれた形で、枝が6本あります。各節点に枝が3本ずつ出ているので、行列とは異なります。
× ウウ(3番目の図)は、V1に枝が3本(V2,V3,V4)出ています。第1行の1が3個になるはずなので、行列と合いません。V2-V3の枝があることも行列と異なります。
○ エエ(4番目の図)は、V1-V2、V1-V3、V2-V4、V3-V4の4本で、行列から読み取った枝とすべて一致します。
同一問題 : 〔平24春問3〕
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる