平成２９年度 春期 応用情報技術者試験問題と解説
問３
ノードとノードの間のエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列に対応させて、ノード間にエッジが存在する場合は1で、エッジが存在しない場合は0で示す。
ａ ｂ ｃ ｄ ｅ ｆ
┌ ┐
ａ│０ １ ０ ０ ０ ０│
ｂ│１ ０ １ １ ０ ０│
ｃ│０ １ ０ １ １ ０│
ｄ│０ １ １ ０ ０ ０│
ｅ│０ ０ １ ０ ０ １│
ｆ│０ ０ ０ ０ １ ０│
└ ┘
ア 
イ 
ウ 
エ 
正解
ウ
解説
隣接行列は、エッジがあれば1、エッジがなければ0を表すものである。
ノードａはｂとのみエッジがある。
ノードｂはａ、ｃ、ｄとエッジがある。
ノードｃはｂ、ｄ、ｅとエッジがある。
ノードｄはｂ、ｃとエッジがある。
これらを満たすのはウである。
ア ｂとｃにエッジがない。
イ ｃとｄにエッジがない。
ウ 正しい。
エ ｄとｅにエッジがあり、隣接行列を満たさない。
| 問２ | 目次 | 問４ |