平成29年 春期 応用情報技術者 午前 問3

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

 ア  
 イ  
 ウ  
 エ  


答え ウ


解説
隣接行列はノード間にエッジが存在する場合は1で、エッジが存在しない場合は0なので、エッジが存在するのはa-b間、b-c間、b-d間、c-d間、c-e間、e-f間でこれをグラフにまとめると
 
(ウ)になります。


キーワード
・隣接行列

キーワードの解説
  • 隣接行列
    グラフを表現するための行列で、n 個の頂点があるグラフを表現するときはn ×n の行列を作り、頂点a b に枝(経路)があるときは、行列の第a 行第b 列と第b 行第a 列の要素が1になります。

もっと、「隣接行列」について調べてみよう。

戻る 一覧へ 次へ