グラフ理論まとめ：定義・定理・アルゴリズムを一覧で整理【離散数学・競技プログラミング】

グラフ理論の全体像を一記事で．グラフの定義から平面性・彩色・マトロイドまで，離散数学と競技プログラミングに必要な定義・定理・アルゴリズムを体系的にまとめた．各トピックの依存関係図付き．

2026年2月27日

1. はじめに：この記事の使い方

この記事は，学部レベルのグラフ理論を一記事で俯瞰することを目的とする．各トピックについて，定義・主要定理・アルゴリズムを簡潔にまとめる．

使い方：

初学者 → セクション順に読み進め，グラフ理論の全体像を掴むとよい
復習・試験対策 → 目次から必要なセクションへジャンプされたい
競プロの確認 → セクション14「定理・アルゴリズム一覧」で主要結果を一覧できる

以下の依存関係図は，各トピックがどのように繋がっているかを示す．

graph TD
    A["グラフの基礎定義"] --> B["道と連結性"]
    B --> C["木と森"]
    B --> D["オイラー・ハミルトン"]
    C --> E["最短経路"]
    B --> E
    B --> F["有向グラフとトポロジカルソート"]
    B --> G["マッチングと被覆"]
    G --> H["ネットワークフロー"]
    A --> I["平面グラフ"]
    I --> J["グラフ彩色"]
    A --> K["代数的グラフ理論"]
    C --> L["マトロイドと貪欲法"]

    style A fill:#f5f5f5,stroke:#333,color:#000
    style E fill:#f5f5f5,stroke:#333,color:#000
    style H fill:#f5f5f5,stroke:#333,color:#000
    style L fill:#f5f5f5,stroke:#333,color:#000

注意 1.

本記事は「グラフ理論の教科書」シリーズの各記事と連携している．各セクション末尾のリンクから，体系的な解説・証明に進むことができる．

2. グラフの基礎定義

定義 2 (グラフ).

無向グラフ（undirected graph）

G = (V, E)

とは，有限集合

V

（頂点集合）と，

V

の2元部分集合の集合

E \subseteq (2 V)

（辺集合）の組である．有向グラフ（directed graph）

G = (V, A)

では，辺は順序対

A \subseteq V \times V

で与えられる．

定義 3 (次数).

無向グラフにおける頂点

v

の次数（degree）

de g (v)

は，

v

に接続する辺の本数である．有向グラフでは入次数

de g^{-} (v)

と出次数

de g^{+} (v)

を区別する．

定理 4 (握手の補題).

無向グラフ

G = (V, E)

において

v \in V \sum de g (v) = 2∣ E ∣

特に，次数が奇数の頂点の個数は偶数である．

定義 5 (特殊なグラフ).

完全グラフ $K_{n}$ ： $n$ 頂点の任意の2頂点間に辺があるグラフ． $∣ E ∣ = (2 n)$
完全二部グラフ $K_{m, n}$ ： $V = V_{1} \cup V_{2}$ （ $∣ V_{1} ∣ = m, ∣ V_{2} ∣ = n$ ）， $V_{1}$ と $V_{2}$ の間のすべてのペアに辺を張ったグラフ
補グラフ $\overset{ˉ}{G}$ ： $E (\overset{ˉ}{G}) = (2 V) ∖ E (G)$

定義 6 (グラフの同型).

G_{1} = (V_{1}, E_{1})

と

G_{2} = (V_{2}, E_{2})

が同型であるとは，全単射

φ : V_{1} \to V_{2}

が存在して

{u, v} \in E_{1} ⟺ {φ (u), φ (v)} \in E_{2}

が成り立つことをいう．

→ 詳しくは：

https://interconnectd.app/articles/dL2zmNaJ814pPXZNDoOA

3. 道と連結性

定義 7 (道・閉路).

頂点列

v_{0}, v_{1}, \dots, v_{k}

で，連続する2頂点が辺で結ばれているものを歩道（walk）という．頂点が重複しないとき道（path）という．

v_{0} = v_{k}

のとき閉路（cycle）という．

定義 8 (連結).

任意の2頂点

u, v

間に道が存在するとき，

G

は連結（connected）であるという．極大連結部分グラフを連結成分という．

定義 9 (連結度).

G

の頂点連結度

κ (G)

は，

G

を非連結にするために除去が必要な最小頂点数である．辺連結度

λ (G)

は，最小辺数である．

定理 10 (Whitneyの不等式).

κ (G) \leq λ (G) \leq δ (G)

ここで

δ (G) = min_{v \in V} de g (v)

は最小次数である．

定義 11 (切断点・橋).

