基本情報技術者試験 ap-2017h29h-a 午前 問3: ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対

問題本文

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

選択肢

• ア.ア
• イ.イ
• ウ.ウ
• エ.エ

正解

ウ. ウ

解説

隣接行列は、行と列が同じノードに対応し、交点が1ならその2ノード間にエッジがあることを表す（無向グラフなので対称行列になる）。行を1つずつ読むとエッジは a-b、b-c、b-d、c-d、c-e、e-f の6本である。この接続パターン（aはbだけと、bはa・c・dと、c・dは互いに結ばれ、e-fが端で結ばれる）に一致するグラフが選択肢ウである。

選択肢ごとの解説

• ア.エッジの接続が隣接行列と一致しない。たとえばb・c・d間の結ばれ方やe・f付近の接続が行列の1の位置（b-c、b-d、c-d、c-e、e-f）と食い違うため誤り。
• イ.同じく一部のエッジが行列と一致しない。行列に存在しないエッジがあったり、必要なエッジが欠けているため誤り。
• ウ.正しい。a-b、b-c、b-d、c-d、c-e、e-fの6本がすべて図と一致し、各ノードの次数（aは1本、bは3本、cは3本、dは2本、eは2本、fは1本）も行列の各行の1の個数と一致する。
• エ.エッジの本数や結び方が隣接行列と一致しないため誤り。行列から読み取れる接続パターンに合致しない。