平成26年度 春期 応用情報技術者試験 午前 問2
テクノロジ／基礎理論三つのグラフA〜Cの同形関係に関する記述のうち，適切なものはどれか。ここで，二つのグラフが同形であるとは，一方のグラフの頂点を他方のグラフの頂点と1対1に漏れなく対応付けることができ，一方のグラフにおいて辺でつながれている頂点同士は他方のグラフにおいても辺でつながれていて，一方のグラフにおいて辺でつながれていない頂点同士は他方のグラフにおいても辺でつながれていないことをいう。
出典：平成26年度 春期 応用情報技術者試験 午前 問2
- アAはCと同形であるが，Bとは同形でない。
- イBはCと同形であるが，Aとは同形でない。
- ウどの二つのグラフも同形である。
- エどの二つのグラフも同形でない。
正解：ア
解説
グラフAは六角形の辺に加えて対頂点を結ぶ3本の対角線（a0-a3，a1-a4，a2-a5）をもち，頂点を(a0,a2,a4)と(a1,a3,a5)の2組に分けるとどの辺も異なる組の頂点間にしかない完全二部グラフK3,3である。グラフCも2列に並んだ頂点(c1,c0,c5)と(c2,c3,c4)の間の全ての組合せを結ぶ完全二部グラフK3,3であり，AとCは頂点を対応付けると同形になる。一方グラフBは，b1-b2-b3-b4-b5-b1という奇数長（5）の閉路をもつため二部グラフにならず，AやCとは同形になり得ない。
選択肢ごとの解説
- ア正しい。AとCはいずれも頂点を2組に分けた完全二部グラフK3,3であり同形だが，Bは奇数長の閉路をもつため二部グラフでなく，AともCとも同形にならない。
- イ誤り。BはAとは異なる構造（奇数長の閉路を含む）をもち，Cと同形になるのはAの方である。
- ウ誤り。Bは奇数長の閉路をもつため二部グラフのAやCとは同形になり得ず，三つ全てが同形ではない。
- エ誤り。AとCはどちらも完全二部グラフK3,3であり，頂点を適切に対応付けると同形になる。