グラフ理論
概要
グラフ理論（graph theory）とは、頂点の集合と 2 頂点を結ぶ辺の集合からなるグラフについて、つながり方、すべての辺や頂点を通る経路、頂点の塗り分け、平面や曲面への描き方、マッチングや被覆の大きさ、ある部分グラフを含まないための辺の本数、隣接行列の固有値などを調べる数学の分野であり、組合せ論の中心的な小分野である。Königsberg の橋の問題に始まり、最短経路や流れなどの最適化の問題にも使われる。代表例として、連結で橋のないグラフには、どの頂点からどの頂点へも進める辺の向きの付け方がある（Robbins の定理）。
グラフ理論（graph theory）は、点（頂点）と、2 点を結ぶ線（辺）からなるグラフを研究する数学の分野である。Königsberg の 7 つの橋をちょうど 1 回ずつ渡る散歩ができるかという問題を、陸地を点、橋を線に置き換えて解いた Euler の仕事が、その始まりとされる（一筆書きとグラフ、Euler閉路 の例「Königsberg の橋」）。その後、地図の塗り分け、回路網、化学の分子の形、交通や通信の網、計算機の計算の構造など、「ものとものの間のつながり」が現れるところで、グラフは共通の言葉になった。
この記事では、グラフ理論が扱う対象と主な問いを定義とともに述べ、小分野と代表的な定理を、それを扱う記事とともに一覧にする。続いて、Königsberg の橋にちなむ定理として、橋（除くと連結でなくなる辺）をもたない連結なグラフにはどの頂点からどの頂点へも行ける一方通行の付け方がある、という Robbins の定理を完全に証明し、仮定を外した反例を示す。最後に、学ぶ順に記事を並べた道筋を示す。
定義
有限集合 $V$ と、$V$ の 2 元部分集合からなる集合 $E$ の組 $G=(V,E)$ を（単純な）グラフ という。$V$ の元を 頂点、$E$ の元を 辺 といい、辺 $\{u,v\}$ を $uv$ と書く。グラフの性質（つながり方、部分構造、大きさを表す量）と、グラフについての問題を解く方法を研究する数学の分野を グラフ理論（graph theory）という。
この定義は、グラフ の記事の定義「グラフの定義」で頂点の集合を有限にしたもの（有限グラフ）である。グラフの基本の言葉（隣接、次数、部分グラフ、道、閉路、連結）は グラフ の記事で定義されている。目的に応じて、定義は次のように変えられる。
- 多重グラフ：同じ 2 頂点を結ぶ辺を複数許し、ループ（1 頂点を結ぶ辺）も許す（多重グラフ）。Königsberg の橋は、同じ 2 つの陸地を結ぶ橋が 2 本ある組を含むので、多重グラフである。
- 有向グラフ：辺に向きを付ける（有向グラフ）。一方通行の道や、試合の勝ち負け（トーナメント(グラフ理論)）を表す。
- 重み付きグラフ：辺に長さや費用を付ける（重み付きグラフの最短経路）。
- 無限グラフ：頂点の集合を無限集合にする（無限グラフ）。
グラフは、頂点の集合 $V$ の上の対称で非反射的な（どの頂点も自分自身とは関係しない）2 項関係と同じものである（グラフ の記事）。したがって、有限集合の上の関係を調べる 組合せ論 の一部と見ることもでき、実際、グラフ理論は組合せ論の中心的な小分野の 1 つである。
グラフ理論の主な問い
- つながり方：グラフが連結か、何個の頂点や辺を除くと連結でなくなるか（連結グラフ、連結度(グラフ)）。閉路をもたない連結なグラフ（木）と、グラフ全体にわたる木（全域木）は、つながり方を調べる基本の道具である。
- 通り道：すべての辺をちょうど 1 回通る閉じた経路（Euler閉路）や、すべての頂点をちょうど 1 回通る閉路（Hamilton閉路）があるか。前者には次数の偶奇による簡単な判定法があるが、後者にはそのような判定法が知られていない。
- 塗り分け：隣接する頂点が同じ色にならないように何色で塗れるか（彩色数、グラフ彩色）。平面に描けるグラフは 4 色で塗れる（四色定理）。
- 描き方：辺を交差させずに平面や曲面に描けるか（平面グラフ、Kuratowskiの定理、位相的グラフ理論）。
- 組み合わせ方と覆い方：端点を共有しない辺の集まり（マッチング(グラフ理論)）、互いに隣接しない頂点の集まり（独立集合）、すべての頂点を見張る頂点の集まり（支配集合）の最大・最小の大きさと、それらの間の関係。
- 最大・最小の構造：ある部分グラフを含まないグラフは辺を何本までもてるか（極値グラフ理論、Turánの定理）、十分大きなグラフには必ずどんな規則的な部分が現れるか（Ramseyの定理）。
- 行列と固有値：隣接行列や Laplacian 行列の固有値からグラフの形を読む（スペクトルグラフ理論、行列木定理）。
- 算法と最適化：最短の経路、最小の全域木、最大の流れ、最適な割り当てを効率よく求める（Dijkstra法、ネットワークフロー、割当問題、組合せ最適化）。効率のよい方法が知られていない問題もある（NP完全）。
Petersenグラフ $P$（$\{1,\dots,5\}$ の 2 元部分集合を頂点とし、交わらないものどうしを結んだ 10 頂点のグラフ）について、上の問いの答えを、それを証明している記事とともに挙げる。
| 問い | 答え | 記事 |
|---|---|---|
| 最も短い閉路の長さ（内周） | $5$ | Petersenグラフ の命題「共通の隣接頂点と内周」 |
| Hamilton 閉路をもつか | もたない | Petersenグラフ の定理「Petersen グラフは Hamilton 閉路をもたない」 |
| 彩色数 | $3$ | Petersenグラフ の命題「Petersen グラフの彩色数」 |
| 平面グラフか | 平面グラフでない | 平面グラフ の例「Petersenグラフは平面グラフでない」 |
| 独立数 | $4$ | 独立集合 の例「Petersen グラフの独立数」 |
| 支配数 | $3$ | 支配集合 の例「基本的なグラフの支配数」 |
1 つのグラフについて、つながり方・通り道・塗り分け・描き方・覆い方の問いがそれぞれ別の答えをもち、別の方法で証明される。Petersen グラフは、多くの予想や主張の反例になることでも知られている。
小分野
| 小分野 | 主な対象と問い | 記事の例 |
|---|---|---|
| 構造グラフ理論 | 連結性、木、閉路、マイナー | 木, 全域木, 閉路, 連結度(グラフ), ブロック(グラフ) |
| 彩色 | 頂点と辺の塗り分け | 彩色数, 辺彩色, 彩色多項式, Brooksの定理, Vizingの定理 |
| 位相的グラフ理論 | 平面・曲面への描き方 | 平面グラフ, Kuratowskiの定理, 位相的グラフ理論, 四色定理 |
| マッチングと被覆 | 辺や頂点の組み合わせ方 | マッチング(グラフ理論), Hallの結婚定理, 独立集合, 支配集合 |
| 極値グラフ理論と Ramsey 理論 | 最大・最小と必ず現れる構造 | 極値グラフ理論, Mantelの定理, Turánの定理, Ramseyの定理 |
| 代数的・スペクトルグラフ理論 | 行列・群・固有値 | 隣接行列, Laplacian行列(グラフ), スペクトルグラフ理論, 強正則グラフ, Cayleyグラフ |
| 有向グラフ | 向きのある辺、到達可能性 | 有向グラフ, 非巡回有向グラフ, トーナメント(グラフ理論), 有向全域木 |
| 算法と組合せ最適化 | 探索、最短経路、流れ、割り当て | 深さ優先探索, 幅優先探索, Dijkstra法, ネットワークフロー, 割当問題 |
代表的な定理
| 定理 | 主張の要点 | 記事 |
|---|---|---|
| 次数の総和 | 次数の総和は辺の本数の 2 倍 | 次数(グラフ) の定理「次数の総和と辺数」 |
| Euler の定理 | 辺をもつ連結なグラフに Euler 閉路があるのは、すべての次数が偶数のとき | Euler閉路 |
| 木の特徴づけ | $n$ 頂点の連結なグラフが木であるのは、辺が $n-1$ 本のとき | 全域木 の命題「木の判定」 |
| 行列木定理 | 全域木の個数は Laplacian 行列の小行列式 | 行列木定理, 有向全域木 |
| 二部グラフの特徴づけ | 二部グラフであるのは、奇数の長さの閉路をもたないとき | 二部グラフ の定理「閉路の長さによる特徴付け」 |
| König の定理 | 二部グラフの最大マッチングの大きさは最小の頂点被覆の大きさ | マッチング(グラフ理論) |
| Hall の結婚定理 | 一方の部を覆うマッチングがあるための近傍の条件 | Hallの結婚定理 |
| Turán の定理 | $K_{r+1}$ を含まない $n$ 頂点のグラフの辺の本数の最大値 | Turánの定理 |
| Ramsey の定理 | 十分大きい完全グラフの辺の 2 色の塗り分けには大きな単色の完全部分グラフがある | Ramseyの定理 |
| 四色定理 | 平面グラフは 4 色で頂点を塗れる | 四色定理 |
| Kuratowski の定理 | 平面グラフであるのは、$K_5$ と $K_{3,3}$ の細分を含まないとき | Kuratowskiの定理 |
| Robbins の定理 | 連結で橋のないグラフには強連結な向き付けがある | この記事の thm-gt-robbins |
証明の方法
グラフ理論の証明でよく使われる方法を挙げる。
- 極端なものに注目する：最も長い道、最小の反例、最大のマッチングなどをとり、それより長い・小さい・大きいものが作れることを示して矛盾を導く（閉路 の定理「最小次数と長い閉路」）。
- 葉や頂点を除く帰納法：木から葉を除く、グラフから 1 頂点を除くなどして、頂点の少ないグラフに帰着させる（全域木、五色定理）。
- 交互道と増加道：マッチングを、交互に入れ替えられる道に沿って大きくする（マッチング(グラフ理論) の定理「Berge の定理」）。
- 少しずつ組み立てる：小さい部分から始めて、条件を保ちながら頂点や辺を加えていく。下の Robbins の定理の証明がこの型である。
- 行列と線形代数：グラフを行列で表し、行列式や固有値で数えたり評価したりする（行列木定理、スペクトルグラフ理論）。
- 確率：無作為に作った構造の期待値を計算して、存在を示す（確率的方法、支配集合 の定理「最小次数による上界」）。
代表例：一方通行と Robbins の定理
ある町の道路をすべて一方通行にしたい。どの交差点からどの交差点へも行けるようにするには、道路網にどんな条件が要るか。交差点を頂点、道路を辺とすれば、これはグラフの各辺に向きを付けて、強連結な有向グラフを作る問題である。
単純なグラフ $G=(V,E)$ の 向き付け とは、各辺 $uv$ について $(u,v)$ と $(v,u)$ のちょうど一方を選んで得られる有向グラフであり（有向グラフ の記事の定義「基礎グラフと向き付け」）、有向グラフが 強連結 であるとは、頂点があって、どの頂点からどの頂点へも有向歩道があることである（同記事の定義「到達可能性と強連結性」）。辺 $e$ が 橋 であるとは、$e$ を除くと連結成分が増えることである（閉路 の定義「橋」）。閉路 の定理「閉路に含まれる辺と橋」により、辺が橋でないことと、その辺がある閉路に含まれることは同値である。
$G=(V,E)$ を連結で橋をもたない単純なグラフとし、$S$ を $V$ の空でない真部分集合とする。このとき、頂点の列 $x_0,x_1,\dots,x_k$（$k\ge2$）で、次を満たすものがある。
- $x_0,x_k\in S$ であり、$x_1,\dots,x_{k-1}$ は相異なり $S$ に属さない。
- 各 $i$ について $x_{i-1}x_i\in E$ であり、これら $k$ 本の辺は相異なる。
（$x_0=x_k$ となってもよい。）このような列を $S$ の 耳 という。
$S$ の頂点と $S$ にない頂点をとり、それらを結ぶ $G$ の道（$G$ は連結）をたどると、$S$ の頂点 $u$ から $S$ にない頂点 $v$ へ進む辺 $uv$ がある。$uv$ は橋でないので、ある閉路 $C$ に含まれる。$C$ を $u=y_0,v=y_1,y_2,\dots,y_m=u$（$m\ge3$、$y_0,\dots,y_{m-1}$ は相異なる）と表すと、$C$ の $m$ 本の辺 $y_{j-1}y_j$ は相異なる。$y_m=u\in S$ なので、$y_j\in S$ となる最小の $j\ge1$ を $k$ とすると、$y_1=v\notin S$ から $k\ge2$ である。$x_i:=y_i$（$0\le i\le k$）とおけば、$x_1,\dots,x_{k-1}$ は相異なり $S$ に属さず、辺は $C$ の相異なる辺である。$\square$
連結な単純グラフ $G$ が強連結な向き付けをもつためには、$G$ が橋をもたないことが必要十分である。
必要性：$G$ が橋 $e=uv$ をもつとし、強連結な向き付け $D$ があったとする。$D$ で $e$ が $(u,v)$ の向きであるとしてよい。$D$ には $v$ から $u$ への有向歩道があり、頂点がくり返す区間を除くと、頂点が相異なる有向道 $v=z_0,z_1,\dots,z_l=u$ が得られる。この道が辺 $e$ を使うとすると、向きは $(u,v)$ なので $u$ が終点より前に現れ、頂点が相異なることに反する。よってこの道は $G-e$ の道であり、$u$ と $v$ は $G-e$ でつながっている。すると $G-e$ に $e$ を戻しても連結成分は合わさらないので、$G-e$ と $G$ の連結成分の個数は等しく、$e$ が橋であることに反する。
十分性：頂点を 1 つとり $S:=\{s\}$、$F:=\emptyset$ から始め、次の性質を保ちながら $S$ を大きくする。
(i) $F$ は、両端点が $S$ に属する $G$ の辺のいくつかにそれぞれ向きを 1 つ付けた有向辺の集合である。
(ii) 有向グラフ $(S,F)$ は強連結である。
最初は (i)(ii) が成り立つ。$S\ne V$ なら、lem-gt-ear により $S$ の耳 $x_0,\dots,x_k$ がある。耳の各辺は $x_1,\dots,x_{k-1}$ のどれかを端点にもつので、両端点が $S$ に属する辺ではなく、まだ向きが付いていない。これらに $(x_0,x_1),(x_1,x_2),\dots,(x_{k-1},x_k)$ の向きを付けて $F$ に加え、$S$ に $x_1,\dots,x_{k-1}$ を加える。新しい $S$ の 2 頂点 $a,b$ をとる。$a$ が耳の内側の頂点 $x_i$ なら、耳に沿って $x_k\in S$ へ進める。$b$ が耳の内側の頂点 $x_j$ なら、$x_0$ から耳に沿って $x_j$ へ進める。古い $S$ の中では (ii) によりどの頂点からどの頂点へも進めるので、$a\to(x_k)\to\dots\to(x_0)\to b$ とつなげば $a$ から $b$ への有向歩道がある。よって (i)(ii) は保たれる。$k\ge2$ なので $S$ は真に大きくなり、有限回で $S=V$ となる。
最後に、まだ向きの付いていない辺に任意に向きを付ける。有向辺を加えても有向歩道は残るので、得られる向き付けは強連結である。$\square$
強連結な向き付けでは、どの辺も「回り道」をもつ。次の命題は、橋がないことの有向グラフの側からの言い換えである。
ループをもたない有向グラフ $D$ が強連結なら、$D$ のどの有向辺もある有向閉路に含まれる。
有向辺 $(u,v)$ をとる（ループがないので $u\ne v$）。強連結性から $v$ から $u$ への有向歩道があり、頂点がくり返す区間を除くと、頂点が相異なる有向道 $v=z_0,\dots,z_l=u$（$l\ge1$）が得られる。$u,z_0,z_1,\dots,z_l$ は、$z_0,\dots,z_l$ が相異なり $z_l=u$ なので、有向辺 $(u,v)$ を含む有向閉路である（有向グラフ の記事の定義「有向歩道・有向道・有向閉路」）。$\square$
thm-gt-robbins の向き付けで有向閉路の向きを忘れると、長さ $3$ 以上なら $G$ の閉路になる。長さ $2$ の有向閉路 $(u,v),(v,u)$ は、各辺に向きを 1 つしか付けない向き付けには現れない。したがって prop-gt-arc-cycle から、強連結な向き付けをもつ連結なグラフのどの辺も閉路に含まれ、橋でないことが再び分かる。
thm-gt-robbins は BM76 の Theorem 10.5（p. 184）にあり、同書は Robbins（1939 年）によるとしている。同書の証明は、閉路から始めて、辺を共有しない 2 本の道を付け加えていく形で、上の証明とは組み立て方が違う。
Euler閉路 の例「Königsberg の橋」と同じく、Kneiphof 島を $A$、北岸を $B$、南岸を $C$、もう一方の中州を $D$ とする。橋は $A$—$B$ に 2 本、$A$—$C$ に 2 本、$A$—$D$、$B$—$D$、$C$—$D$ に 1 本ずつある。$A$—$B$ の 2 本を $A\to B$ と $B\to A$、$A$—$C$ の 2 本を $A\to C$ と $C\to A$ とし、残りを $A\to D$、$D\to B$、$C\to D$ とする。すると $A$ から $B,C,D$ へ直接行け、$B,C$ からは直接 $A$ へ、$D$ からは $B$ を通って $A$ へ戻れるので、どの陸地からどの陸地へも行ける。Königsberg の橋を 1 回ずつ渡って戻る散歩はできない（Euler閉路）が、橋をすべて一方通行にしても町の行き来はできる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 連結 | 共通の頂点をもたない 2 つの三角形（橋はない） | 強連結な向き付けをもつ |
| 橋がない | 1 本の辺だけのグラフ（道 $P_2$） | 強連結な向き付けをもつ |
| 各辺に向きを 1 つだけ付ける | 道 $P_2$ の辺を両向きの 2 本の有向辺にする | 強連結になるのは橋がないときに限る |
どの行も、左の条件だけを外している。
3 つの確認を開く
1 行目：各辺は三角形に含まれるので、閉路 の定理「閉路に含まれる辺と橋」により橋でない。しかし向き付けは辺の向きを変えるだけで、2 つの三角形の間には辺がないので、一方の三角形の頂点から他方へ行く有向歩道はない。
2 行目：$P_2$ は連結で、ただ 1 本の辺を除くと 2 頂点がばらばらになるので、その辺は橋である。向き付けは $1\to2$ か $2\to1$ で、どちらも逆向きには進めない。
3 行目：$P_2$ は連結で橋をもつが、辺 $12$ を $(1,2)$ と $(2,1)$ の 2 本にすれば強連結である。これは向き付けではない（向き付けは各辺について一方だけを選ぶ）。
ほかの分野とのつながり
- 位相幾何学：グラフは 1 次元の図形とみなせ、曲面に描いたグラフの面がどれも円板と同相なら、頂点・辺・面の個数から曲面の Euler 標数が分かる（Euler標数、位相的グラフ理論、Eulerの多面体定理）。
- 代数：群の生成系から作る Cayleyグラフ は、群の構造をグラフの形で表す。グラフの自己同型は群をなす（グラフの同型）。
- 線形代数と解析：Laplacian 行列の固有値は、グラフの連結性や、ランダムな歩みが平均化する速さを表す（スペクトルグラフ理論、Cheegerの不等式(グラフ)、エクスパンダーグラフ）。
- 確率：グラフの上のランダムな歩みは Markov連鎖 である。無作為に作ったグラフの性質を調べることで、条件を満たすグラフの存在が示せる（確率的方法）。
- 計算と最適化：多くの最適化問題はグラフの上の問題として述べられる（組合せ最適化、輸送問題、割当問題）。どの問題が効率よく解けるかは計算複雑性理論の中心的な問いである（NP完全、P対NP問題）。
歴史の要点
- Euler による Königsberg の橋の問題の解決が、グラフ理論の始まりとされる（Euler閉路 の例「Königsberg の橋」、一筆書きとグラフ）。
- 全域木を行列式で数える行列木定理は、Kirchhoff の電気回路の研究に由来する（行列木定理）。
- 地図の 4 色問題では、Kempe（1879 年）の議論の誤りを Heawood が指摘して 5 色で足りることを示し（1890 年）、4 色で足りることは Appel と Haken が計算機を使って証明した（1976 年に発表）。これらの経緯は 四色定理 にまとめられている。
- 一方通行の問題についての thm-gt-robbins は Robbins（1939 年）による（BM76 p. 184）。
学ぶ順の道筋
- 基本の言葉：グラフ → 次数(グラフ) → 部分グラフ → 道(グラフ) → 閉路 → 連結グラフ。高校数学からは 一筆書きとグラフ が入口になる。
- 木と通り道：木 → 森 → 全域木 → Euler閉路 → Hamilton閉路。
- 二部グラフとマッチング：二部グラフ → マッチング(グラフ理論) → Hallの結婚定理 → 独立集合 → 支配集合。
- 彩色と平面性：彩色数 → 平面グラフ → 五色定理 → Kuratowskiの定理 → 四色定理。
- 極値と Ramsey：Mantelの定理 → Turánの定理 → 極値グラフ理論 → Ramseyの定理 → Ramsey理論。
- 行列で見る：隣接行列 → Laplacian行列(グラフ) → 行列木定理 → 有向全域木 → スペクトルグラフ理論。
- 有向グラフと算法：有向グラフ → 非巡回有向グラフ → 深さ優先探索 → Dijkstra法 → ネットワークフロー → 輸送問題 → 割当問題。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
