グラフ理論とは？サイクリックグラフや重み付きグラフを基礎から理解しよう

はじめに

電車の路線図、道路網、SNSの人間関係、コンピュータネットワーク。

一見すると違うものですが、

「もの」と「もの同士のつながり」

として考えると、共通した形で表現できます。

例えば、

A ----- B
|       |
C ----- D

のように、

A・B・C・Dという「もの」
それらを結ぶ「つながり」

として表現できます。

このように、もの同士のつながりを数学的に扱うのが**グラフ理論（Graph Theory）**です。

グラフには、

無向グラフ
有向グラフ
サイクリックグラフ
連結グラフ
完全グラフ
重み付きグラフ
木

など、さまざまな種類があります。

この記事では、それぞれの違いを中心にグラフ理論を整理していきます。

1. グラフとは

グラフは基本的に、

頂点（Vertex）
辺（Edge）

から構成されます。

例えば、

A ----- B
      /
     C

なら、

頂点 = A、B、C

で、

辺 = A-B、B-C

です。

数学的には、

G = (V, E)

と表すことがあります。

ここで、

V = 頂点の集合
E = 辺の集合

です。

🍯 はちみつメモ

グラフ = 頂点と辺を使って「もの同士のつながり」を表したもの

2. 頂点と辺

グラフを理解するときは、まず、

頂点 = もの
辺   = つながり

と考えると分かりやすいです。

例えば電車なら、

頂点 = 駅
辺   = 路線

SNSなら、

頂点 = ユーザー
辺   = フォローや友達関係

ネットワークなら、

頂点 = ルータやスイッチ
辺   = 通信経路

と考えることができます。

3. 無向グラフ

辺に方向がないグラフを**無向グラフ（Undirected Graph）**と呼びます。

例えば、

A ----- B

という場合、

AからBへも、BからAへもつながっていると考えます。

友達関係などがイメージしやすい例です。

Aさん ----- Bさん

AさんとBさんが友達なら、お互いにつながっています。

4. 有向グラフ

辺に方向があるグラフを**有向グラフ（Directed Graph）**と呼びます。

例えば、

A -----> B

という場合、

AからBへのつながりはありますが、BからAへのつながりがあるとは限りません。

SNSのフォロー関係なら、

Aさん
  ↓ フォロー
Bさん

のように一方向の関係を表現できます。

5. サイクリックグラフとは

グラフの中に、ある頂点から出発して辺をたどり、再び元の頂点へ戻る道筋が存在するものを、**サイクリックグラフ（Cyclic Graph）**と呼びます。

例えば、

A ----- B
|       |
|       |
D ----- C

というグラフでは、

A
↓
B
↓
C
↓
D
↓
A

と一周して元のAへ戻ることができます。

このような一周する道筋を**閉路（Cycle）**といいます。

つまり、

閉路を持つグラフがサイクリックグラフ

です。

6. アサイクリックグラフ

反対に、閉路を持たないグラフを**アサイクリックグラフ（Acyclic Graph）**と呼びます。

例えば、

A ----- B ----- C
        |
        D

では、どこから出発しても一周して元の場所へ戻ることはできません。

そのため、これはアサイクリックなグラフです。

整理すると、

閉路あり
↓
サイクリックグラフ

閉路なし
↓
アサイクリックグラフ

です。

7. DAGとは

有向グラフの中でも、

閉路を持たない有向グラフ

をDAGと呼びます。

正式名称は、

Directed Acyclic Graph

です。

日本語では有向非巡回グラフなどと呼ばれます。

例えば、

A → B → D
 \
  → C → D

のようなグラフです。

矢印の方向に進んでも、元の頂点へ戻ることはできません。

DAGは、

作業の依存関係
ビルド処理
タスク管理
Gitのコミット構造

などでも利用される考え方です。

🍯 はちみつメモ

DAG = 方向はあるけれど、ぐるっと一周できないグラフ

8. 次数

ある頂点につながっている辺の数を**次数（Degree）**と呼びます。

例えば、

    B
    |
A --C-- D

なら、Cには3本の辺がつながっています。

そのため、

Cの次数 = 3

です。

A、B、Dはそれぞれ、

次数 = 1

となります。

9. 有向グラフの次数

有向グラフでは、次数を、

入次数
出次数

に分けて考えます。

例えば、

A -----> B

なら、

Aから辺が出ているので、

Aの出次数 = 1

です。

Bには辺が入ってくるので、

Bの入次数 = 1

です。

つまり、

入次数
=
その頂点へ入ってくる辺の数

出次数
=
その頂点から出ていく辺の数

となります。

10. 経路

頂点から頂点へ、辺をたどって移動する道筋を**経路（Path）**と呼びます。

例えば、

