平成29年 秋期 応用情報技術者 午前 問6

ノード1〜5をもつグラフを隣接行列で表したもののうち、木となるものはどれか。
ここで、隣接行列i 行j 列目の成分は、ノードi とノードj を結ぶエッジがある場合は1、ない場合は0とする。

ア
イ
ウ
エ

答え　イ

---

【解説】
それぞれの隣接行列をグラフにすると

ア
イ
ウ
エ

になり、木になっているのはイである。

---

【キーワード】
・隣接行列

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

戻る 一覧へ 次へ