グラフとは結局なにか ― 「関係」を可視化する道具
ケーニヒスベルクの橋からSNS,依存関係,スケジューリングまで,あらゆる「つながり」がグラフに帰着します.無向・有向・重み付きグラフの直感的な意味と,なぜこの抽象化が強力なのかを解説します.
なぜBFSは最短路を見つけるのか ― 波紋のアナロジー
BFS が最短路を見つける理由を「波紋」の比喩で直感的に理解します.DFS が最短路を保証しない反例,Dijkstra 法が「重み付きの波紋」である理由も解説します.
木はなぜ特別なのか ― 最小限の連結構造の美学
木の7つの等価条件がすべて「冗長性ゼロの連結構造」を別の角度から述べていることを直感的に解説します.辺を1本足せば閉路ができ,1本引けば非連結になる ― この極限的な美しさの正体に迫ります.
貪欲法はなぜ木で上手くいくのか ― マトロイドが教えてくれること
Kruskal 法の貪欲戦略がなぜ最適な最小全域木を与えるのか,マトロイドの交換公理を通じて直感的に理解します.ナップサック問題での貪欲法の失敗との対比も解説します.
オイラーとハミルトンの断絶 ― 「全辺」と「全頂点」はなぜこうも違うのか
すべての辺を1回ずつ通る(オイラー回路)は次数の偶奇で判定できるのに,すべての頂点を1回ずつ通る(ハミルトン閉路)は NP 完全です.「辺」と「頂点」でなぜこれほど計算量が違うのかを直感的に解説します.
最大フロー最小カット定理が言っていること ― 双対性の直感
最大フローと最小カットが等しいという驚くべき定理を,「最も弱い部分がボトルネック」という直感から解説します.増加路の考え方,LP 双対性とのつながり,道路やインターネットの帯域幅の実例も紹介します.
二部グラフの魔法 ― なぜ二部グラフではすべてが上手くいくのか
奇数閉路がないだけで,マッチング・彩色・被覆がすべて効率的に解ける ― 二部グラフの驚くべき性質を解説します.König の定理の直感と,競技プログラミングでの帰着パターンも紹介します.
グラフの「かたち」は何を決めるのか ― 平面性から四色定理へ
平面グラフは辺数が $3V - 6$ 以下に抑えられ,一般のグラフで困難な問題も効率的に解けます.オイラーの公式 $V - E + F = 2$,Kuratowski の定理,そして四色定理の哲学的意味を直感的に解説します.