解説

隣接行列からグラフを復元する問題です。隣接行列は、行と列にノードを対応させ、ノード間にエッジ（辺）が存在すれば1、存在しなければ0を格納するグラフの表現方法で、無向グラフでは対角線に関して対称な行列になります。与えられた行列から1の位置を読み取ってエッジを列挙すると、a行はb列のみ1 → a-b、b行はc列・d列が1 → b-c と b-d、c行はd列・e列が1 → c-d と c-e、e行はf列が1 → e-f となり、エッジは全部で a-b、b-c、b-d、c-d、c-e、e-f の6本です。この6本と過不足なく一致するのはウのグラフです。ウは直線上の a-b、b-c、c-d、e-f の接続に加えて、b から d への弧と c から e への弧をもち、d-e 間にはエッジがありません。隣接行列の問題は、行列側からエッジを列挙し、各選択肢のグラフのエッジ数と構成を1本ずつ照合するのが最も確実な解法です。1の個数（対称行列なので12個＝エッジ6本）を先に数えておくと検算にも使えます。

なぜ他の選択肢は違うのか

選択肢 ア

アのグラフには b-c 間のエッジがなく、代わりに d-e 間にエッジがあります。行列を見ると b行c列＝1 なので b-c のエッジは必須であり、d行e列＝0 なので d-e のエッジは存在してはいけません。2か所で行列と矛盾しています。グラフの直線部分の接続関係（どの隣り合うノードがつながっているか）を行列の値と1つずつ突き合わせれば、確実に不一致を発見できます。

選択肢 イ

イのグラフには c-d 間のエッジがなく、代わりに d-e 間にエッジがあります。行列では c行d列＝1 なので c-d は必要であり、d行e列＝0 なので d-e は不要です。一見ウと似た形をしていますが、直線部分の接続が1か所ずれています。弧（b-d、c-e）だけでなく、直線部分の各エッジも行列と照合することが正確な判別のポイントです。

選択肢 エ

エのグラフは正解ウがもつ6本のエッジに加えて d-e 間にも余分なエッジがあり、合計7本になっています。行列の d行e列（および対称位置の e行d列）は0なので、d-e のエッジは存在してはいけません。行列中の1の個数は12個で、無向グラフではエッジ数はその半分の6本です。先にエッジの本数を数えておけば、7本あるエは本数の不一致だけで除外できます。

解くときのポイント

隣接行列の問題は、まず行列から「エッジの本数」を数え（1の個数÷2）、次に各エッジを列挙して選択肢と照合する。本数が合わない選択肢を先に消すと速い。