最終更新日：2026年8月5日
fe technology basic-theory graph
まず結論
隣接行列とは、頂点どうしを結ぶ辺があるかどうかを、0と1で表した行列です。
第i行・第j列の値は、次のように読みます。
1 → 頂点ViとVjを結ぶ辺がある
0 → 頂点ViとVjを結ぶ辺がない
基本情報技術者試験では、次の手順で読むと安定します。
1の位置を確認する
↓
頂点の組として書き出す
↓
図の接続関係と照合する
一番大切なのは、図の形ではなく、どの頂点同士が直接つながっているかを見ることです。
直感的な説明
隣接行列は、グラフの「接続チェック表」です。
例えば、4つの頂点があるとします。
V1、V2、V3、V4
V1とV2がつながっているなら、行列のV1行・V2列を1にします。
A12 = 1
つながっていなければ0です。
A12 = 0
無向グラフでは、V1とV2がつながることと、V2とV1がつながることは同じです。
A12 = A21
そのため、行列は主対角線をはさんで左右対称になります。
定義・仕組み
頂点がn個あるグラフでは、隣接行列はn行n列になります。
| 項目 | 意味 |
|---|---|
| 行 | 出発側または確認元の頂点 |
| 列 | 到着側または確認先の頂点 |
| 1 | 辺がある |
| 0 | 辺がない |
例えば、次の行列を考えます。
V1 V2 V3 V4
V1 0 1 1 0
V2 1 0 0 1
V3 1 0 0 1
V4 0 1 1 0
この行列から、次の辺が読み取れます。
V1―V2
V1―V3
V2―V4
V3―V4
上三角部分だけを見る
無向グラフでは、同じ辺が行列内に2回現れます。
A12 = 1
A21 = 1
これは2本の辺ではなく、V1とV2を結ぶ1本の辺です。
重複を避けるには、主対角線より上側だけを見ると分かりやすいです。
V1-V2
V1-V3
V1-V4
V2-V3
V2-V4
V3-V4
この6か所だけを確認すれば、4頂点の無向グラフを読み取れます。
対角成分
主対角線は、同じ頂点どうしの接続を表します。
A11、A22、A33、A44
対角成分が1なら、その頂点には自己ループがあります。
対角成分が1 → 自己ループあり
対角成分が0 → 自己ループなし
このテーマは、基本情報技術者試験の「基礎理論」に関係します。公式の出題範囲やシラバスは、IPA：基本情報技術者試験から確認できます。
科目Aでどう出る？
科目Aでは、隣接行列から対応するグラフを選ぶ問題や、辺の本数を求める問題が出ます。
行列から図を選ぶ問題
次の順番で読みます。
1. 行列が対称か確認する
2. 上三角部分だけを見る
3. 1の位置を頂点の組として書く
4. 選択肢の図と照合する
例えば、次のように短くメモします。
12
13
24
34
これは次の意味です。
12 → V1―V2
13 → V1―V3
24 → V2―V4
34 → V3―V4
辺の本数を求める問題
無向グラフでは、行列全体の1の個数を2で割ります。
辺の本数
=
行列全体の1の個数 ÷ 2
ただし、自己ループがある場合は扱いが変わるため、対角成分を別に確認します。
自己ループがなければ、上三角部分にある1の個数を数える方法が安全です。
図の形ではなく接続を見る
同じ接続関係でも、頂点の配置を変えると見た目は大きく変わります。
線が斜め
線が縦
頂点の位置が違う
これらは判断材料ではありません。
見るべきなのは、次の一点です。
どの頂点とどの頂点が直接つながっているか。
どんな場面で使う？
隣接行列は、頂点間の接続関係を表す場面で使います。
代表例は次のとおりです。
- コンピュータネットワークの接続関係
- 駅や道路の接続関係
- 人間関係やSNSのつながり
- Webページ間のリンク
- 部品や工程の依存関係
- 配送経路や経路探索
接続の有無を行列で表せるため、コンピュータで処理しやすいのが特徴です。
有向グラフとの違い
辺に向きがある有向グラフでは、行列は必ずしも対称になりません。
V1 → V2 がある
V2 → V1 はない
この場合、
A12 = 1
A21 = 0
となります。
無向グラフか有向グラフかで、行列の読み方が変わる点に注意します。
隣接リストとの違い
隣接リストは、各頂点について、直接つながっている頂点だけを列挙する方法です。
V1：V2、V3
V2：V1、V4
V3：V1、V4
V4：V2、V3
| 表現 | 特徴 |
|---|---|
| 隣接行列 | 接続の有無をすぐ確認しやすい |
| 隣接リスト | 辺が少ないグラフで記憶効率がよい |
FE試験では、まず両者の表現方法の違いを理解しておけば十分です。
よくある誤解・混同
1を頂点番号として読む
行列中の1は頂点番号ではありません。
1 → 辺がある
0 → 辺がない
という意味です。
A12とA21を別の辺として数える
無向グラフでは、A12とA21は同じ1本の辺を表します。
A12 = 1
A21 = 1
→ V1―V2という1本の辺
図の形が似ているものを選ぶ
頂点の位置や線の角度は重要ではありません。
図の形
≠
接続関係
頂点番号どうしの接続だけを確認します。
対称なら必ず完全グラフである
対称であることは、無向グラフであることを表すだけです。
すべての頂点同士がつながっているとは限りません。
完全グラフでは、対角成分以外がすべて1になります。
対角成分を無視する
対角成分は自己ループの有無を表します。
問題によっては、対角成分が辺の本数に関係します。
確認問題（基本情報技術者試験対策）
次の無向グラフの隣接行列で、1になっている組が 12、13、24、34 である。存在する辺の組合せとして正しいものはどれか。
- ア. V1―V4、V2―V3
- イ. V1―V2、V1―V3、V2―V4、V3―V4
- ウ. V1―V2、V1―V4、V2―V3、V3―V4
- エ. V1―V3、V1―V4、V2―V3、V2―V4
▶ クリックして答えと解説を見る（ここを開く）
正解：イ
12、13、24、34 は、それぞれ次の辺を表します。
12 → V1―V2
13 → V1―V3
24 → V2―V4
34 → V3―V4
したがって、正しい組合せはイです。
まとめ（試験直前用）
- 隣接行列は、頂点どうしを結ぶ辺の有無を0と1で表す
- 第i行・第j列が1なら、ViとVjを結ぶ辺がある
- 無向グラフでは行列が対称になる
- 無向グラフは上三角部分だけを見ると重複を避けられる
- 対角成分が1なら自己ループがある
- 図の形ではなく、頂点番号どうしの接続を見る
- 有向グラフでは行列が対称とは限らない
- 辺の本数は、自己ループがなければ上三角部分の1を数える