応用情報技術者 2014年 春期 午前2 問02
問題文
三つのグラフA～Cの同形関係に関する記述のうち、適切なものはどれか。ここで、二つのグラフが同形であるとは、一方のグラフの頂点を他方のグラフの頂点と1対1に漏れなく対応付けることができ、一方のグラフにおいて辺でつながれている頂点同士は他方のグラフにおいても辺でつながれていて、一方のグラフにおいて辺でつながれていない頂点同士は他方のグラフにおいても辺でつながれていないことをいう。
選択肢
ア：AはCと同形であるが、Bとは同形でない。（正解）
イ：BはCと同形であるが、Aとは同形でない。
ウ：どの二つのグラフも同形である。
エ：どの二つのグラフも同形でない。
三つのグラフA～Cの同形関係に関する問題【午前2 解説】
要点まとめ
- 結論：グラフAとグラフCは同形であり、グラフBはどちらとも同形ではありません。
- 根拠：同形グラフは頂点の対応と辺の接続関係が完全に一致し、AとCは頂点数・辺数・接続パターンが一致します。
- 差がつくポイント：完全二部グラフK₃、₃の特徴と、放射状の辺を持つAの構造理解が重要です。Bは辺の数と構造が異なり同形になりません。
正解の理由
アが正解です。
グラフAは中心頂点から6つの周辺頂点へ放射状に辺が伸び、周辺頂点は輪で結ばれています。グラフCは左3頂点と右3頂点の完全二部グラフK₃、₃で、左側と右側の頂点間に全ての辺が存在し、同じく12本の辺を持ちます。これらは頂点の対応付けにより同形と判断できます。
一方、グラフBは辺が9本で、AやCの12本とは異なり、辺の接続関係も異なるため同形ではありません。
グラフAは中心頂点から6つの周辺頂点へ放射状に辺が伸び、周辺頂点は輪で結ばれています。グラフCは左3頂点と右3頂点の完全二部グラフK₃、₃で、左側と右側の頂点間に全ての辺が存在し、同じく12本の辺を持ちます。これらは頂点の対応付けにより同形と判断できます。
一方、グラフBは辺が9本で、AやCの12本とは異なり、辺の接続関係も異なるため同形ではありません。
よくある誤解
グラフの見た目や頂点の配置が異なるだけで同形でないと誤解しやすいです。頂点のラベルや位置は同形判定に影響しません。
また、辺の数や接続関係を正確に把握せずに判断すると誤答につながります。
また、辺の数や接続関係を正確に把握せずに判断すると誤答につながります。
解法ステップ
- 各グラフの頂点数と辺数を数える。
- 同形の定義に基づき、頂点の1対1対応が可能か検討する。
- 辺の接続関係が対応する頂点間で一致するか確認する。
- グラフAとCは頂点数7（A）と6（C）で異なるように見えるが、Aの中心頂点を除く6頂点の接続関係がCの二部グラフの構造に対応。
- グラフBは辺数と接続パターンが異なるため同形ではないと判断。
選択肢別の誤答解説
- イ: BとCが同形とするが、Bは辺数9本、Cは12本で異なるため誤り。
- ウ: どの二つも同形とするが、辺数や接続関係が異なるため誤り。
- エ: どの二つも同形でないとするが、AとCは同形であるため誤り。
補足コラム
同形グラフ（グラフ同型）はグラフ理論の基本概念で、頂点のラベルや描画の違いに関係なく、構造的に同じグラフを指します。
完全二部グラフは、左側の頂点と右側の頂点の間に全ての辺が存在し、同形判定の際に特徴的な構造として利用されます。
完全二部グラフは、左側の頂点と右側の頂点の間に全ての辺が存在し、同形判定の際に特徴的な構造として利用されます。
FAQ
Q: 同形グラフの判定で頂点の位置は重要ですか？
A: 位置は関係なく、頂点間の辺の接続関係が重要です。
A: 位置は関係なく、頂点間の辺の接続関係が重要です。
Q: 辺の数が違うグラフは同形になれますか？
A: 辺の数が異なる場合は同形ではありません。
A: 辺の数が異なる場合は同形ではありません。
Q: 完全二部グラフとは何ですか？
A: 左右の頂点集合間の全ての辺が存在する二部グラフのことです。
A: 左右の頂点集合間の全ての辺が存在する二部グラフのことです。
関連キーワード: グラフ同型、完全二部グラフ、グラフ理論、頂点対応、辺の接続
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！