除去すると連結成分数が増加する頂点を切断点（cut vertex），辺を橋（bridge）という．

定理 12 (二部グラフの判定).

グラフ

G

が二部グラフ（bipartite graph）である

⟺

G

に奇閉路が存在しない．

定理 13 (Mengerの定理).

グラフ

G

の2頂点

s, t

について，

s

t

間の互いに内部頂点を共有しない道の最大本数は，

s

t

間を分離する最小頂点集合のサイズに等しい．

→ 詳しくは：

https://interconnectd.app/articles/eD3ngWQ0P48zNAC9alpy

4. 木と森

定義 14 (木).

閉路を持たない連結グラフを木（tree）という．閉路を持たないグラフ（連結とは限らない）を森（forest）という．

定理 15 (木の同値条件).

n

頂点のグラフ

T

について，次は同値である：

$T$ は木（連結かつ閉路なし）
$T$ は連結で $∣ E ∣ = n - 1$
$T$ は閉路なしで $∣ E ∣ = n - 1$
任意の2頂点間にちょうど1本の道が存在する
$T$ は連結だが，任意の辺を除くと非連結になる
$T$ は閉路を持たないが，任意の辺を追加すると閉路ができる

定理 16 (Cayleyの公式).

n

頂点のラベル付き木の総数は

n^{n - 2}

である．

定義 17 (全域木).

グラフ

G

の全域木（spanning tree）とは，

G

のすべての頂点を含む

G

の部分グラフであって木であるものをいう．

定義 18 (最小全域木).

辺重み付きグラフにおいて，辺重みの和が最小の全域木を最小全域木（MST）という．

主要アルゴリズム：

Kruskalのアルゴリズム：辺を重み順にソートし，閉路ができない限り追加． $O (∣ E ∣ lo g ∣ E ∣)$
Primのアルゴリズム：ある頂点から出発し，最小重みの辺で木を拡大． $O (∣ E ∣ lo g ∣ V ∣)$

定理 19 (カット性質).

任意のカット（

V

を2つに分ける辺集合）の最小重み辺はある MSTに含まれる．

→ 詳しくは：

https://interconnectd.app/articles/gaxkQJMoXSEyiKRBco9B

5. オイラーグラフとハミルトングラフ

定義 20 (オイラー閉路・オイラーグラフ).

すべての辺をちょうど1回ずつ通る閉路をオイラー閉路（Eulerian circuit）という．オイラー閉路を持つグラフをオイラーグラフという．

定理 21 (オイラーの定理).

連結グラフ

G

がオイラーグラフである

⟺

すべての頂点の次数が偶数である．

定義 22 (ハミルトン閉路).

すべての頂点をちょうど1回ずつ通る閉路をハミルトン閉路（Hamiltonian cycle）という．

定理 23 (Diracの定理).

n \geq 3

の単純グラフ

G

でもし

δ (G) \geq n /2

ならば

G

はハミルトン閉路を持つ．

定理 24 (Oreの定理).

n \geq 3

の単純グラフで，隣接しない任意の2頂点

u, v

に対して

de g (u) + de g (v) \geq n

ならば

G

はハミルトン閉路を持つ．

注意 25.

オイラー閉路の存在判定は

O (∣ E ∣)

で可能だが，ハミルトン閉路の存在判定はNP完全問題である．

→ 詳しくは：

https://interconnectd.app/articles/Lxy0UjLpWgByBoiKiYFT

6. 最短経路問題

定義 26 (最短経路).

辺重み

w : E \to R

を持つグラフにおいて，

s

t

間の最短経路とは辺重みの和が最小の道をいう．その重みの和を

dist (s, t)

と書く．

主要アルゴリズム：

BFS：重みなしグラフの単一始点最短路． $O (∣ V ∣ + ∣ E ∣)$
Dijkstra：非負重みグラフの単一始点最短路． $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$ （二分ヒープ使用時）
Bellman-Ford：負辺を含むグラフの単一始点最短路． $O (∣ V ∣∣ E ∣)$ ．負閉路の検出も可能
Warshall-Floyd：全頂点間最短路． $O (∣ V ∣^{3})$
DAG上の最短路：トポロジカルソートに沿って緩和． $O (∣ V ∣ + ∣ E ∣)$

定理 27 (Dijkstraの正当性).

非負重みグラフにおいて，Dijkstraのアルゴリズムは確定済み頂点の距離が最短であることを不変条件として保つ．

定理 28 (負閉路の検出).

Bellman-Fordで

∣ V ∣

回目の反復で更新が生じる

⟺

s

から到達可能な負閉路が存在する．

→ 詳しくは：

