ウカマル応用情報技術者ログイン

平成29年度 春期 応用情報技術者 問3

テクノロジ系

ノードとノードの間のエッジの有無を,隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合,グラフで表現したものはどれか。ここで,ノードを隣接行列の行と列に対応させて,ノード間にエッジが存在する場合は1で,エッジが存在しない場合は0で示す。

abcdef
a010000
b101100
c010110
d011000
e001001
f000010
選択肢

選択肢の図

図の内容(文字)
ア
ノードa,b,c,d,e,fが横一列に並ぶ。エッジ:a−b,c−d,d−e,e−f,c−e(上側の弧),b−d(下側の弧)。b−c間にエッジはない。
イ
ノードa,b,c,d,e,fが横一列に並ぶ。エッジ:a−b,b−c,d−e,e−f,c−e(上側の弧),b−d(下側の弧)。c−d間にエッジはない。
ウ
ノードa,b,c,d,e,fが横一列に並ぶ。エッジ:a−b,b−c,c−d,e−f,c−e(上側の弧),b−d(下側の弧)。d−e間にエッジはない。
エ
ノードa,b,c,d,e,fが横一列に並ぶ。エッジ:a−b,b−c,c−d,d−e,e−f,c−e(上側の弧),b−d(下側の弧)。
正解と解説

正解 ウ

行列の1は、a−b、b−c、b−d、c−d、c−e、e−fの6本です。d−eのエッジがない図を選びます。

無向グラフの隣接行列は対角線をはさんで対称なので、対角線より右上の1だけを読めば全エッジが分かります。a行はb、b行はcとd、c行はdとe、e行はfが1です。よってエッジはa−b、b−c、b−d、c−d、c−e、e−fの6本です。d行のe列は0なので、d−e間にエッジはありません。この6本だけをもつ図はウです。

ア:b−cのエッジがありません。行列にないd−eのエッジもあります。

イ:c−dのエッジがありません。行列にないd−eのエッジもあります。

エ:d行のe列は0なのに、d−eのエッジがあります。エッジが7本で、1本多くなっています。

出典:平成29年度 春期 応用情報技術者試験 問3

全年度から出題。10問で実力を判定します。登録不要。

出典:平成29年度 春期 応用情報技術者試験 問3(独立行政法人情報処理推進機構)

解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方