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

三つのグラフはどれも頂点が6個，辺が9本で，各頂点の次数は3です。そこで，構造の違いを調べます。

• A: 辺は六角形の外周（a₀-a₁，a₁-a₂，…，a₅-a₀）と対角線（a₀-a₃，a₁-a₄，a₂-a₅）です。頂点を {a₀，a₂，a₄} と {a₁，a₃，a₅} の2組に分けると，すべての辺が2組の間を結んでおり，各頂点が反対側の3頂点すべてとつながっています（完全2部グラフ K₃,₃）。三角形（3頂点の閉路）はありません。
• B: b₀-b₁，b₁-b₅，b₅-b₀ がすべて辺でつながっており，三角形があります。
• C: c₀，c₁，c₅ の組と c₂，c₃，c₄ の組に分けると，各頂点が反対側の3頂点すべてとつながっています（K₃,₃）。

AとCはどちらも K₃,₃ なので同形です。Bは三角形を含むため，三角形をもたないA，Cとは同形になりません。

• ア: AはCと同形であるが，Bとは同形でない。
  正しい。上の分析のとおり，AとCは同形で，Bは三角形を含むのでAとは同形ではありません。

• イ: BはCと同形であるが，Aとは同形でない。
  誤り。BとCは，Bに三角形があってCにはないので同形ではありません。

• ウ: どの二つのグラフも同形である。
  誤り。Bは他の二つと同形ではありません。

• エ: どの二つのグラフも同形でない。
  誤り。AとCは同形です。

答え

ア: AはCと同形であるが，Bとは同形でない。