グラフ理論
「グラフ」と聞くと、棒グラフや折れ線グラフを思い浮かべるかもしれません。しかし、情報科学で扱うグラフ理論のグラフは、それらとはまったく別のものです。グラフ理論のグラフとは、「もの」と「もののつながり」を図で表したものです。
たとえば、鉄道の路線図を想像してみてください。駅が丸い点で表され、駅と駅が線で結ばれています。このように「点と線の関係」で構造を表す考え方が、グラフ理論の基本です。
頂点（ノード）と辺（エッジ）
Section titled “頂点（ノード）と辺（エッジ）”グラフ理論では、2つの要素でグラフを構成します。
頂点（ちょうてん）は、グラフの中で「もの」を表す点のことです。ノード（node）とも呼ばれます。路線図であれば「駅」、SNSであれば「ユーザー」に相当します。
辺（へん）は、頂点と頂点のつながりを表す線のことです。エッジ（edge）とも呼ばれます。路線図であれば「路線（線路）」、SNSであれば「友人関係」や「フォロー関係」に相当します。
| 用語 | 別名 | 意味 | 路線図での例 | SNSでの例 |
|---|---|---|---|---|
| 頂点 | ノード（node） | ものを表す点 | 駅 | ユーザー |
| 辺 | エッジ（edge） | つながりを表す線 | 路線 | 友人関係・フォロー関係 |
つまり、グラフとは「頂点（ノード）の集まりと、それらを結ぶ辺（エッジ）の集まり」で構成される図のことです。
試験で出るポイント
グラフには大きく分けて2つの種類があります。まずは無向グラフから見ていきましょう。
無向グラフとは、辺に方向がないグラフのことです。つまり、頂点Aと頂点Bが辺で結ばれている場合、「AからBへ」も「BからAへ」も同じように移動できます。
身近な例としては、次のようなものがあります。
- 鉄道の路線図：東京駅と品川駅が路線で結ばれていれば、東京→品川も品川→東京も行き来できます
- SNSの友人関係（LINEの友だちなど）：AさんとBさんが友だちであれば、その関係は双方向です
一方、有向グラフとは、辺に方向があるグラフのことです。辺が矢印で表され、「AからBへ」という一方向の関係を示します。有向グラフの辺は「有向辺」とも呼ばれます。
身近な例としては、次のようなものがあります。
- 一方通行の道路：A交差点からB交差点へは進めるが、逆方向には進めない場合があります
- SNSのフォロー関係（X（旧Twitter）など）：AさんがBさんをフォローしていても、BさんがAさんをフォローしているとは限りません
無向グラフと有向グラフの比較
Section titled “無向グラフと有向グラフの比較”2つのグラフの違いを表にまとめます。
| 特徴 | 無向グラフ | 有向グラフ |
|---|---|---|
| 辺の方向 | なし（双方向） | あり（一方向） |
| 辺の表し方 | 線（─） | 矢印（→） |
| 身近な例 | 鉄道路線図、LINEの友だち関係 | 一方通行の道路、Xのフォロー関係 |
| 関係の性質 | 対称（AとBが対等） | 非対称（AからBとBからAは別） |
試験で出るポイント
グラフ理論の活用場面
Section titled “グラフ理論の活用場面”グラフ理論の考え方は、IT分野のさまざまな場面で活用されています。ITパスポート試験で直接「グラフ理論」として出題される機会は多くありませんが、以下のような場面の基礎知識として役立ちます。
- ネットワーク構成図：コンピュータやルータを頂点、通信回線を辺として表す（無向グラフ）
- Webページのリンク構造：Webページを頂点、ハイパーリンクを有向辺として表す（有向グラフ）
- プロジェクト管理（PERT図）：作業を辺、作業の開始・終了を頂点として表し、スケジュールを管理する
このように、グラフ理論は「ものとものの関係」を整理するための基本的なツールです。頂点（ノード）と辺（エッジ）という2つの要素でさまざまな構造を表現できることを理解しておきましょう。
試験で出るポイント