応用情報技術者試験 応用情報技術者試験 平成29年度春期 午前 問3: ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対

正解

ウ. 選択肢ウのグラフ図

正答率 76.8%（491人中 377人が正解）

問題の解説

隣接行列は、行と列が同じノードに対応し、交点が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の個数と一致する。
• エエッジの本数や結び方が隣接行列と一致しないため誤り。行列から読み取れる接続パターンに合致しない。