※小説ではない※専門書 要約資料集 為替(換算)3.9万円でもらう 紐解集生成 専門 初入門 資料 作：｛作者名｝
> 学問の宇宙・数学の恒星群、派生分野。規格 §16.2 / 生産規定 §16.4 / 出典規律 §16.5 準拠。水準五〜六(後半)。
> この冊の前提 = BOOK-0077(第1巻)/ 水準帯 = 五〜六。専門用語は初出説明+「(水準n: 定義)」注記。
---
# BOOK-0128 数学派生・離散数学 — 繋がりと数え上げの奥地(第2巻)
> 学問の宇宙・数学の恒星群、派生分野。規格 §16.2 / 生産規定 §16.4 / 出典規律 §16.5 準拠。水準五〜六(後半)。
> この冊の前提 = BOOK-0077(第1巻)/ 水準帯 = 五〜六。専門用語は初出説明+「(水準n: 定義)」注記。
---
## 入口の物語 — 平面に描いた瞬間に生まれる制約
前巻(BOOK-0077)で私たちは、オイラーがケーニヒスベルクの橋をグラフ(頂点と辺だけの繋がりの図)に翻訳し、「奇数次数の頂点が0個か2個でなければ一筆書き不能」という法則を打ち立てた場面から出発した。そこから木構造、彩色問題、漸化式の入口までを歩き、「数える・比べる・繋げる」という同じ根から多くの技法が枝分かれしていることを見た。
本巻(第2巻・水準五〜六)では、その続きを歩く。グラフを平面に描いたとき何が起きるか(オイラーの公式)、平面に描けないグラフはどんな姿をしているか(クラトフスキの定理)、地図の塗り分けの限界(四色定理の中身)、パーティーで必ず起きる人間関係の構造(ラムゼー理論)、数え上げのさらに強力な道具(生成関数・カタラン数・包除原理)、そして人と仕事を過不足なく組み合わせる理論(ホールの結婚定理)へと進む。最後には、離散数学が現代のコンピュータ科学(計算複雑性)とどう地続きになっているかを見届ける。
この巻で扱う言葉: 平面グラフ・オイラーの公式(水準五)・クラトフスキの定理(水準六)・ラムゼー理論(水準六)・数え上げの高度な技法(生成関数・カタラン数・包除原理、水準五〜六)・ホールの結婚定理(水準五)・グラフ彩色の応用(水準五)・最短路問題(水準五)・計算複雑性との接続(水準六)。それぞれ初出の箇所で必ず説明を添える。
---
## 第八章 平面グラフとオイラーの公式 — 描いた瞬間に決まる数(水準五)
### 辺が交差しない描き方
グラフ(BOOK-0077第四章)は本来、頂点と辺の繋がりの情報だけを持つ抽象的な図であり、実際に紙の上でどう描くかは自由だ。しかし、あるグラフを「辺同士が絶対に交差しないように」平面の上に描けることがある。このような描き方ができるグラフを**平面グラフ(へいめんグラフ、水準五: 辺同士が交差しないように平面上に描くことができるグラフ)**と呼ぶ。
平面グラフを実際に紙に描くと、辺によって平面がいくつかの領域に区切られる。この領域(外側の無限に広がる部分も1つの領域として数える)を**面(めん、水準五: 平面グラフの辺によって区切られた領域の一つ一つ。外側の無限に広がる領域も1面として数える)**と呼ぶ。
### オイラーの公式
ここで驚くべき法則が現れる。平面グラフの頂点の数を`V`(vertexの頭文字)、辺の数を`E`(edgeの頭文字)、面の数を`F`(faceの頭文字)とすると、連結な(すべての頂点が辺を辿って繋がっている)平面グラフでは必ず次の関係が成り立つ。
```
V − E + F = 2
```
これを**オイラーの公式(水準五: 連結な平面グラフにおいて、頂点数−辺数+面数が必ず2になるという法則)**と呼ぶ。オイラー(BOOK-0077でケーニヒスベルクの橋を解いた同じ人物)が発見した、グラフの形によらず成り立つ普遍的な法則である。
具体例で確かめよう。立方体(サイコロの形)を思い浮かべる。頂点は8個(各角)、辺は12本(各辺)。立方体の表面を平面に押し広げて描く(これを「展開図的に平面へ潰す」と考えてよい)と、面は6面(立方体の各面)+外側の1面(展開図の外側)＝合計7面になる、と考えたくなるが、ここは注意が必要だ。オイラーの公式でいう「面」は、立方体の表面を球面とみなして平面に投影したときの面の数え方であり、実際には立方体の6つの面がそのまま6面としてカウントされ、外側の領域は数えない(あるいは、平面グラフとして描いた時点で最も外側の領域そのものが立方体の「裏側の面」に対応する)。
> **検算6(立方体): V=8、E=12、F=6。V−E+F = 8−12+6 = 2。オイラーの公式が成り立つ。**
もう一つ、もっと単純な例で確かめておく。三角形を1つだけ描いた平面グラフを考える。頂点3個(V=3)、辺3本(E=3)。面は「三角形の内側」と「外側の無限に広がる領域」の2つ(F=2)。
> **検算7(三角形1個): V=3、E=3、F=2。V−E+F = 3−3+2 = 2。オイラーの公式が成り立つ。**
四角形(頂点4・辺4)でも同様に、内側の面1つと外側の面1つでF=2となり、`4−4+2=2`が成り立つ。頂点や辺の数がいくつであっても、平面グラフである限りこの`V−E+F=2`という関係は崩れない——これは前巻で見た握手補題(次数の合計は辺数の2倍)と同じく、「グラフの形の細部によらず、構造そのものから自動的に決まる数」の代表例である。
### なぜこの公式が便利なのか
オイラーの公式の実用的な価値は、「頂点と辺の数さえ分かれば、実際に絵を描かなくても面の数が計算で求まる」という点にある。逆に言えば、「面の数がこの式に矛盾するようなグラフは、そもそも平面グラフとして描けない」という判定にも使える。次の第九章で見る「平面に描けないグラフ」の議論は、まさにこの発想の延長線上にある。
### 休憩所
平面グラフとは辺が交差しないように描けるグラフ。連結な平面グラフでは必ず`V−E+F=2`(オイラーの公式)が成り立つ。立方体(V=8,E=12,F=6)でも三角形1個(V=3,E=3,F=2)でも、どちらも2になる(検算6・7)。
---
## 第九章 クラトフスキの定理 — 平面に描けないグラフの正体(水準六)
### すべてのグラフが平面グラフになれるわけではない
前章で見た平面グラフは「辺が交差しないように描けるグラフ」だった。では、どんなグラフでも工夫すれば平面に描けるのだろうか——答えは「否」である。頂点の繋がり方によっては、どう線を引き直しても辺同士の交差を完全になくせないグラフが存在する。
その代表例が**完全グラフ(かんぜんグラフ、水準五: すべての頂点対の間に辺が存在するグラフ。頂点数nの完全グラフはK_nと表記する)**の`K5`(頂点5個の完全グラフ)である。頂点数がnのとき辺の数は組合せ(BOOK-0077第二章)の`C(n,2) = n×(n−1)/2`通りになる。
> **検算8(K5の辺数): K5はC(5,2) = 5×4/2 = 10。頂点5個の完全グラフの辺数は10本である。**
`K5`は5個の頂点をどう配置しても必ずどこかの辺同士が交差してしまう。これは構造そのものが平面には収まらないことが証明されている。
### もう一つの障害物・K3,3
もう一つの代表例が**完全二部グラフ(かんぜんにぶグラフ、水準五: 頂点を2つのグループに分け、異なるグループ同士のすべてのペアを辺で結んだグラフ。片方m個・もう片方n個ならK_{m,n}と表記する)**の`K3,3`である。これは「3軒の家と3つの井戸(3つの設備という寓話でも語られる)があり、すべての家からすべての設備に配管を引く」場面に対応し、3×3=9本の配管をすべて交差なく平面に描くことは不可能であることが知られている。
### クラトフスキの定理
ポーランドの数学者カジミェシュ・クラトフスキは1930年、次の定理を発表した。**あるグラフが平面グラフでないための必要十分条件は、そのグラフの中に「K5」または「K3,3」の構造が(辺を頂点で細分化したような変形も含めて)部分的に含まれていることである。** これを**クラトフスキの定理(水準六: グラフが平面グラフでないための必要十分条件は、そのグラフがK5またはK3,3の細分を部分グラフとして含むことである、というグラフ理論の定理)**と呼ぶ。
この定理のありがたみは、「あらゆる平面に描けないグラフは、突き詰めればK5かK3,3という2種類の"元凶"のどちらかを内部に隠し持っている」と言い切れる点にある。前巻の鳩の巣原理(「中身を調べずに重複を断言できる」)と同じ精神で、グラフの全体像を逐一調べなくてもこの2つの部分構造の有無だけを確認すればよいという強力な判定基準を与えている。
### 休憩所
完全グラフK5(辺数10、検算8)と完全二部グラフK3,3は、平面に交差なく描けない代表的なグラフ。クラトフスキの定理(1930年)は「平面グラフでないための必要十分条件は、K5かK3,3の構造を内部に含むこと」と言い切った。
---
## 第十章 四色定理の中身 — 計算機支援証明の意義と論争(水準六)
### 前巻の四色定理をもう一段深く
前巻(BOOK-0077第六章)では、四色定理(平面上のどんな地図も4色以内で塗り分けられる、という定理)と、1976年にケネス・アッペルとヴォルフガング・ハーケンがコンピュータの計算を用いて証明したという史実、そして証明の検証可能性をめぐる議論があったことを紹介した。本章ではその中身にもう一歩踏み込む。
### なぜ「還元」という発想が必要だったか
四色定理の証明の骨格は、地図(平面グラフに対応する)がどれほど複雑であっても、その中には必ず「ごく限られた種類の局所的なパターン(**可約配置**と呼ばれる、小さな範囲の頂点の繋がり方)」のどれかが含まれることを示し、「その局所パターンさえ4色で塗り分けられれば、地図全体も4色で塗り分けられる」という論法(局所パターンへの帰着を**還元**と呼ぶ)を積み重ねる、という発想による。
この「限られた種類の局所的なパターン」は数百種類にも及び、一つ一つ「本当に4色で塗り分け可能か」を確認する必要があった。人間の手作業では非現実的な分量であり、アッペルとハーケンはコンピュータにこの膨大な場合分けの検証を担わせた。
### 論争の内容
発表当初、数学界でこの証明の扱いをめぐって議論が起きた。
第一に、**証明の全過程を人間が目視で追うことができない**という点。数学の証明は伝統的に「他の数学者が一行ずつ論理を追って検証できる」ことが要件とされてきたが、コンピュータが行った膨大な場合分けの計算過程を人間が逐一検証することは事実上不可能だった。
第二に、**コンピュータのプログラム自体に誤りがないかをどう保証するか**という点。もしプログラムにバグがあれば、証明全体の正しさが揺らいでしまう。
これらの論争を経て、その後の独立な検証(別の研究者グループによる異なる手法での再確認を含む)が進み、四色定理の証明は現在では広く数学界に受け入れられている。ただし、「計算機に本質的に依存する証明」というスタイル自体が、数学の方法論上の一つの論点として意識されるようになったこと自体は史実として明記しておく。彩色問題のスケジューリング等への応用は第十四章で扱う。
### 休憩所
四色定理の証明は「地図を有限種類の局所パターンに還元し、各パターンをコンピュータで検証する」という構成。証明を人間が全過程で検証できない点、プログラムの正しさの保証が必要な点が論争になったが、その後の独立検証を経て現在は広く受け入れられている。
---
## 第十一章 ラムゼー理論 — 秩序は必ずどこかに潜んでいる(水準六)
### パーティーの法則
6人が集まるパーティーがある。任意の2人は「互いに知り合い」か「互いに他人(初対面)」のどちらかであるとする(中間はない、という前提を置く)。このとき、次の主張が成り立つ。
**6人が集まれば、必ず「互いに知り合いである3人組」か「互いに他人である3人組」のどちらかが存在する。**
これを**ラムゼー数(すいすう、水準六: 「互いに知り合いのm人組」か「互いに他人のn人組」のどちらかが必ず存在することを保証する最小の人数。R(m,n)と表記する)**の言葉で言うと、`R(3,3) = 6`と表される。この分野を**ラムゼー理論(水準六: 十分に大きな集合の中には、必ず何らかの秩序だった部分構造が存在する、ということを扱う数学の理論)**と呼ぶ。
### R(3,3)=6の完全な議論
なぜ6人でこの主張が必ず成り立つのか、順を追って確かめよう。
まず、6人のうちの1人(Aさんとする)に注目する。Aさんから見て、残り5人はそれぞれ「知り合い」か「他人」のどちらかに分類される。5人を2種類に分けるので、鳩の巣原理(BOOK-0077第三章、n個の枠にn+1個以上を入れれば必ずどこかが2個以上になる原理)により、少なくとも`⌈5/2⌉=3`人は同じ分類(「知り合い」なら知り合いが3人以上、「他人」なら他人が3人以上)に属することになる。
ここで、Aさんと「知り合い」である人が3人以上いる場合を考える(「他人」が3人以上の場合も対称的に議論できるので、片方だけ詳しく見れば十分)。その3人をB・C・Dとする。
- もしB・C・Dの中に互いに知り合いの組が1組でもあれば(たとえばBとCが知り合いなら)、A・B・Cの3人は全員互いに知り合いとなり、「知り合いの3人組」が見つかる(AとB、AとCはすでに知り合いと分かっており、BとCも知り合いだから)。
- もしB・C・Dの中に互いに知り合いの組が1組もなければ、B・C・Dの3人は互いにすべて他人同士であり、これがそのまま「他人の3人組」になる。
どちらに転んでも、必ず「知り合いの3人組」か「他人の3人組」のどちらかが見つかる。これが`R(3,3)≤6`の証明の骨格だ。
> **検算9(R(3,3)=6の下限確認): 5人では必ずしもこの主張が成り立たないことも知られている。5人を「互いに知り合いの2人組を線で結んだときに五角形の外周だけができる」ように配置する(5人を円状に並べ、隣同士だけを知り合いとし、対角線の関係はすべて他人とする)と、知り合いの3人組も他人の3人組も存在しない配置が作れる。したがって5人ではこの主張は保証されず、6人が必要最小の人数である。**
この「5人では反例が作れる」ことと「6人では必ず成り立つ」ことの両方を合わせて、`R(3,3)=6`という値が確定する。
### 大きなラムゼー数は未確定
ラムゼー理論の驚くべき点は、`R(3,3)=6`のような小さな値でさえこれだけ丁寧な議論を要するのに、もう少し大きな値になると途端に計算が困難になることだ。たとえば`R(5,5)`(互いに知り合いの5人組か、互いに他人の5人組が必ず存在することを保証する最小人数)は、2026年現在、正確な値がいまだに数学的に確定していない(下限と上限の範囲でしか分かっていない)。**この点は未確定の事実として明記しておく。** 研究者の間では「宇宙人がR(5,5)の値を要求したら全計算機資源を投入すべきだが、R(6,6)を要求されたら撃退法を考えたほうがよい」という、計算の困難さを誇張したジョークが語られることがあるが、これは学術的主張ではなく比喩的な逸話である点を明記しておく。
### なぜラムゼー理論が重要なのか
ラムゼー理論が教えてくれるのは、「完全な無秩序は、十分に大きな規模では存在しえない」という洞察だ。どれほど気まぐれに繋がりを作っても、集団が一定の大きさを超えれば必ず規則だった部分構造(秩序)が浮かび上がる。これは前巻の鳩の巣原理の精神を、より複雑なネットワークに拡張した理論だと言える。
### 休憩所
ラムゼー理論は「十分大きな集合には必ず秩序が潜む」ことを扱う理論。R(3,3)=6は「6人集まれば必ず知り合い3人組か他人3人組が存在する」ことを意味し、鳩の巣原理を使って完全に議論できる(検算9)。R(5,5)以上の大きなラムゼー数は2026年現在も正確な値が未確定である。
---
## 第十二章 数え上げの高度な技法 — 生成関数・カタラン数・包除原理(水準五)
### 生成関数という発想
前巻(BOOK-0077第二章)の数え上げの技術(和の法則・積の法則・順列・組合せ)をさらに強力にする道具の一つが**生成関数(せいせいかんすう、水準五: 数列の各項を、ある変数xの累乗の係数として並べた式に置き換え、数列の性質を式の操作として調べる道具)**である。数列`a0, a1, a2, ……`があるとき、これを`a0 + a1x + a2x² + a3x³ + ……`という式(冪級数)に対応させる。数列の足し算や特定の組合せ問題が、この式同士の足し算・掛け算という操作に翻訳できるため、複雑な数え上げ問題を式の計算に帰着させられる場面がある。生成関数は本巻では入口の考え方の紹介に留め、詳しい式変形の技法は水準がさらに上がった段階で扱う。
### カタラン数
数え上げの中でも特に有名な数列が**カタラン数(水準五: 括弧の正しい組合せ方の数など、多様な「分割・組合せ」問題に共通して現れる数列。C_nと表記し、C0=1から始まる)**である。カタラン数が現れる典型的な場面は、「n組の括弧を、開き括弧と閉じ括弧が正しく対応するように並べる場合の数」だ。ここでいう「正しく対応する」とは、どの時点で左から読んでも閉じ括弧の数が開き括弧の数を超えない、という条件を指す。
`n=3`(3組の括弧、つまり開き括弧3個・閉じ括弧3個の計6文字)の場合を全列挙してみよう。正しい組合せは次の5通りである。
```
((()))
(()())
(())()
()(())
()()()
```
> **検算10(カタラン数C3の列挙): 3組の括弧の正しい並べ方は、全列挙により`((()))`,`(()())`,`(())()`,`()(())`,`()()()`の5通り。したがってC3=5である。**
カタラン数には`C_n = C(2n,n)/(n+1)`という式があり、これに当てはめても`C3 = C(6,3)/4 = 20/4 = 5`と一致する(`C(6,3)`は6個から3個を選ぶ組合せで、前巻の組合せの技法で`6!/(3!×3!)=720/(6×6)=20`と計算できる)。カタラン数は括弧の対応関係のほかにも、木構造(BOOK-0077第五章)の枝分かれパターンの数え上げや、多角形を対角線で三角形に分割する場合の数など、一見無関係に見える多くの問題に共通して姿を現す、数え上げの世界の「万能数列」の一つである。
### 包除原理
もう一つの強力な技法が**包除原理(ほうじょげんり、水準五: 複数の集合が重なり合う場合の数を数えるとき、単純な足し算では重複を数えすぎてしまう分を、引いたり足したりして調整する数え上げの原理)**である。
例で確かめよう。1から100までの整数のうち、「3の倍数、または5の倍数」である数はいくつあるか。3の倍数は`⌊100/3⌋=33`個、5の倍数は`⌊100/5⌋=20`個(`⌊ ⌋`は小数点以下を切り捨てる記号)。単純に足すと`33+20=53`個だが、これは「3の倍数でも5の倍数でもある数(つまり15の倍数)」を2回数えてしまっている。15の倍数は`⌊100/15⌋=6`個だから、これを1回分引く必要がある。
> **検算11(包除原理): 1〜100のうち3の倍数(33個)+5の倍数(20個)−15の倍数(6個) = 33+20−6 = 47個。これが「3の倍数または5の倍数」の正しい個数である。**
このように「まず単純に足し合わせ(和の法則の素朴な適用)、重複分を引き、さらに3つ以上の集合が絡む場合は再び足し戻す……」と交互に足し引きを繰り返して正確な個数に近づけていく手法が包除原理だ。前巻の和の法則(単純に足すだけでよい場面)が「重なりがない」という前提の上に成り立っていたのに対し、包除原理は「重なりがある場面でも、足し引きの調整さえすれば正確に数えられる」という、和の法則の一般化・拡張版だと位置づけられる。
### 休憩所
生成関数は数列を式に翻訳して調べる道具。カタラン数C3=5は括弧の正しい並べ方の数と一致する(検算10)。包除原理は重なりのある集合の数え上げで、単純な足し算の重複分を引いて調整する技法であり(検算11の47個)、和の法則の拡張版にあたる。
---
## 第十三章 マッチング — ホールの結婚定理(水準五)
### 過不足なく組み合わせる問題
n人の求職者がいて、それぞれが「応募可能な求人」のリストを持っているとする。**すべての求職者に、それぞれ異なる求人を1つずつ、本人の応募可能リストの中から割り当てることができるか**——この種の「過不足のない組み合わせ」を探す問題を**マッチング(水準五: 2つのグループの要素同士を、条件を満たしながら過不足なく1対1に対応させる組合せ)**と呼ぶ。
この問題は前巻の完全二部グラフ(第九章で紹介したK3,3のような、2グループ間の繋がりを表すグラフ)の枠組みで捉えられる。片方のグループを求職者、もう片方を求人とし、「応募可能」な関係を辺で結んだグラフを考える。
### ホールの結婚定理
数学者フィリップ・ホールは1935年、この問題に完全な答えを与える定理を発表した。今でも「結婚定理」という通称で広く知られている(この名前は、伝統的に「n人の女性それぞれに、本人が交際可能な男性のリストの中から結婚相手を1人ずつ、重複なく割り当てられるか」という設定で語られてきたことに由来する、歴史的な通称である)。
**ホールの結婚定理(水準五: n人のグループの各要素に、それぞれ異なる相手を過不足なく割り当てられるための必要十分条件は、そのグループのどんな部分集合を取っても、その部分集合全体が応募・交際可能な相手の総数が、部分集合の人数以上であること、とする定理)**の主張は次の通りだ。
**すべての求職者に異なる求人を割り当てられるための必要十分条件は、「求職者のどんな部分グループを取っても、そのグループ全体が応募可能な求人の総数が、そのグループの人数以上である」ことである。**
これを**ホール条件**と呼ぶ。直感的に言えば、「もし3人の求職者が束になっても、応募可能な求人が合わせて2つしかない(3人に対して2求人しかない)ようなグループが1つでも存在すれば、その3人のうち少なくとも1人は求人にありつけない」——これは当たり前のようだが、ホールの定理の驚くべき点は「この当たり前に見える条件さえ全部の部分グループについて満たされていれば、それだけで必ず全員に割り当てが可能である」という**逆方向**まで保証している点にある。
### 小さな例で確認する
求職者A・B・Cがいて、Aは求人1・2に、Bは求人1に、Cは求人2・3に応募可能だとする。
- 部分グループ{A}: 応募可能求人は{1,2}で2個 ≥ 1人。条件満たす。
- 部分グループ{B}: 応募可能求人は{1}で1個 ≥ 1人。条件満たす。
- 部分グループ{A,B}: 応募可能求人の合計は{1,2}で2個 ≥ 2人。条件満たす。
- 部分グループ{A,C}: 応募可可求人の合計は{1,2,3}で3個 ≥ 2人。条件満たす。
- 部分グループ{B,C}: 応募可能求人の合計は{1,2,3}で3個 ≥ 2人。条件満たす。
- 部分グループ{A,B,C}: 応募可能求人の合計は{1,2,3}で3個 ≥ 3人。条件満たす。
すべての部分グループでホール条件が満たされるので、定理により全員に割り当てが可能なはずだ。実際に「Bには求人1、Aには求人2、Cには求人3」と割り当てれば、全員に重複なく求人が行き渡る。
> **検算12(ホールの結婚定理の適用): 求職者A・B・Cと求人1・2・3の例で、すべての部分グループがホール条件(部分グループの応募可能求人の合計数≥部分グループの人数)を満たすため、B→求人1、A→求人2、C→求人3という重複のない割り当てが実際に構成できる。**
### 応用
ホールの結婚定理は、**限られた候補の中から全員に重複なく資源を配分できるか**を判定する理論的土台であり、現代の応用は第十七章で扱う。次章のグラフ彩色とも「衝突なく資源を割り振る」という発想を共有している。
### 休憩所
ホールの結婚定理(1935年、フィリップ・ホール)は、2グループ間の過不足ない割り当てが可能なための必要十分条件を「どの部分グループを取っても、応募可能な相手の総数が部分グループの人数以上」というホール条件で言い切った(検算12)。
---
## 第十四章 グラフ彩色とスケジューリングの応用(水準五)
### 彩色数という考え方
前巻・本巻第十章で見た四色定理は「平面グラフに限れば4色で足りる」という特別な場合の結論だったが、一般のグラフに対しては、**彩色数(さいしきすう、水準五: あるグラフを、隣り合う頂点が同じ色にならないように塗り分けるために必要な、最小の色の数)**という値を考えることができる。
完全グラフ`K_n`(前章のK5などの仲間、すべての頂点対が辺で結ばれたグラフ)では、すべての頂点が互いに隣接しているため、`n`個の頂点すべてに異なる色を割り当てる必要があり、彩色数はちょうど`n`になる。逆に、木構造(BOOK-0077第五章、輪を作らない枝分かれのグラフ)は、根から交互に2色を塗り分けるだけで必ず塗り分けが完成するため、彩色数は常に2以下になる(頂点が1個だけなら1色で足りる)。
### スケジューリングへの翻訳
彩色問題の応用として代表的なのが試験や会議のスケジュール調整だ。「同じ学生が2つの試験を両方受ける」場合、その2つの試験は同じ時間帯に実施できない——これを「衝突する」と表現する。すべての試験を頂点とし、衝突する試験同士を辺で結んだグラフを作ると、「必要な最小の時間帯の数」は、まさにこのグラフの彩色数に一致する。同様の翻訳は、無線局の周波数割り当て(電波が干渉し合う局同士を辺で結ぶ)、レジスタ割り当て(コンピュータのプログラムが同時に使う変数同士を辺で結ぶ、情報科学BOOK-0066・BOOK-0116領域の技法)など、**「同時に同じ資源を使えない対象同士を辺で結び、彩色数を求める」**という枠組みで、驚くほど多様な分野に応用されている。
### 休憩所
彩色数は隣接頂点を同色にせず塗り分けるための最小色数。完全グラフK_nの彩色数はn、木構造の彩色数は2以下。試験スケジュールや周波数割り当ての「衝突を避けて資源を配分する」問題は、彩色問題として翻訳できる。
---
## 第十五章 最短路問題 — ダイクストラのアルゴリズム(水準五)
### 最短経路を求めるという問題
グラフの各辺に「距離」や「コスト」といった重み(数値)がついているとき、ある頂点から別の頂点まで移動する経路の中で、**通過する辺の重みの合計が最小になる経路**を求める問題を**最短路問題(さいたんろもんだい、水準五: 重み付きグラフにおいて、ある頂点から別の頂点までの、辺の重みの合計が最小になる経路を求める問題)**と呼ぶ。地図上でカーナビが最短ルートを計算する場面が、まさにこの問題そのものだ。
### ダイクストラのアルゴリズム
オランダの計算機科学者エドガー・ダイクストラは1956年にこの問題を解くアルゴリズム(手順)を考案したことが知られている(発表は1959年)。**ダイクストラのアルゴリズム(水準五: 出発点から各頂点までの最短距離を、確定済みの頂点から近い順に一つずつ確定させていくことで、重み付きグラフの最短路を求める手法)**の骨格は次のようになる。
1. 出発点の距離を0、それ以外のすべての頂点の距離を「未確定(仮に無限大)」とする。
2. 未確定の頂点の中から、現時点で最も距離が小さい頂点を1つ選び、その距離を「確定」とする。
3. 確定した頂点から直接繋がっている頂点について、「確定した頂点の距離+その辺の重み」が、現在のその頂点の暫定距離より小さければ、暫定距離を更新する。
4. すべての頂点が確定するまで2〜3を繰り返す。
このアルゴリズムの巧妙な点は、「一度確定した頂点の距離は、その後どんなに探索を続けても二度と縮まらない」という性質を利用し、無駄な再計算を避けながら、必ず最短距離にたどり着ける点にある(ただし、辺の重みが負の値を含む場合はこの性質が崩れるため、ダイクストラのアルゴリズムは重みが非負(0以上)の場合に限られる、という制約も知られている)。
### 現代の応用
最短路問題とダイクストラのアルゴリズムは、カーナビ・地図アプリの経路探索(BOOK-0070・BOOK-0119のネットワーク領域とも接続する)、SNSにおける「友達の友達」を辿る繋がりの近さの計算、鉄道や航空路線の乗り換え案内など、現代のネットワーク社会を支える最も基本的な計算技法の一つになっている。
### 休憩所
最短路問題は重み付きグラフで辺の重みの合計が最小の経路を求める問題。ダイクストラは1956年にこれを解くアルゴリズムを考案(発表1959年)し、確定済み頂点から近い順に距離を確定させていく手順で、非負の重みを持つグラフの最短路を効率的に求める。
---
## 第十六章 計算複雑性との接続 — ハミルトン閉路とNP完全性(水準六)
### すべての頂点をちょうど1回ずつ訪れる経路
前巻で扱った一筆書き(すべての「辺」をちょうど1回ずつ通る経路、オイラー路と呼ばれる)とよく似ているが、実は難しさの質がまるで違う問題がある。**ハミルトン閉路(水準六: グラフのすべての「頂点」をちょうど1回ずつ訪れて出発点に戻る経路)**を求める問題だ。
一筆書き(オイラー路)が「奇数次数の頂点が0個か2個か」という単純な条件だけで存在の有無を判定できたのに対し、ハミルトン閉路が存在するかどうかを効率よく判定する一般的な方法は、2026年現在も見つかっていない。この違いは、離散数学が現代のコンピュータ科学と接続する重要な地点の一つになっている。
### NP完全性という分類
計算複雑性理論(計算にどれだけの手間がかかるかを分類する理論)では、「答えが与えられればすぐに正しいか確認できるが、答えを一から探し出すのは効率的な方法が知られていない」という性質を持つ問題の集まりを**NP完全問題(水準六: 答えの検証は効率的にできるが、答えを求める効率的な一般手順が知られていない〈かつ、同じ困難さを持つと理論的に示されている〉問題の分類)**と呼ぶ。
「ハミルトン閉路が存在するか」という判定問題は、このNP完全問題の一つであることが知られている。この分類の枠組みを整えたのが、スティーブン・クック(1971年)とリチャード・カープ(1972年)の研究である。クックは「ある種の論理式が充足可能かどうかを判定する問題(充足可能性問題)」がNP完全問題の中でも基礎的な位置を占めることを示し、カープはそこからハミルトン閉路を含む多数の重要な問題が、互いに変換し合える(ある問題が解ければ別の問題も解ける、という関係にある)NP完全問題であることを示した。
### なぜこれが重要なのか
もしハミルトン閉路問題を効率的に解く一般手順が発見されれば、NP完全問題は互いに変換し合える関係にあるため、**理論上は他のすべてのNP完全問題も一気に効率的に解けるようになる**。これは現代の計算機科学における最大級の未解決問題(「P対NP問題」)に直結しており、2026年現在も解決されていない。**この点は未確定の事実として明記しておく。**
### 休憩所
ハミルトン閉路(すべての頂点を1回ずつ訪れて戻る経路)を求める問題は、一筆書き(オイラー路)とは対照的に、効率的な一般判定法が知られていないNP完全問題である。この分類はクック(1971年)とカープ(1972年)の研究で整えられた。NP完全問題が効率的に解けるかどうか(P対NP問題)は2026年現在も未解決である。
---
## 第十七章 現代の応用 — SNS・地図・割当問題(水準五)
### SNSのネットワーク
現代のSNSは、ユーザーを頂点、「友達関係」や「フォロー関係」を辺としたグラフとして解析されている。第十五章の最短路の考え方は「知り合いを何人介せば繋がるか」の計算に、第十四章の彩色に近い発想は「興味の近いユーザーのグループ分け」に応用される。ラムゼー理論(第十一章)の「大きな集団には必ず秩序が現れる」という洞察は、SNS上で自然発生する派閥や共通話題のグループの理論的裏付けにもなる。
### 地図とカーナビ
第十五章のダイクストラのアルゴリズムは、カーナビ・地図アプリの経路探索エンジンの根幹技法であり、実際の道路網では渋滞状況を重みに反映させる改良が積み重ねられている。
### 割当問題
第十三章のホールの結婚定理が保証する「過不足のない割り当て」の考え方は、求人マッチング、大学の研究室配属、病院の研修医配属決定(「安定マッチング」と呼ばれる、ホールの定理と関係の深い理論が各国で運用されている)など、資源配分の随所で活躍している。
### 休憩所
グラフ理論・数え上げ・マッチング理論は、SNSのネットワーク解析、カーナビの経路探索、求人・研修医配属などの割当問題として、現代社会の随所で実際に稼働している。
---
## §16.21 ノウハウ — 数え上げを間違えない三つの実践解
離散数学の数え上げ問題(第十二章)は、一見単純に見えて「重複して数えてしまう」「数え漏らす」という失敗が起きやすい。ここでは、数え上げを間違えないための三つの実践解を紹介する。
### 実践解1 — 小さい場合を全列挙して規則を見る
**材料**: 紙とペン(あるいはテキストエディタ)、対象を小さいサイズ(n=1,2,3程度)に絞ったときの具体例。
**工程**: いきなり一般のnで公式を立てようとせず、まずn=1、n=2、n=3程度の小さい場合について、答えを実際にすべて書き出す(全列挙する)。第十二章のカタラン数C3の検算10で、3組の括弧の正しい並べ方を`((()))`から`()()()`まで実際に5通りすべて書き出したのがこの手法にあたる。書き出した具体例の中に、増え方の規則(たとえば「1つ前の答えの2倍になっている」「1つ前と2つ前の和になっている」など)が見えてくることが多い。
**なぜ効くか**: 人間の直感は、抽象的な式よりも具体的に並んだ実例のほうが規則を見つけやすいようにできている。前巻(BOOK-0077第七章)のハノイの塔やフィボナッチ数列の漸化式も、小さいnの実例(円盤1枚・2枚・3枚の手数)を並べたところから規則が見えてきた。全列挙は一見遠回りに見えて、間違った公式を早合点するリスクを大きく減らす、最も確実な第一歩になる。
**限界**: nが大きくなると全列挙自体が現実的でなくなる(たとえばn=10の場合分けを手作業で書き出すのは非現実的)。全列挙はあくまで「規則を見つけるための下調べ」であり、規則が見えたら一般の式(漸化式や閉じた公式)に翻訳する作業が別途必要になる。また、小さいnだけでは規則を誤認するリスクもゼロではない(n=1,2,3だけでは偶然一致して見える規則が、n=4以降で崩れる場合もありうる)。
### 実践解2 — 対称性で割る(重複数え防止)
**材料**: 数えようとしている対象の「並べ方」と「選び方」の違いを意識する視点。
**工程**: 前巻(BOOK-0077第二章)の組合せの技法を思い出そう。「5人から3人を選んで並べる」順列は60通りだが、「同じ3人の組」が`3!=6`通りずつ重複して数えられているため、60を6で割って組合せ10通りを得た。この「重複して数えている分の対称性(何通りの並べ替えが『同じもの』とみなされるか)を数え、その数で割る」という操作を、より複雑な数え上げでも意識的に適用する。第十二章のカタラン数の公式`C_n = C(2n,n)/(n+1)`の`÷(n+1)`の部分も、この対称性による調整の一種である。
**なぜ効くか**: 「同じものを区別して数えてしまう」ミスは、数え上げの失敗の中でも最も頻発するパターンだ。対称性(何通りの見かけ上の違いが、実は『同じもの』とみなされるべきか)を先に見極めてから割り算で調整することで、重複を機械的かつ確実に除去できる。第十二章の包除原理も、見方を変えれば「重なり合う部分を余分に数えた分を、対称性ならぬ『重なりの回数』に応じて引く」という、同じ発想の親戚にあたる。
**限界**: 対称性の度合い(何通りが『同じ』とみなされるか)を正しく見極めること自体が難しい場合がある。すべての要素が完全に区別できない特殊なケース(たとえば同じ色の玉が複数ある場合)では、単純に`n!`で割るだけでは不十分で、より丁寧な場合分けが必要になることもある。
### 実践解3 — 漸化式を立てて表で積み上げる
**材料**: 「n番目の答えを、n未満の答えを使って表せないか」という視点、そして答えを書き溜める表(あるいはスプレッドシート)。
**工程**: 前巻(BOOK-0077第七章)のハノイの塔・フィボナッチ数列と同じ要領で、「今考えている問題の答え(n番目の項)は、1つ前・2つ前……の答えを使って表せないか」を考える。表せそうであれば、小さいnから順に表に書き込んでいき(`n=1`の答え、`n=2`の答え、……)、大きいnの答えを、表にすでに書き込んだ小さいnの答えを参照しながら機械的に積み上げていく。
**なぜ効くか**: 漸化式(BOOK-0077第七章)は、複雑な問題を「1段階前の状態との関係」という、はるかに単純な関係式に分解してくれる。表に沿って一段ずつ積み上げていく作業は、一気に大きなnの答えを求めようとするよりも間違いが起きにくく、また第十六章で見た「答えの検証は簡単だが、答えを求めるのは難しい」という計算複雑性の発想とも相性がよい——表を使えば、途中経過(小さいnの答え)がすべて記録として残るため、どこかで計算違いがあっても遡って検証しやすい。
**限界**: そもそも漸化式が見つからない(n番目の答えを、それより小さいnの答えだけで表現する関係が存在しない、あるいは非常に複雑になる)問題も存在する。また、表を使う方法はnが極端に大きくなると、表自体が膨大になり手に負えなくなる場合がある(前巻で見たハノイの塔の`T(n)=2ⁿ−1`のように、指数的に増える量を扱う場合は特に、表を最後まで書き切ること自体が非現実的になりうる)。
### 三つの実践解の関係
この三つは独立した技ではなく、実際には組み合わせて使うことが多い。まず実践解1(小さい場合を全列挙)で規則の当たりをつけ、実践解2(対称性で割る)で重複除去の式を整え、実践解3(漸化式で積み上げる)でnが大きい場合まで機械的に答えを伸ばす——この三段構えが、離散数学の数え上げ問題における最も信頼できる王道の手順だと言える。
---
## 次への一歩 — 本巻を終えて
本巻(第2巻・水準五〜六)では、平面グラフとオイラーの公式、クラトフスキの定理、四色定理の証明の中身、ラムゼー理論、数え上げの高度な技法(生成関数・カタラン数・包除原理)、ホールの結婚定理、グラフ彩色の応用、最短路問題、そして計算複雑性(NP完全性)との接続までを歩いた。
前巻の入口で見た「数直線には隙間がある」という素朴な観察から出発した離散数学は、今や現代社会のネットワーク(SNS・地図・通信)を支える理論的土台であり、さらにコンピュータ科学における最大級の未解決問題(P対NP問題)にまで地続きになっていることを見届けた。数え上げ・鳩の巣原理・グラフ理論というシンプルな道具立てが、これほど広く深い応用を持つという事実こそ、離散数学という分野の懐の深さを物語っている。
情報科学の分野(BOOK-0066・BOOK-0116のアルゴリズム、BOOK-0070・BOOK-0119のネットワーク)では、本巻で見たグラフ理論や計算複雑性の考え方が、より具体的な計算手順の設計・解析として直接活用されていく。また、集合と論理(BOOK-0075)や確率論(BOOK-0083)とも、離散数学は多くの概念を共有している。
---
## 章末図 — 平面グラフとラムゼー理論(ASCII)
```
[立方体の平面グラフ・オイラーの公式(第八章)]
頂点8・辺12・面6 → V-E+F = 8-12+6 = 2
[K5(完全グラフ・第九章)辺数10本]
1
/ | \ \
2--+--3 \
\ | / \ /
4----5
(すべての頂点対が辺で直結。平面に交差なく描けない)
[ラムゼー数R(3,3)=6の骨格(第十一章)]
Aさんに注目 → 残り5人を「知合い/他人」で分類
→ 鳩の巣原理で必ずどちらかが3人以上
→ その3人の中に知合いの組があれば「知合い3人組」確定
→ なければその3人自体が「他人3人組」
```
---
## 出典・系譜(§16.5準拠・パブリックドメイン/確立した史実)
- レオンハルト・オイラー(1707年 - 1783年)によるオイラーの公式(V−E+F=2、平面グラフに関する法則) — グラフ理論の基礎定理として広く確立している。
- カジミェシュ・クラトフスキ(1896年 - 1980年、ポーランドの数学者)によるクラトフスキの定理(1930年発表) — 平面グラフの判定条件として確立している古典的定理。
- ケネス・アッペル、ヴォルフガング・ハーケンによる四色定理の証明(1976年発表)の詳細(還元・可約配置・論争の内容)は、前巻に続き史実として明記し、証明の検証をめぐる論争があったこと自体を確立した史実として扱う。
- フランク・ラムゼー(1903年 - 1930年、イギリスの数学者)にちなむラムゼー理論、およびR(3,3)=6という値 — 数学的に確立した結果。R(5,5)以上の大きなラムゼー数が2026年現在未確定であることも確立した事実として明記する。「宇宙人が侵略してきたら」という逸話は、あくまで比喩的なジョークとして紹介し、学術的主張と混同しないよう明記する。
- フィリップ・ホール(1904年 - 1982年、イギリスの数学者)によるホールの結婚定理(1935年発表) — マッチング理論の基礎定理として確立している。
- エドガー・ダイクストラ(1930年 - 2002年、オランダの計算機科学者)によるダイクストラのアルゴリズム(1956年考案、1959年発表) — 最短路問題の基礎アルゴリズムとして確立している。
- スティーブン・クック(1971年発表)、リチャード・カープ(1972年発表)によるNP完全性の理論的枠組み — 計算複雑性理論の基礎として確立している。P対NP問題が2026年現在未解決であることも確立した事実として明記する。
- カタラン数(ウジェーヌ・カタラン、1814年 - 1894年、ベルギーの数学者にちなむ)、包除原理、生成関数は、特定の一人の発見に限定されない、数学史を通じて確立してきた基礎技法として扱う。
本文は外部サイトの文章を転載せず、確立した数学的知識・史実から自分の言葉で構成した。
## 用語集(水準つき)
平面グラフ・面(五)/クラトフスキの定理(六)/ラムゼー数(六)/生成関数・カタラン数・包除原理(五)/マッチング・ホールの結婚定理(五)/彩色数(五)/最短路問題(五)/ハミルトン閉路・NP完全問題(六)。
## 相互リンク
- BOOK-0077(数学派生・離散数学 第1巻 — 本巻の前提。数え上げ・鳩の巣原理・グラフ理論誕生・木構造・彩色問題入口・漸化式入口)
- BOOK-0066(情報派生・アルゴリズム 第1巻 — 計算手順の基礎)
- BOOK-0116(情報派生・アルゴリズム 第2巻 — グラフアルゴリズム・計算複雑性の接続先)
- BOOK-0070(情報派生・ネットワーク 第1巻 — 通信網の基礎構造)
- BOOK-0119(情報派生・ネットワーク 第2巻 — 最短路・経路探索の応用先)
- BOOK-0083(数学派生・確率論 第1巻 — ラムゼー理論・数え上げと隣接する確率的発想)
- BOOK-0075(数学派生・集合と論理 第1巻 — NP完全性・充足可能性問題の論理的基盤)
# BOOK-0128 数学派生・離散数学 — 繋がりと数え上げの奥地(第2巻)