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

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

正解の理由

解法ステップ

1. 各図の基本データ（頂点数・辺数）を数える。
   • 図A：頂点 7、辺 12（外周6辺＋中心からの放射6辺）。
   • 図B：頂点 6、辺 9（六角形6辺＋斜め3本）。
   • 図C：頂点 7、辺 12（図CはAと同等の接続形を持つ構成として与えられているため、頂点・辺がAと一致する）。
     （問題文図の読み替えにより図Cは図Aと同構造を表しているため、AとCは頂点・辺が一致します。）
2. 次に各頂点の次数（その頂点に接する辺の本数）の多重集合を比較する。
   • 図A：中心頂点の次数6、周辺6頂点の各次数3 → 多重集合 {6, 3,3,3,3,3,3}。
   • 図C：同様に中心1頂点が6、本体の6頂点がそれぞれ3 → 同じ多重集合。
   • 図B：全頂点の次数が3で揃う → 多重集合 {3,3,3,3,3,3}（中心的な次数6を持つ頂点がない）。
3. AとCの多重集合が一致するので、詳しく1対1対応を構成して隣接関係が保たれることを確認する（外周の順序を保った対応＋中心を中心に対応させる）。これにより同形であることが確定する。
4. Bは次数分布や頂点数がA・Cと一致せず、さらに三角形（長さ3の閉路）などの局所構造が異なるため、同形ではない。

選択肢別の誤答解説

• ア（正答）: 上述の通り。AとCは頂点・辺・次数分布が一致し、明確な1対1対応で隣接関係を保てるため同形。Bとは次数分布・局所構造（奇数閉路の有無）で異なる。
• イ: 「BはCと同形であるがAとは同形でない」とする選択。BとCはともに各頂点次数が3で辺数9のグラフに見えるが、グラフ同形は次数だけで決まらない。二部グラフであるCは奇数長閉路（例えば三角形）を含まないが、Bは実際に三角形を含むため二部性がない。よってBとCは同形ではない。
• ウ: 「どの二つも同形である」は誤り。A・Cは同形でも、Bは局所構造（閉路の長さや二部性）が異なるため含まれない。
• エ: 「どの二つのグラフも同形でない」も誤り。AとCは上で述べた通り同形であるため、この選択は不適切。

よくある誤解

• 「次数分布が一致すれば同形」と考える誤り：次数の多重集合が一致することは必要条件だが十分条件ではありません。具体的な隣接関係（どの頂点がどの頂点とつながるか）まで保存できる対応が取れるかを確認する必要があります。
• 「描かれた見た目（位置や左右対称）だけで同形を判断する」誤り：描画のレイアウトは任意で、グラフの本質は隣接関係だけです。位置にとらわれず次数や閉路構造、二部性などの不変量で判定します。

補足コラム

• 有力な不変量（isomorphismの判別に使える性質）：頂点数・辺数・次数列（多重集合）、連結成分の個数、閉路（サイクル）長の存在、二部性（bipartiteness）、次数ごとの隣接関係（例：次数kの頂点が何個の次数ℓの頂点と隣接するか）など。複雑なグラフ同形判定ではこれらを組み合わせて絞り込み、最後に具体的な1対1対応を構成して確認します。
• 実務的には次数列と二部性・三角形の有無で多くの誤答候補を排除できるため、試験時間内でも有効な手法です。

FAQ