平成29年秋期試験午前問題 問6

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

  • 06a.gif
  • 06i.gif
  • 06u.gif
  • 06e.gif
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
各隣接行列からノード間のエッジを抽出し、図を描いて木構造になっているものを導きます。木構造とは1つの根と複数の節点および節点(根を含む)同士を結ぶ辺で構成され、ループをもたないデータ構造です。
  • ノード間のエッジは"1-2","1-5","2-3","3-4","4-5"の5つです。
    06aa.gif
    全体がループになっているので木ではありません。
  • ノード間のエッジは"1-2","1-5","2-3","2-4"の4つです。
    06ii.gif
    ループが存在しないため木構造になっています。よって、これが正解です。
  • ノード間のエッジは"1-2","1-4","2-3","3-4","3-5"の5つです。
    06uu.gif
    1-2-3-4間がループ構造になっているので木ではありません。
  • ノード間のエッジは"1-2","1-3","2-3","3-4","3-5","4-5"の6つです。
    06ee.gif
    1-2-3間および3-4-5間がループ構造になっているので木ではありません。

Pagetop