https://interconnectd.app/articles/bomEbDtztcOegRkTUd0P

7. 有向グラフとトポロジカルソート

定義 29 (強連結).

有向グラフ

G

の任意の2頂点

u, v

間に

u \to v

と

v \to u

の有向道が存在するとき，

G

は強連結（strongly connected）であるという．極大強連結部分グラフを強連結成分（SCC）という．

定理 30 (SCCの縮約).

有向グラフの各 SCC を1頂点に縮約すると DAG（有向非巡回グラフ）になる．

SCCのアルゴリズム：

Kosarajuのアルゴリズム：DFS2回． $O (∣ V ∣ + ∣ E ∣)$
Tarjanのアルゴリズム：DFS1回とスタック． $O (∣ V ∣ + ∣ E ∣)$

定義 31 (トポロジカルソート).

DAG

G

の頂点に全順序

v_{1}, v_{2}, \dots, v_{n}

を与えて，

(v_{i}, v_{j}) \in A \Rightarrow i < j

が成り立つようにすることをトポロジカルソートという．

定理 32.

グラフがトポロジカルソート可能

⟺

DAG である．

注意 33.

DAG上のDPは，トポロジカルソート順に状態を処理することで，最長路や経路数などの問題を

O (∣ V ∣ + ∣ E ∣)

で解ける．

→ 詳しくは：

https://interconnectd.app/articles/PhqOyej79FM9hJF1IEWu

8. マッチングと被覆

定義 34 (マッチング).

辺集合

M \subseteq E

で，

M

のどの2辺も端点を共有しないものをマッチング（matching）という．

∣ M ∣

が最大のものを最大マッチングという．

定義 35 (増加路).

マッチング

M

に関する増加路（augmenting path）とは，

M

に含まれない辺と

M

に含まれる辺が交互に現れる道で，両端が

M

に被覆されていないものをいう．

定理 36 (Bergeの定理).

マッチング

M

が最大

⟺

M

に関する増加路が存在しない．

定理 37 (Hallの結婚定理).

二部グラフ

G = (X \cup Y, E)

において，

X

の完全マッチングが存在する

⟺

任意の

S \subseteq X

に対して

∣ N (S) ∣ \geq ∣ S ∣

（Hall条件）．

定理 38 (Königの定理).

二部グラフにおいて，最大マッチングのサイズ

=

最小頂点被覆のサイズ．

定理 39 (Gale-Shapleyのアルゴリズム).

安定マッチング問題（

n

人と

n

人の選好リストが与えられたとき，ブロッキングペアのないマッチングを求める問題）は

O (n^{2})

で解ける．

→ 詳しくは：

https://interconnectd.app/articles/9XWlGbZ9vPHoLXgQVlYa

9. ネットワークフロー

定義 40 (フローネットワーク).

有向グラフ

G = (V, A)

，容量関数

c : A \to R_{\geq 0}

，始点

s

，終点

t

の4つ組

(G, c, s, t)

をフローネットワークという．フロー

f : A \to R_{\geq 0}

は容量制約

f (e) \leq c (e)

と流量保存則を満たす関数である．

定義 41 (カット).

S \subseteq V

（

s \in S

，

t \in / S

）としたとき，

S

から

V ∖ S

への辺の容量の和

c (S, V ∖ S) = \sum_{(u, v) \in A, u \in S, v \in / S} c (u, v)

をカットの容量という．

定理 42 (最大フロー最小カット定理).

最大フローの値

=

最小カットの容量．

主要アルゴリズム：

Ford-Fulkerson法：残余グラフ上の増加路を反復的に探す
Edmonds-Karp：BFSで増加路を選択． $O (∣ V ∣∣ E ∣^{2})$
Dinicのアルゴリズム：レベルグラフとブロッキングフロー． $O (∣ V ∣^{2} ∣ E ∣)$

定理 43 (二部マッチングへの帰着).

二部グラフの最大マッチングは，始点

s

，終点

t

を追加して各辺容量1のフローネットワークを構成することで，最大フロー問題に帰着できる．

→ 詳しくは：

https://interconnectd.app/articles/FcN78m9a22pq5LV5mEFl

10. 平面グラフ

定義 44 (平面グラフ).

辺の交差なしに平面上に描けるグラフを平面的（planar）であるという．そのような描画を平面グラフ（plane graph）という．

定理 45 (オイラーの多面体公式).

連結平面グラフ

G

において

V - E + F = 2

ここで

V

は頂点数，

E

は辺数，

F

は面数（外面を含む）である．

定理 46 (辺数の上界).

∣ V ∣ \geq 3

の単純連結平面グラフにおいて

