問３
ノードとノードの間のエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列に対応させて、ノード間にエッジが存在する場合は１で、エッジが存在しない場合は０で示す。
ａ ｂ ｃ ｄ ｅ ｆ
┌ ┐
ａ│０ １ ０ ０ ０ ０│
ｂ│１ ０ １ １ ０ ０│
ｃ│０ １ ０ １ １ ０│
ｄ│０ １ １ ０ ０ ０│
ｅ│０ ０ １ ０ ０ １│
ｆ│０ ０ ０ ０ １ ０│
└ ┘
ア 
イ 
ウ 
エ 
正解
ウ
解説
隣接行列は、エッジがあれば１、エッジがなければ０を表すものである。
ノードａはｂとのみエッジがある。
ノードｂはａ、ｃ、ｄとエッジがある。
ノードｃはｂ、ｄ、ｅとエッジがある。
ノードｄはｂ、ｃとエッジがある。
これらを満たすのはウである。
ア ｂとｃにエッジがない。
イ ｃとｄにエッジがない。
ウ 正しい。
エ ｄとｅにエッジがあり、隣接行列を満たさない。
タグ：隣接行列
