平成29年度 春期 午前 問3
基礎理論
隣接行列に関する問題
ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は 1 で，エッジが存在しない場合は 0 で示す。
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 0 | 1 | 0 | 0 | 0 | 0 |
| b | 1 | 0 | 1 | 1 | 0 | 0 |
| c | 0 | 1 | 0 | 1 | 1 | 0 |
| d | 0 | 1 | 1 | 0 | 0 | 0 |
| e | 0 | 0 | 1 | 0 | 0 | 1 |
| f | 0 | 0 | 0 | 0 | 1 | 0 |
選択肢ア〜エは原典ではグラフの図。図から読み取ったエッジの集合を書き写した（図そのものは復元していない）。どの選択肢も a〜f の 6 個のノードを横一列に並べた形で，違いは直線の有無と追加の曲線だけ。
- ア直線 a−b，c−d，d−e，e−f に加えて，曲線 c−e と b−d（b−c が結ばれていない）
- イ直線 a−b，b−c，d−e，e−f に加えて，曲線 c−e と b−d（c−d が結ばれていない）
- ウ直線 a−b，b−c，c−d，e−f に加えて，曲線 c−e と b−d（d−e が結ばれていない）
- エ直線 a−b，b−c，c−d，d−e，e−f に加えて，曲線 c−e と b−d
答えと解説を見る
✓ これが正解ウ直線 a−b，b−c，c−d，e−f に加えて，曲線 c−e と b−d（d−e が結ばれていない）
解説
行列の 1 から 6 本の辺を書き出して照合します。
設問は、ある無向グラフの隣接行列を示し、同じ関係を表す図を選ばせています。読み方は単純で、行と列の交わるところにある 1 が、エッジ 1 本を表します。無向グラフなので行列は対称になり、右上の三角だけを見れば足ります。上から順に拾うと、a と b、b と c、b と d、c と d、c と e、e と f の 6 本が得られます。対角の成分はすべて 0 なので、自分自身へ戻る線はありません。各ノードから出ている本数を数えると、a が 1、b が 3、c が 3、d が 2、e が 2、f が 1 で、合計 12 は 6 本の 2 倍にあたり、拾い忘れがないことを確かめられます。この 6 本とちょうど一致する図が当てはまります。グラフ理論の問題は、図を描き直すより行列の 1 を列挙するほうが速く決まります。
ほかの選択肢はなぜ違うのか
- ア直線 a−b，c−d，d−e，e−f に…：b と c をつなぐ線が抜けており、代わりに d と e がつながれています。行列では b の行の c の位置に 1 が立ち、d の行の e の位置は 0 なので、2 か所が食い違います。
- イ直線 a−b，b−c，d−e，e−f に…：c と d をつなぐ線が抜けている代わりに、d と e がつながれています。本数こそ合っていますが、1 が立っている場所と立っていない場所が入れ替わっています。
- エ直線 a−b，b−c，c−d，d−e，e…：線を 7 本引いており、1 本多くなっています。d と e の間に余分な線があり、行列のその位置が 0 であることと合いません。本数を数えるだけで外せます。
出典：平成29年度 春期 応用情報技術者試験 午前 問3
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）