∣ E ∣ \leq 3∣ V ∣ - 6

．特に

K_{5}

は平面的でない．

G

が三角形を含まない（

K_{3, 3}

型）場合は

∣ E ∣ \leq 2∣ V ∣ - 4

である．

定理 47 (Kuratowskiの定理).

グラフ

G

が平面的

⟺

G

は

K_{5}

または

K_{3, 3}

の部分分割（subdivision）を部分グラフとして含まない．

定義 48 (双対グラフ).

平面グラフ

G

の双対グラフ

G^{*}

は，

G

の各面を頂点とし，共有辺で隣接する面同士を辺で結んだグラフである．

→ 詳しくは：

https://interconnectd.app/articles/D89xD9bYJmYE6uVOIIYC

11. グラフ彩色

定義 49 (頂点彩色).

グラフ

G

の頂点彩色（vertex coloring）とは，隣接する2頂点に異なる色を割り当てることである．

k

色で彩色可能なとき

G

は

k

-彩色可能といい，必要な最小の色数を彩色数

χ (G)

という．

定理 50 (基本的な不等式).

ω (G) \leq χ (G) \leq Δ (G) + 1

ここで

ω (G)

はクリーク数，

Δ (G)

は最大次数である．

定理 51 (Brooksの定理).

連結グラフ

G

が完全グラフでも奇閉路でもなければ

χ (G) \leq Δ (G)

である．

定義 52 (彩色多項式).

P (G, k)

を

G

の

k

色彩色の総数とすると，

P (G, k)

は

k

の多項式となる．

定理 53 (Vizingの定理).

単純グラフ

G

の辺彩色数

χ^{'} (G)

について

Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1

．

定理 54 (四色定理).

任意の平面グラフは4-彩色可能である（

χ (G) \leq 4

）．

注意 55.

四色定理は1976年にAppelとHakenにより，コンピュータを用いた場合分けで初めて証明された．

→ 詳しくは：

https://interconnectd.app/articles/hz41t0UMANbrxPe1jcIs

12. 代数的グラフ理論

定義 56 (隣接行列).

n

頂点のグラフ

G

の隣接行列

A = (a_{ij})

は，

a_{ij} = 1

（

{i, j} \in E

のとき），

a_{ij} = 0

（それ以外）で定まる

n \times n

行列である．

定理 57 (道の数え上げ).

A^{k}

の

(i, j)

成分は，頂点

i

から頂点

j

への長さ

k

の歩道の本数に等しい．

定義 58 (ラプラシアン行列).

L = D - A

（

D

は次数行列）をラプラシアン行列という．

L

は半正定値で，固有値

0 \leq λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}

をもつ．

定理 59 (ラプラシアンと連結性).

L

の固有値

0

の重複度は

G

の連結成分数に等しい．特に

λ_{2} > 0 ⟺ G

は連結である．

λ_{2}

を代数的連結度（algebraic connectivity）という．

定理 60 (行列木定理（Kirchhoff）).

G

の全域木の本数は，

L

の任意の

(i, i)

余因子に等しい．

→ 詳しくは：

https://interconnectd.app/articles/2LILYC8PpZPkwFfcmSun

13. マトロイドと貪欲法

定義 61 (マトロイド).

有限集合

E

とその部分集合族

I \subseteq 2^{E}

の組

(E, I)

がマトロイド（matroid）であるとは，次の3条件を満たすことをいう：

$\emptyset \in I$
$A \in I$ ， $B \subseteq A \Rightarrow B \in I$ （遺伝性）
$A, B \in I$ ， $∣ A ∣ < ∣ B ∣ \Rightarrow \exists b \in B ∖ A$ s.t. $A \cup {b} \in I$ （交換性質）

I

の元を独立集合という．

例 62 (グラフ的マトロイド).

グラフ

G = (V, E)

に対して，

E

の部分集合が閉路を含まないとき独立と定めると，

(E, I)

はマトロイドをなす．これをグラフ的マトロイド（graphic matroid）という．独立集合は森，基底は全域木に対応する．

定理 63 (貪欲法の最適性).

(E, I)

がマトロイドのとき，重み

w : E \to R

に対する最大重み独立集合は貪欲法で求まる：重みの大きい順に，独立性を壊さない限り加えていく．

定理 64 (逆も成立).

(E, I)

が遺伝性を満たすとき，任意の重み関数に対して貪欲法が最大重み独立集合を与える

⟺

(E, I)

はマトロイドである．

注意 65.

Kruskalのアルゴリズムは，グラフ的マトロイド上の貪欲法に他ならない．「なぜ貪欲で最適解が得られるか」の答えがマトロイドである．

