問 題
グラフ G の頂点集合を二つの素な部分集合 A と B に分割でき G の全ての辺は A の頂点と B の頂点を結んでおり、かつ、同じ部分集合に含まれる頂点どうしの間には辺が存在しないとき G は２部グラフと呼ばれる。さらに A の各頂点が B の全ての頂点と辺で結ばれているとき G は完全２部グラフと呼ばれる。次の㋐～㋓のグラフのうち完全２部グラフとして妥当なもののみを全て挙げているのはどれか。ただしグラフ中の黒丸は頂点を表している。
1. ㋐
2. ㋐ ㋒
3. ㋐ ㋓
4. ㋑ ㋓
5. ㋒ ㋓
正解 (2)
解 説
㋐について
左上から頂点に時計回り(⤵)に、１，２，３，４と番号を付けます。そして１，３の頂点と、２，４の頂点 という部分集合にわけると２部グラフです。さらに、頂点１は２，４と、頂点３は２，４と結ばれているため、㋐は完全２部グラフです。
㋒ ですが
上３つの頂点と下２つの頂点という部分集合にわけて、上３つをAと考えれば、各頂点はBの全ての頂点と辺で結ばれています。よって、㋒も完全２部です。
以上より、正解は 2 です。
コメント