ノードとノードの間のエッジの有無を,隣接行列を用いて表す。 ある無向グラフの隣接行列が次の場合,グラフで表現したものはどれか。 ここで,ノードを隣接行列の行と列に対応させて,ノード間にエッジが存在する場合は1で, エッジが存在しない場合は0で示す。
イ
ウ
エ
エッジが存在しないところに注目する。
ア:b と c の間がエッジが存在しないが、問題文のグラフでは、b − c は1であるので間違い。
イ:c と d の間がエッジが存在しないが、問題文のグラフでは、c − d は1であるので間違い。
ウ:d と e の間がエッジが存在しないが、問題文のグラフでは、c − d は0である。 よって、正しい。
エ:問題文のグラフでは、c − d は0である。d と e の間がエッジが存在するので間違い。
【平成29年春 問03 応用情報】