問題プレビューID: 243c1926応用情報技術者試験 2014年(平成26年度)春期 午前

問 2
応用情報技術者試験 2014年(平成26年度)春期 午前

三つのグラフ A~C の同形関係に関する記述のうち,適切なものはどれか。ここで,二つのグラフが同形であるとは,一方のグラフの頂点を他方のグラフの頂点と 1 対 1 に漏れなく対応付けることができ,一方のグラフにおいて辺でつながれている頂点同士は他方のグラフにおいても辺でつながれていて,一方のグラフにおいて辺でつながれていない頂点同士は他方のグラフにおいても辺でつながれていないことをいう。

グラフ A

グラフ B

グラフ C

解説

正解は「ア」です。

2 つのグラフが同形とは,頂点を 1 対 1 に対応付けたとき,辺のつながり方(隣接関係)が完全に一致することをいいます。

  • A と C: どちらも 6 個の頂点を 3 個ずつの 2 つのグループに分けたとき,異なるグループの頂点同士がすべて辺で結ばれた形(完全 2 部グラフ K₃,₃)になっています。A では {a0, a2, a4} と {a1, a3, a5},C では {c0, c1, c5} と {c2, c3, c4} に分けることができ,頂点を対応付けると辺の関係が一致するので同形です。
  • B: 2 つの三角形 {b0, b1, b5} と {b2, b3, b4} を対応する頂点どうしで結んだ三角柱の形であり,三角形を含まない A,C とは辺の構成が異なるため同形ではありません。

したがって,「A は C と同形であるが,B とは同形でない」の ア が正解です。

関連問題

本文が同じ・似ている問題を表示しています