応用情報技術者 2014年 春期 午前2 問02

グラフ同形判定【午前2解説】

正解の理由

解法ステップ

1. 各図について頂点数と各頂点の次数（次数分布）を数える。
   • 図A: 中心1頂点＋周辺6頂点＝7頂点。中心の次数6、周辺各頂点の次数3（2辺の輪＋中心の辺） → 次数多重集合 {6,3,3,3,3,3,3}。
   • 図B: 6頂点。各頂点が隣接する2辺（輪）に加え対角線の1本があるため各頂点次数3 → {3,3,3,3,3,3}。
   • 図C: K3,3。左右合わせて6頂点、各頂点次数3 → {3,3,3,3,3,3}。
2. 頂点数が一致しない場合は同形にならない（A と B/C は即 NG）。
3. 頂点数・次数分布が一致しても、グラフ不変量（例えば奇長サイクルの有無、二部性、連結成分構造など）を比較する。
   • 図Bには3辺のサイクル（三角形）が存在する（例: b0–b1–b5–b0）。
   • 図C（K3,3）は二部グラフであり奇長サイクルを含まない。
     よって B と C も同形でない。
4. 以上より、どの二つのグラフも同形でない（選択肢エが正しい）。

選択肢別の誤答解説

• ア: 「AはCと同形であるが、Bとは同形でない。」
  誤り。A は頂点数7、C は頂点数6であり頂点数が異なるため同形になり得ません（次数分布も不一致）。したがって<AがCと同形>という主張は不当です。
• イ: 「BはCと同形であるが、Aとは同形でない。」
  頂点数・次数分布は B と C で一致しますが、B は三角形などの奇長サイクルを含む一方で C（K3,3）は二部グラフのため奇長サイクルを持ちません。奇長サイクルの有無は同形の不変量なので同形ではありません。よってイも誤りです。
• ウ: 「どの二つのグラフも同形である。」
  明確に誤り。頂点数や次数分布が異なる組（A と B/C）や、奇長サイクルの有無が異なる組（B と C）があるため成立しません。
• エ: 「どの二つのグラフも同形でない。」
  正しい。上記の理由（頂点数・次数分布・奇長サイクルの有無）により、どの組も同形ではありません。

よくある誤解

• 頂点数を見落とす: 図の中心頂点を「装飾」と勘違いして数え忘れると、A と C が同形だと誤判断しやすいです。必ず頂点数を最初に確認してください。
• 次数分布だけで同形と決める: 次数分布は必要条件ですが十分条件ではありません（B と C は次数分布が同じでも同形でない）。奇長サイクルや二部性など他の不変量も確認してください。

補足コラム

• 同形判定で有用な不変量（同形なら必ず一致するもの）
  • 頂点数、辺数、次数分布（次数の多重集合）
  • 連結成分の個数・大きさ
  • 二部グラフ性（グラフが二部か否か）
  • 含まれる最短奇長サイクルの長さ（存在および長さ）
    これらを組み合わせれば多くの簡単な同形判定は速やかに行えます。次数分布が一致しても、例えば「三角形（3-cycle）が存在するか否か」で否定できるケースがよくあります（本問のBとCがその例）。

FAQ