ノードとノードの間のエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列に対応させて、ノード間にエッジが存在する場合は1で、エッジが存在しない場合は0で示す。

選択肢

• アノードをa,b,[すき間]c,d,e,fの順に並べ、直線でa-b、c-d、d-e、e-fを結び、さらに弧（アーチ）でc-e（dの上を通る）とb-d（cの下を通る）を結んだグラフ
• イノードをa,b,c,[すき間]d,e,fの順に並べ、直線でa-b、b-c、d-e、e-fを結び、さらに弧でc-e（dの上を通る）とb-d（cの下を通る）を結んだグラフ
• ウノードをa,b,c,d,[すき間]e,fの順に並べ、直線でa-b、b-c、c-d、e-fを結び、さらに弧でc-e（dの上を通る）とb-d（cの下を通る）を結んだグラフ
• エノードをa,b,c,d,e,fの順にすき間なく並べ、直線でa-b、b-c、c-d、d-e、e-fを結び、さらに弧でc-e（dの上を通る）とb-d（cの下を通る）を結んだグラフ

正解と解説

正解：ウ ノードをa,b,c,d,[すき間]e,fの順に並べ、直線でa-b、b-c、c-d、e-fを結び、さらに弧でc-e（dの上を通る）とb-d（cの下を通る）を結んだグラフ

無向グラフの隣接行列は対称行列になり、値が1のマス（行,列）の組がそのまま辺を表す。この行列で1が立っているのは a-b、b-c、b-d、c-d、c-e、e-f の6組であり、辺の数は6本、各頂点の次数は a=1、b=3、c=3、d=2、e=2、f=1 となる。この6本の辺をすべて過不足なく備えた図が正解であり、次数の分布（次数1の頂点が a と f の2つだけ）を数えるだけでも絞り込める。

選択肢ごとの解説

• アb-e という行列にない辺を含み、b-c が欠けている。
• イb-d と c-e はあるが c-d が無く、辺の組合せが行列と一致しない。
• ウ正解。a-b、b-c、c-d、b-d、c-e、e-f の6本を過不足なく表している。
• エb-e という存在しない辺を含んでおり、行列と対応しない。

同じ分野の他の問題

• 入力されたビットに対して出力されるビットが0か1のいずれかである確率を遷移確率という。遷移確率を表にしたとき，a，b，c…2026年度 公開問題 科目A 問1
• 液晶ディスプレイなどの表示装置において、傾いた直線の境界を滑らかに表示する手法はどれか。2024年度 公開問題 科目A 問6
• 3次元グラフィックス処理におけるクリッピングの説明はどれか。2023年度 公開問題 科目A 問5
• 入力記号、出力記号の集合が{0, 1}であり、状態遷移図で示されるオートマトンがある。0011001110を入力記号とし…2022年度 公開問題 科目A 問4
• 次のBNFで定義される＜変数名＞に合致するものはどれか。 ＜数字＞::=0｜1｜2｜3｜4｜5｜6｜7｜8｜9 ＜英字＞…2019年度 秋期 午前 問7