最終更新日:2026年11月5日
fe fe-technology basic-theory graph
まず結論
グラフ理論(graph theory)は、点(ノード・頂点)と、それらを結ぶ線(エッジ・辺)のつながりを考える分野です。通信ネットワーク、道路、依存関係などの構造を表せます。
| 用語 | 役割 |
|---|---|
| 頂点(vertex)・ノード(node) | 人、機器、地点などを表す点 |
| 辺(edge)・エッジ | 頂点同士を結ぶ関係 |
| 次数(degree) | 無向グラフで、頂点につながる辺の本数 |
| 有向グラフ | 辺に方向があるグラフ |
| 無向グラフ | 辺に方向がないグラフ |
「点が何個あるか」と「つながる辺が何本あるか」は別の数です。
直感的な説明
5台の端末A~Eが次のようにつながっているとします。
A ─── B
│
D ─── E
│
C
この例では、頂点は5個、辺は4本です。
- Aの次数は2(BとDに接続)
- Dの次数は3(A、C、Eに接続)
- B・C・Eの次数はそれぞれ1
Dの次数が3である理由は、Dから3本の辺が伸びているためです。ほかの頂点を「経由して」たどり着ける数ではありません。
定義・仕組み
無向グラフと有向グラフ
無向グラフの辺A―Bは、AとBの間に方向を指定しない関係を表します。一方、有向グラフのA→Bは、AからBへ向かう方向を表します。
| 比較 | 無向グラフ | 有向グラフ |
|---|---|---|
| 辺の書き方 | A―B | A→B |
| 方向 | 指定しない | 指定する |
| 次数 | つながる辺の数 | 入次数・出次数を区別する |
| 例 | 双方向のつながりを単純化した関係 | 一方通行の道路、作業の先行関係 |
有向グラフでは、入次数(in-degree)はその頂点へ入る辺の数、出次数(out-degree)はその頂点から出る辺の数です。
経路・閉路・木
| 用語 | 意味 | 目印 |
|---|---|---|
| 経路(path) | 辺をたどって頂点を結ぶ道筋 | AからEへどう進むか |
| 閉路(cycle) | たどって出発点へ戻る循環したつながり | 一周して元の点 |
| 木(tree) | 連結で閉路のない無向グラフ | 循環なし、つながりが切れない |
5頂点の木なら、辺は必ず4本です。一般に、頂点が (n) 個の木の辺は (n-1) 本になります。
ただし、辺が (n-1) 本という条件だけでは、必ず木とは限りません。連結で閉路がないことも必要です。
次数の合計を使ったチェック
無向グラフでは、1本の辺が両端の2頂点の次数に1ずつ数えられます。したがって
[ \text{次数の合計} = 2\times \text{辺の本数} ]
上の例では次数の合計は (2+1+1+3+1=8) で、辺の本数4の2倍です。
「線形計画法のグラフ」とは別物
線形計画法では、座標平面に制約条件の直線を引き、実行可能領域の頂点を比べて利益最大化などを考えます。
一方、グラフ理論では、ノード同士のつながりを対象とします。
同じ「頂点」「グラフ」という語が登場しても、問題文にある辺・接続・経路・次数が手掛かりならグラフ理論です。
触って覚える:図を見て予想する
次の図を基に、答えを開く前に考えてください。
A ─── B
│
D ─── E
│
C
ケース1:頂点Dの次数はいくつ?
3です。Dに直接接続する辺はDA、DE、DCの3本です。
ケース2:このグラフの辺は何本?
4本です。AB、AD、DC、DEの4本があります。
ケース3:AからEに進むにはどこを経由する?
Dを経由します。A―D―Eという経路です。
ケース4:このグラフには閉路がある?
ありません。 同じ辺を戻ることなく一周できる道筋がないためです。頂点がすべてつながり閉路がないので、この図は木です。
科目Aでどう出る?
問題文の動詞と対象から区別します。
| 問い | 考えること |
|---|---|
| このノードの次数は? | 直接つながる辺の本数を数える |
| 有向グラフの入次数は? | 矢印が向かってくる本数を数える |
| AからEまでの経路は? | 辺に沿ってたどる |
| 木の辺は何本? | 連結・閉路なしを確認し、頂点数から1を引く |
| 制約条件下で利益を最大化するには? | グラフ理論より線形計画法を考える |
| 相手の行動に応じた戦略選択は? | ゲーム理論を考える |
確認問題
A―B、A―C、B―D、B―Eという4本の無向の辺で5つの頂点を結んだ。このとき、頂点Bの次数はどれか。
- ア:2
- イ:3
- ウ:4
- エ:5
正解と解説を見る
正解:イ(3)。Bに直接つながる辺はBA、BD、BEの3本です。
どんな場面で使う?
コンピュータネットワーク、ソーシャルネットワーク、交通経路、作業の依存関係などを考えるときに利用します。最短経路の問題でもグラフ理論の考え方が役立ちますが、格子状の最短経路の組合せは移動回数の並べ方を扱う別の学習テーマです。
よくある誤解・混同
「次数は、その頂点から到達できるすべての頂点数」?
違います。直接つながる辺の数です。
「辺が4本、頂点が5個なら必ず木」?
違います。木であるためには連結で閉路がないことを確認する必要があります。
「有向グラフにも次数は1種類だけ」?
有向グラフでは入次数と出次数を区別します。問題文の指示を確認しましょう。
まとめ(試験直前用)
- グラフ理論:頂点(ノード)と辺(エッジ)のつながり。
- 無向グラフの次数:直接つながる辺の本数。
- 有向グラフ:入次数と出次数を区別。
- 木:連結で閉路なし。頂点 (n) 個なら辺は (n-1) 本。
- 線形計画法の座標グラフとは別の話。