ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は1で，エッジが存在しない場合は0で示す。
解答
ウ
解説
隣接行列では、ノード（節点）間のエッジ（枝・辺）の有無を確認することができます。
例えば、問題の行列の1行目に着目すると、aとbの交点のみ1、他は0となっているため、ノードaとノードbの間にエッジがあり、ノードaとノードa、ノードc、ノードd、ノードe、ノードfの間にはエッジがない、となります。
よって、問題の行列から、エッジが存在するノード間は、{a, b}、{b, c}、{b, d}、{c, d}、{c, e}、{e, f}、ということがわかります。
これを満たす図は、ウです。
参考情報
分野・分類
| 分野 | テクノロジ系 |
| 大分類 | 基礎理論 |
| 中分類 | 基礎理論 |
| 小分類 | 応用数学 |
出題歴
- FE 令和元年度秋期 問3
