平成26年度 春期 午前 問2
基礎理論
グラフ理論に関する問題
三つのグラフ A 〜 C の同形関係に関する記述のうち，適切なものはどれか。ここで，二つのグラフが同形であるとは，一方のグラフの頂点を他方のグラフの頂点と 1 対 1 に漏れなく対応付けることができ，一方のグラフにおいて辺でつながれている頂点同士は他方のグラフにおいても辺でつながれていて，一方のグラフにおいて辺でつながれていない頂点同士は他方のグラフにおいても辺でつながれていないことをいう。
〔三つのグラフ〕
A … 六角形に頂点を置く（左から時計回りに a0・a1・a2・a3・a4・a5）
外周 6 本 … a0-a1 ／ a1-a2 ／ a2-a3 ／ a3-a4 ／ a4-a5 ／ a5-a0
中を通る対角線 3 本 … a0-a3 ／ a1-a4 ／ a2-a5（3 本とも中心で交わる）
⇒ 辺は 9 本・どの頂点も次数 3
B … 同じ六角形の置き方（b0・b1・b2・b3・b4・b5）
外周 6 本 … b0-b1 ／ b1-b2 ／ b2-b3 ／ b3-b4 ／ b4-b5 ／ b5-b0
中の弦 3 本 … b1-b5（左の縦線）／ b2-b4（右の縦線）／ b0-b3（横線）
⇒ 辺は 9 本・どの頂点も次数 3
C … 上段 c1・c2 ／ 中段 c0（左）・c3（右）／ 下段 c5・c4 に置く
c0 から … c2 ／ c3 ／ c4
c1 から … c2 ／ c3 ／ c4
c5 から … c2 ／ c3 ／ c4
⇒ 辺は 9 本・どの頂点も次数 3- アA は C と同形であるが，B とは同形でない。
- イB は C と同形であるが，A とは同形でない。
- ウどの二つのグラフも同形である。
- エどの二つのグラフも同形でない。
答えと解説を見る
✓ これが正解アA は C と同形であるが，B とは同形でない。
解説
頂点と辺の数が同じでも、三角形の数で分かれます。
設問は、三つのグラフがグラフ理論でいう同形の関係にあるかどうかを選ばせています。三つとも頂点が 6 個、辺が 9 本、どの頂点からも辺が 3 本出ているので、数え上げだけでは分かれません。数が一致することは同形であるための必要条件にすぎないからです。次に見るのが、長さ 3 の閉路、つまり三角形がいくつあるかです。同形なら三角形の数は必ず一致しますから、違えばその場で同形でないと言い切れます。B には b0 と b1 と b5 で作る三角形と、b2 と b3 と b4 で作る三角形があります。A と C ではどの頂点を選んでも、その隣どうしが辺で結ばれていないので、三角形は一つもありません。ここで B が外れます。残る A と C は、どちらも三つずつの組を二つ作って、その間を全部結んだ形です。a0 を c0 に、a2 を c1 に、a4 を c5 に、a1 を c2 に、a3 を c3 に、a5 を c4 に対応させると、辺が一つ残らず対応します。
ほかの選択肢はなぜ違うのか
- イB は C と同形であるが，A とは同形…：長さ 3 の閉路を持つのは B だけです。C の側にはその閉路が作れないので、この二つを同じ形だと結び付けることはできません。
- ウどの二つのグラフも同形である。：頂点 6・辺 9・次数 3 という数え上げで止まると、この判断になります。数が一致することは同じ形であることの証拠にはなりません。
- エどの二つのグラフも同形でない。：六角形と三段の配置という、描き方の違いに引きずられた形です。どこがどこにつながっているかが同じなら、絵が違っても同じ形です。
出典：平成26年度 春期 応用情報技術者試験 午前 問2
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）