→ 詳しくは：

https://interconnectd.app/articles/PLR7YEBUPJRoULtY3lEQ

14. グラフ理論の定理・アルゴリズム一覧

離散数学と競技プログラミングで登場する主要な定理とアルゴリズムの一行サマリーである．

基本定理：

握手の補題： $\sum de g (v) = 2∣ E ∣$
二部グラフ判定：奇閉路なし $⟺$ 二部グラフ
木の辺数： $n$ 頂点の木は $n - 1$ 辺を持つ
Cayleyの公式： $n$ 頂点のラベル付き木の数は $n^{n - 2}$
オイラーの定理：連結 $+$ 全頂点偶数次数 $⟺$ オイラー閉路
Diracの定理： $δ (G) \geq n /2$ ならハミルトン閉路あり
オイラーの多面体公式： $V - E + F = 2$
Kuratowskiの定理： $K_{5}, K_{3, 3}$ の部分分割がなければ平面的
四色定理：任意の平面グラフは4-彩色可能
Brooksの定理： $χ (G) \leq Δ (G)$ （完全グラフ・奇閉路を除く）
Vizingの定理： $Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1$

マッチング・フローの定理：

Bergeの定理：最大マッチング $⟺$ 増加路なし
Hallの結婚定理： $∣ N (S) ∣ \geq ∣ S ∣$ $⟺$ 完全マッチング存在
Königの定理：二部グラフで最大マッチング $=$ 最小頂点被覆
最大フロー最小カット定理：最大フロー $=$ 最小カット
Mengerの定理：最大独立路数 $=$ 最小分離集合

代数・構造の定理：

行列木定理：全域木の本数 $=$ ラプラシアンの余因子
$A^{k}$ 定理： $(A^{k})_{ij}$ $=$ 長さ $k$ の歩道数
貪欲法の最適性：マトロイド上で貪欲法は最適

主要アルゴリズム：

BFS / DFS： $O (∣ V ∣ + ∣ E ∣)$
Dijkstra： $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$
Bellman-Ford： $O (∣ V ∣∣ E ∣)$
Warshall-Floyd： $O (∣ V ∣^{3})$
Kruskal： $O (∣ E ∣ lo g ∣ E ∣)$
Prim： $O (∣ E ∣ lo g ∣ V ∣)$
Kosaraju / Tarjan（SCC）： $O (∣ V ∣ + ∣ E ∣)$
Dinic（最大フロー）： $O (∣ V ∣^{2} ∣ E ∣)$
Gale-Shapley（安定マッチング）： $O (n^{2})$

15. 付録：記号と用語一覧

記号	読み	意味
$G = (V, E)$	グラフ	頂点集合 $V$ と辺集合 $E$ の組
$de g (v)$	次数	$v$ に接続する辺の数
$δ (G)$	最小次数	$min_{v} de g (v)$
$Δ (G)$	最大次数	$max_{v} de g (v)$
$κ (G)$	頂点連結度	非連結化に必要な最小頂点除去数
$λ (G)$	辺連結度	非連結化に必要な最小辺除去数
$K_{n}$	完全グラフ	$n$ 頂点の完全グラフ
$K_{m, n}$	完全二部グラフ	サイズ $m, n$ の完全二部グラフ
$χ (G)$	彩色数	頂点彩色に必要な最小色数
$χ^{'} (G)$	辺彩色数	辺彩色に必要な最小色数
$ω (G)$	クリーク数	最大クリークのサイズ
$A$	隣接行列	$a_{ij} = [{i, j} \in E]$
$L = D - A$	ラプラシアン	次数行列と隣接行列の差
MST	最小全域木	辺重みの和が最小の全域木
SCC	強連結成分	極大強連結部分グラフ
DAG	有向非巡回グラフ	有向閉路を持たない有向グラフ
NP完全	NP-complete	多項式時間で検証可能な決定問題の最困難クラス

グラフ理論離散数学まとめ定理一覧アルゴリズム競技プログラミング

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 フォロワー·105 記事

グラフ理論まとめ：定義・定理・アルゴリズムを一覧で整理【離散数学・競技プログラミング】

1. はじめに：この記事の使い方

2. グラフの基礎定義

3. 道と連結性

4. 木と森

5. オイラーグラフとハミルトングラフ

6. 最短経路問題

7. 有向グラフとトポロジカルソート

8. マッチングと被覆

9. ネットワークフロー

10. 平面グラフ

11. グラフ彩色

12. 代数的グラフ理論

13. マトロイドと貪欲法

14. グラフ理論の定理・アルゴリズム一覧

15. 付録：記号と用語一覧

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