基本情報技術者試験「グラフ」の問題
5 個のノード 1〜5 から成る無向グラフを隣接行列 M で表す（M[i][j]=1 で辺あり、添字は 1 から、自己ループなし。無向なので M は対称）。
M[1] = {0,1,1,0,0}
M[2] = {1,0,1,1,0}
M[3] = {1,1,0,0,1}
M[4] = {0,1,0,0,1}
M[5] = {0,0,1,1,0}
次の手続 edgeCount は、このグラフの辺の総数を返す。上三角部分（i < j）だけを走査して 1 を数える。edgeCount(M) を実行したとき、戻り値はどれか。
○整数型: edgeCount(整数型の二次元配列: M)
整数型: e ← 0
整数型: i, j
for (i を 1 から 5 まで 1 ずつ増やす)
for (j を i + 1 から 5 まで 1 ずつ増やす)
if (M[i][j] が 1 と等しい)
e ← e + 1
endif
endfor
endfor
return eア5 本
イ12 本（÷2 忘れ）
ウ辺は 6 本
エ3 本だけ
正解
ウ．辺は 6 本
無向グラフの辺数は対称行列の上三角部分の 1 の個数に等しい。上三角で 1 となるのは (1,2)(1,3)(2,3)(2,4)(3,5)(4,5) の 6 か所であり、e=6 となるため ウが正しい。
?選択肢ごとの解説
ア ×ノード数 5 を辺数と混同した、ノードと辺を取り違えた誤りである。
イ ×上三角に限定せず行列全体の 1 を数えた 12（各辺を 2 回計上）であり、÷2 を忘れた誤りである。
ウ ○無向グラフの辺数は対称行列の上三角部分の 1 の個数に等しい。上三角で 1 となるのは (1,2)(1,3)(2,3)(2,4)(3,5)(4,5) の 6 か所であり、e=6 となるため ウが正しい。
エ ×一部の辺だけを数えて 3 本とした、内側ループの開始 j=i+1 を取り違えた過少カウントである。
✎くわしく
無向グラフでは辺 (i,j) が M[i][j] と M[j][i] の 2 か所に現れる。上三角（i<j）だけを数えるか、全体を数えて 2 で割るかで、二重計上を避けるのが要点である。
✓本番での押さえどころ
試験のコツ
無向の辺数は『上三角の 1 の数』または『全体の 1 ÷ 2』と覚え、対角線(0)は無視する。
覚え方
『無向は往復で 2 回、だから半分』と覚える。
よくある誤り
行列全体の 1 を数えて 2 で割り忘れ、辺数を 2 倍にしてしまうミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0151