グラフ理論
“グラフとは、位置を捨てて、つながりだけを残した地図です。”
数式
G = (V, E), Σ(v∈V) deg(v) = 2|E|読み方: グラフとは頂点の集合Vと、それらを結ぶ辺の集合Eである。すべての頂点の次数を合計すると辺の数の2倍になる
- V
- — 頂点の集合——「点」
- E
- — 辺の集合——点を結ぶ「線」
- deg(v)
- — vの次数——vに接続する辺の数
- Σdeg(v) = 2|E|
- — 次数の合計は辺の数の2倍に等しい（握手補題）
きっかけ
友人関係、地下鉄路線図、インターネット、分子——これらすべてが、点と線というシンプルな1枚の絵に捉えられます。
やさしく言うと
グラフとは点（頂点）と、それらを結ぶ線（辺）の集まりです。何と何がつながっているかだけを記録し、位置や形、距離は捨て去ります。関係を骨格だけに削ぎ落とした地図です。
直感
地下鉄路線図を思い浮かべてください——実際の距離や方角は正しくありませんが、「どの駅とどの駅がつながっているか」は完全に保たれています。それがグラフの精神です。点が何であれ（人、都市、ウェブページ）、線が何であれ（友情、道路、リンク）、つながりの構造だけを見ることで、まったく異なる問題が同じ問題になります。
どう作られるか
2つの要素——頂点集合Vと辺集合E。各頂点の「次数」はそこに接続する辺の数です。握手補題：すべての次数を足すと、ちょうど辺の数の2倍になります（各辺はその両端でそれぞれ1回ずつ数えられるから）。このシンプルな数え方は驚くほど強力です。
例
三角形グラフ：頂点3個、辺3個。各頂点の次数は2なので、次数の合計は2+2+2 = 6 = 2 × 3（辺の数）。握手補題がぴったり成り立っています。
よくある誤解
ここでの「グラフ」は関数y=f(x)の曲線ではありません。軸も曲線もなく、点とそれを結ぶ線のネットワークだけです。同じ言葉でも、まったく違うものを指しています。
どこで使うか
Googleの検索ランキング（PageRank）、GPSの最短経路、ソーシャルネットワーク分析、回路設計、スケジューリングや彩色問題、感染症の拡大モデル——ものとものがつながる問題はすべてグラフです。
どこから来たか
1736年、オイラーはケーニヒスベルクの7つの橋をすべて一度ずつ渡れるかというパズルを解き、グラフ理論とトポロジーの扉を開きました（答え：不可能）。
前提概念
確認問題
握手補題によると、辺が5本のグラフのすべての頂点の次数の合計はいくつですか？
- 5
- 10✓
- 25
- 2.5
練習
辺が4本のグラフのすべての頂点の次数の合計を求めなさい。
答え: 8
- 握手補題：次数の合計 = 辺の数 × 2
- = 2 × 4 = 8
ポイント: 辺1本ごとに次数の合計に2が加わります。
完全グラフK₄（頂点4個、すべてのペアが結ばれている）の辺の数を求めなさい。
答え: 6
- 4個から2個を選ぶ方法の数、C(4,2)
- = (4·3)/2 = 6
ポイント: 完全グラフKₙの辺の数はn(n−1)/2です。
次数3, 3, 2, 2の頂点を持つグラフの辺の数を求めなさい。
答え: 5
- 次数の合計 = 3+3+2+2 = 10
- 辺の数 = 10 / 2 = 5
ポイント: 辺の数は次数の合計の半分です。
ケーニヒスベルクの7つの橋をすべて一度ずつ渡る経路が存在しない理由を、次数を使って説明しなさい。
答え: undefined
- そのような経路（オイラー路）には、奇数次数の頂点が0個か2個必要
- ケーニヒスベルクでは4つの陸地すべてが奇数次数
- 奇数次数の頂点が4個（2個を超える）あるので不可能
ポイント: 奇数次数の頂点が3個以上あると、オイラー路は存在しません。