うごく基本情報

令和元年度 秋期 問3

基礎理論 › グラフ理論・数値計算 △ ときどき出る

出典:令和元年度 秋期 基本情報技術者試験 午前 問3 の問題

出典:令和元年度 秋期 基本情報技術者試験 午前 問3

正解と解説を見る

正解:ウ

覚えること:隣接行列で 1 になっている組を書き出し、その辺だけをもつグラフを選ぶ。

行列の右上半分で 1 になっているのは、a-b、b-c、b-d、c-d、c-e、e-f の六つです(無向グラフなので左下は同じ内容)。この6本の辺だけをもつグラフがウです。d と e の間、a と c の間など、行列で 0 の組に線があるグラフは誤りです。辺の本数(6本)と、各ノードから出る線の数(b と c は3本)で絞ると速く解けます。アは b と c の間の辺がなく、d と e の間に辺があります。イは c と d の間の辺がなく、d と e の間に辺があります。エは d と e の間に辺がありますが、行列では d と e の間は 0 です。

解説はこのサイトが作成したものです。