隣接行列から無向グラフの辺をどう見分けるか
基本情報技術者試験 令和元年度秋期 午前 問3 ／ 基礎理論 › 応用数学
過去問にチャレンジ
ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は 1 で，エッジが存在しない場合は 0 で示す。
- ア
- イ
- ウ
- エ
会話形式の解説
講師行列の1が示すノードの組を拾い、図にある辺と照らし合わせます。
受験者a行b列とb行a列がどちらも1です。これは2本の辺として数えますか。
講師無向グラフでは同じ1本です。行と列を入れ替えた位置は重複するので、片方だけ拾うとどうなりますか。
受験者aとb、bとc、bとd、cとd、cとe、eとfの6本です。
講師その6本がそろっているか見ます。まず、bとcがつながっていない図はどうでしょう。
受験者アの図はbとcの辺がないので違います。しかも、行列で0のdとeがつながっています。
講師そうです。イの図では、必要な辺のうち何が欠けていますか。
受験者cとdの辺がありません。イにも、行列では0のdとeの辺があります。
講師エの図はどうですか。
受験者必要な辺はありますが、dとeも直接つながっています。d行e列は0なので選べません。
講師では、残る図の辺を行列と照合しましょう。
受験者ウの図には挙げた6本がすべてあり、余分な辺もありません。正解はウです。
講師図を選ぶときは、1が示す辺の欠落だけでなく、0なのに描かれた余分な辺も確認します。
まとめ
隣接行列の1は、行と列に対応するノード間の辺を示します。無向グラフでは、行と列を入れ替えた位置の1は同じ辺として数えます。この行列が示す6本の辺を過不足なく持つ図はウです。
解答・解説
正解はウです
この問題のテーマ
無向グラフの隣接行列から辺を読み取り、対応する図を選ぶ問題です。
解き方の考え方
行と列がともに示すノードを確認し、値が1の組を辺として拾います。無向グラフでは、例えばa行b列とb行a列は同じ1本の辺を表すので、重複して数えません。得られた辺を各図と照合します。
選択肢ごとの解説
- ×アアの図では、行列で1になっているbとcがつながっていません。また、d行e列は0ですが、図にはdとeを結ぶ辺があります。
- ×イイの図には、行列が示すcとdの辺がありません。さらに、行列で0になっているdとeが図ではつながっています。
- ○ウウの図にはa–b、b–c、b–d、c–d、c–e、e–fの6本の辺があります。行列の1が示す組とすべて一致するため、これが正解です。
- ×エエの図にはdとeを直接結ぶ辺があります。しかし、行列のd行e列は0なので、この辺がある図は選べません。
POINT
- 行列の1は、その行と列に対応するノード間に辺があることを示します。
- 無向グラフでは、行と列を入れ替えた位置の1を同じ辺として扱います。
- 図との照合では、必要な辺の欠落と、余分な辺の両方を確かめます。