ウカマル応用情報技術者ログイン

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

テクノロジ系

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

図

図の内容(文字)
A:頂点a0〜a5を六角形状に配置(左a0,左上a1,右上a2,右a3,右下a4,左下a5)。辺:a0−a1,a1−a2,a2−a3,a3−a4,a4−a5,a5−a0,a0−a3,a1−a4,a2−a5。 B:頂点b0〜b5を六角形状に配置(左b0,左上b1,右上b2,右b3,右下b4,左下b5)。辺:b0−b1,b1−b2,b2−b3,b3−b4,b4−b5,b5−b0,b0−b3,b1−b5,b2−b4。 C:頂点c0〜c5を配置(左c0,左上c1,右上c2,右c3,右下c4,左下c5)。辺:c1−c2,c1−c3,c1−c4,c0−c2,c0−c3,c0−c4,c5−c2,c5−c3,c5−c4。
選択肢
正解と解説

正解 ア

AとCはどちらも、3頂点ずつの2組の間だけに辺がある完全二部グラフです。Bには三角形(b0−b1−b5)があるので、AともCとも同形になりません。

3つのグラフは、どれも頂点が6個、辺が9本で、各頂点の次数は3です。このため、辺の数や次数だけでは区別できません。Aは{a0,a2,a4}と{a1,a3,a5}に分けると、9本の辺がすべて2組の間を結びます。Cも{c0,c1,c5}と{c2,c3,c4}に分けると同じ形になります。したがって、AとCはどちらも完全二部グラフK3,3で、同形です。Bでは辺b0−b1、b1−b5、b5−b0が三角形を作ります。二部グラフには長さ3の閉路がないので、BはAともCとも同形ではありません。

イ:Bには三角形b0−b1−b5がありますが、Cには三角形がありません。このため、BとCは同形ではありません。

ウ:頂点の数、辺の数、次数がすべて同じでも、同形とは限りません。Bだけに三角形があるので、Bは他の2つと同形ではありません。

エ:AとCは、頂点を2組に分けると同じ完全二部グラフK3,3になります。このため、AとCは同形です。

出典:平成26年度 春期 応用情報技術者試験 問2

全年度から出題。10問で実力を判定します。登録不要。

出典:平成26年度 春期 応用情報技術者試験 問2(独立行政法人情報処理推進機構)

解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方