平成26年度春期 応用情報技術者試験 午前 問2
三つのグラフA〜Cの同形関係に関する記述のうち，適切なものはどれか。ここで，二つのグラフが同形であるとは，一方のグラフの頂点を他方のグラフの頂点と1対1に漏れなく対応付けることができ，一方のグラフにおいて辺でつながれている頂点同士は他方のグラフにおいても辺でつながれていて，一方のグラフにおいて辺でつながれていない頂点同士は他方のグラフにおいても辺でつながれていないことをいう。
- ア AはCと同形であるが，Bとは同形でない。
- イ BはCと同形であるが，Aとは同形でない。
- ウ どの二つのグラフも同形である。
- エ どの二つのグラフも同形でない。
解答・解説を見る
正解：ア
AI解説
グラフの同形とは,頂点を1対1に対応付けたとき辺のつながり方(隣接関係)が完全に一致することをいう。判定では,まず頂点数・辺数・各頂点の次数(接続する辺の数)の分布を比べ,一致すれば実際に対応付けを構成して確認する。本問ではAとCは頂点の対応付けが構成でき同形だが,Bは隣接関係(例えば同じ次数の頂点同士のつながり方や閉路の構造)が異なり,どう対応付けても一致しないため同形でない。 ア: 正解。AとCは頂点の1対1対応で辺の有無がすべて一致するので同形,BはAやCと隣接構造が異なるため同形でない。 イ: BはCと同形ではない。Cと同形なのはAである。 ウ: Bだけは他の2つと辺のつながり方が異なるため,3つすべてが同形という記述は誤りである。 エ: AとCは同形であるため,どの2つも同形でないという記述は誤りである。 💡 同形判定は「頂点数・辺数・次数列の一致」が必要条件(不一致なら即,非同形)だが十分条件ではない点に注意。次数列が同じでも,次数の高い頂点同士が隣接しているかなど局所構造まで確認する。
出典：平成26年度 春期 応用情報技術者試験 午前 問2 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。