A ----- B ----- C ----- D

なら、

A → B → C

はAからCへの経路です。

また、

A → B → C → D

も経路です。

11. 閉路

ある頂点から出発し、辺をたどって再び元の頂点へ戻る道筋を**閉路（Cycle）**と呼びます。

例えば、

A ----- B
|       |
D ----- C

なら、

A → B → C → D → A

が閉路です。

この閉路が存在するかどうかによって、

サイクリック
アサイクリック

を区別できます。

12. さまざまなグラフ

グラフには、その構造や辺の性質によってさまざまな種類があります。

代表的なものを整理すると、

種類	特徴
無向グラフ	辺に方向がない
有向グラフ	辺に方向がある
サイクリックグラフ	閉路を持つ
アサイクリックグラフ	閉路を持たない
連結グラフ	すべての頂点が何らかの経路でつながる
完全グラフ	すべての頂点同士が直接つながる
重み付きグラフ	辺に数値を持つ
木	連結かつ閉路を持たない

グラフを見るときは、

方向がある？

閉路がある？

全部つながっている？

辺に数値がある？

という観点で見ると整理しやすくなります。

13. 連結グラフ

すべての頂点が何らかの経路でつながっている無向グラフを**連結グラフ（Connected Graph）**と呼びます。

例えば、

A ----- B ----- C
        |
        D

では、AからDにも、CからAにも移動できます。

そのため連結グラフです。

一方、

A ----- B

C ----- D

では、A側とC側が分離しています。

そのためグラフ全体としては連結ではありません。

14. 完全グラフ

すべての異なる頂点同士が直接つながっているグラフを**完全グラフ（Complete Graph）**と呼びます。

3つの頂点なら、

    A
   / \
  B---C

です。

すべての頂点が互いに直接つながっています。

頂点がn個ある完全グラフの辺の数は、

n(n - 1)
---------
    2

です。

例えば4頂点なら、

4 × 3 ÷ 2
= 6

なので、辺は6本になります。

15. 重み付きグラフ

辺に数値を持たせたグラフを**重み付きグラフ（Weighted Graph）**と呼びます。

例えば、

     5
A -------- B
 \        /
  2      3
   \    /
     C

のようなグラフです。

数字の部分が**重み（Weight）**です。

重みには、

距離
時間
料金
通信コスト
遅延

などを設定できます。

16. 道路を重み付きグラフで表す

例えば道路なら、

東京 --30km-- A --20km-- 横浜

のように、

頂点 = 場所
辺   = 道路
重み = 距離

として表現できます。

もし料金を考えるなら、

重み = 通行料金

としても構いません。

つまり、同じグラフでも、

何を最小化したいのか

によって重みの意味を変えることができます。

17. ネットワークを重み付きグラフで表す

ネットワークでも重み付きグラフは非常に重要です。

例えば、

Router A --10-- Router B
    \             /
     5           3
      \         /
       Router C

なら、

頂点 = ルータ
辺   = 通信経路
重み = 経路コスト

のように考えられます。

ルーティングでは、

どの経路を通るのが最も適切か

を判断するために、こうしたコストの考え方が利用されます。

18. 重みなしグラフとの違い

通常のグラフでは、

A ----- B

という接続について、

つながっているかどうか

だけを考えます。

一方、重み付きグラフでは、

A --5-- B

のように、

そのつながりを利用するコストはいくらか

まで表現できます。

つまり、

通常のグラフ
=
つながりを表す

重み付きグラフ
=
つながり + コストを表す

と考えると分かりやすいでしょう。

19. 最短経路

重み付きグラフでは、

ある頂点から別の頂点まで、重みの合計が最も小さくなる経路

を求めることがあります。

これを最短経路といいます。

例えば、

      2
A -------- B
|          |
5          3
|          |
C ---1---- D

AからDまで行く場合、

A → B → D
2 + 3 = 5

です。

一方、

A → C → D
5 + 1 = 6

です。

したがって、

A → B → D

の方が小さいので最短経路になります。

20. 木

**木（Tree）**とは、

連結していて、閉路を持たないグラフ

です。

例えば、

です。

すべての頂点がつながっていますが、

ぐるっと回って元の場所へ戻る

という経路はありません。

つまり木は、

連結
+
アサイクリック

なグラフです。

21. 木とサイクリックグラフの違い

木とサイクリックグラフを比較すると分かりやすくなります。

木

A ----- B ----- C
        |
        D

閉路がありません。

サイクリックグラフ

A ----- B
|       |
D ----- C

閉路があります。

つまり、

木
=
閉路なし

サイクリックグラフ
=
閉路あり

という違いがあります。

22. 木の辺の数

頂点がn個ある木では、

辺の数 = n - 1

になります。

例えば、

頂点 = 5個

