応用情報技術者 2017年 秋期 午前2 問06

グラフの木判定【午前2解説】

正解の理由

解法ステップ

1. 隣接行列が無向グラフの対称行列であることを確認（与題は無向なので問題なし）。
2. 各行の1の個数を足して次数合計 $S$ を求め、エッジ数 $E=S/2$ を計算する。
3. ノード数 $n$ と比較し、$E=n-1$ であるか確認する（木の必要条件）。
4. 連結性を確認する（BFS/DFSで全ノード到達可能か）。$E=n-1$ かつ連結なら木である。
5. 必要なら閉路の有無を直接チェック（DFSでバックエッジの検出など）。

選択肢別の誤答解説

• ア
  • 各ノードの次数はすべて2で、次数合計は10。したがってエッジ数は $10/2=5$ 本です。エッジ数が $n-1=4$ を超えているため閉路が存在し、木ではありません（例：1–2–3–4–5–1 のような巡回が可能）。
• イ
  • 各行の1の個数は [2,3,1,1,1] で次数合計は8、エッジ数は $8/2=4$ 本です。辺は 1–2、1–5、2–3、2–4 で全ノードが繋がっています。よって連結かつエッジ数が $n-1$ を満たすため木です（正解：イ）。
• ウ
  • 各行の1の個数は [2,2,3,2,1] で次数合計は10、エッジ数は $10/2=5$ 本です。エッジ数が4より多いため木ではありません。実際に閉路（例：1–2–3–4–1）が存在します。以前の記述でのエッジ数誤記はなく、正しい値は5本です。
• エ
  • 各行の1の個数は [2,2,4,2,2] で次数合計は12、エッジ数は $12/2=6$ 本です。$E=6$ は $n-1=4$ を大きく上回るため木ではありません。複数の閉路が含まれます（例えば 1–3–2–1 や 3–4–5–3 など）。正しいエッジ数は6本です。

よくある誤解

• 1の総数をそのままエッジ数と勘違いする（必ず合計を2で割ること）。
• エッジ数が $n-1$ なら自動的に木だと考え、連結性を確認しない（孤立成分があると木にならない）。
• 行列の対角要素や自己ループ（問題では0）を無視せず誤カウントする。

補足コラム

• 木の特徴的な性質：ノード数が $n$ の木は「連結かつ閉路がない」「連結かつエッジ数が $n-1$」「閉路がなくエッジ数が $n-1$」のいずれかの性質で判定できます。隣接行列からは次数合計→エッジ数を簡単に求められるので、まずは数値的条件を確認し、次にDFS/BFSで連結性を確かめる流れが最短です。
• 実装例（簡易）：隣接行列から次数合計を計算してエッジ数を求め、DFSで訪問数が$n$か確認する、という手順が典型です。

# adjacency: 2D list of 0/1, n = len(adjacency)
S = sum(sum(row) for row in adjacency)
E = S // 2
# BFS/DFSで連結性を確認

FAQ