なら、

辺 = 4本

です。

これはグラフ理論で非常に重要な性質です。

23. グラフの表現方法

グラフをコンピュータで扱う場合、

A ----- B
|
C

という図そのものを保存するのではなく、

どの頂点とどの頂点が接続しているか

をデータとして表現します。

代表的な方法には、

隣接行列
隣接リスト

があります。

24. 隣接行列

**隣接行列（Adjacency Matrix）**とは、頂点同士がつながっているかどうかを行列で表現する方法です。

例えば、

A ----- B
|
C

なら、

	A	B	C
A	0	1	1
B	1	0	0
C	1	0	0

となります。

基本的には、

つながっている
=
1

つながっていない
=
0

です。

25. 重み付きグラフの隣接行列

重み付きグラフの場合は、

0か1

だけでなく、辺の重みを行列に入れることもできます。

例えば、

A --5-- B
|
2
|
C

なら、イメージとして、

	A	B	C
A	0	5	2
B	5	0	-
C	2	-	0

のように表すことができます。

つまり、

隣接行列は単純な接続関係だけでなく、重みを表現するためにも使える

ということです。

26. 隣接リスト

**隣接リスト（Adjacency List）**では、それぞれの頂点について、

どの頂点とつながっているか

を一覧にします。

例えば、

A ----- B
|
C

なら、

A : B, C
B : A
C : A

です。

隣接行列と比べて、辺が少ないグラフではメモリを効率的に使いやすい特徴があります。

27. 最小全域木

重み付きグラフでは、

すべての頂点をつなぎながら、重みの合計をできるだけ小さくする

という問題もあります。

このとき使われるのが**最小全域木（Minimum Spanning Tree）**です。

例えば、複数の拠点をネットワークで接続するとき、

全部の拠点を接続したい
+
ケーブルの総距離をできるだけ短くしたい

といった問題として考えることができます。

28. 最短経路と最小全域木

この2つは似ていますが目的が違います。

問題	目的
最短経路	ある地点から目的地までのコストを最小化する
最小全域木	すべての頂点を接続する総コストを最小化する

例えば、

東京から大阪へ一番短く行きたい

なら最短経路です。

一方、

東京・大阪・名古屋・福岡を
できるだけ安く全部つなぎたい

なら最小全域木です。

29. グラフの種類を整理しよう

今回登場したグラフを整理します。

グラフ	特徴
無向グラフ	辺に方向がない
有向グラフ	辺に方向がある
サイクリックグラフ	閉路が存在する
アサイクリックグラフ	閉路が存在しない
DAG	閉路のない有向グラフ
連結グラフ	すべての頂点がつながっている
完全グラフ	すべての異なる頂点同士が直接つながる
重み付きグラフ	辺に距離やコストなどの値を持つ
木	連結かつ閉路を持たない

これらは完全に別々の分類ではありません。

例えば、

「有向かつ重み付き」

のグラフも作れます。

A --5--> B

のような形です。

また、

「無向かつ重み付き」

もあります。

A --5-- B

つまり、

方向
閉路
連結性
重み

など、違う観点から同じグラフを分類していると考えることが重要です。

30. グラフを見るときの考え方

グラフ問題が出てきたら、最初に次のポイントを確認しましょう。

① 辺に方向がある？
↓
有向 / 無向

② 一周できる？
↓
サイクリック / アサイクリック

③ 全部の頂点がつながっている？
↓
連結かどうか

④ 辺に数字がある？
↓
重み付きグラフ

⑤ 連結で閉路がない？
↓
木

この順番で確認すると、グラフの特徴を整理しやすくなります。

まとめ

今回はグラフ理論について学びました。

この記事で覚えること

グラフは頂点と辺から構成される
辺に方向がないものを無向グラフという
辺に方向があるものを有向グラフという
閉路を持つものをサイクリックグラフという
閉路を持たないものをアサイクリックグラフという
閉路を持たない有向グラフをDAGという
すべての頂点がつながったものを連結グラフという
すべての異なる頂点同士が直接つながるものを完全グラフという
辺に距離や時間などの値を持つものを重み付きグラフという
連結かつ閉路を持たないグラフを木という
頂点がn個ある木の辺はn−1本
グラフは隣接行列や隣接リストで表現できる
重み付きグラフでは最短経路などを考える
最短経路と最小全域木では目的が異なる
グラフの種類は方向・閉路・連結性・重みなど異なる観点で分類される

🍯 はちみつメモ

グラフを見るときは「方向・閉路・連結・重み」の4つを確認しよう。

方向あり → 有向グラフ

閉路あり → サイクリックグラフ

閉路なし → アサイクリックグラフ

辺に数字あり → 重み付きグラフ

連結 + 閉路なし → 木