グラフ理論まとめ:定義・定理・アルゴリズムを一覧で整理【離散数学・競技プログラミング】
グラフ理論の全体像を一記事で.グラフの定義から平面性・彩色・マトロイドまで,離散数学と競技プログラミングに必要な定義・定理・アルゴリズムを体系的にまとめた.各トピックの依存関係図付き.
グラフの基礎定義と基本性質 ― グラフ理論の出発点を固める
無向グラフ・有向グラフの形式的定義から出発し,次数,握手の補題,完全グラフ$K_n$,完全二部グラフ$K_{m,n}$,グラフの同型を証明付きで解説する教科書スタイルの記事.
道と連結性 ― グラフの「つながり」を定式化する
道・径路・閉路の定義,連結成分,連結度$\kappa(G)$,切断点と橋,二部グラフ判定定理,Mengerの定理を証明する.
木と森 ― 最小限の連結構造
木の同値条件を証明し,$|E|=|V|-1$,根付き木,Cayleyの公式,全域木,最小全域木(Kruskal/Primのアルゴリズム)を扱う.
オイラーグラフとハミルトングラフ ― 道を巡る二つの古典問題
ケーニヒスベルクの橋問題からオイラーの定理,有向オイラーグラフ,ハミルトン路,OreとDiracの定理,NP完全性を解説する.
最短経路問題 ― 重み付きグラフを探索する
BFS最短路,Dijkstraの正当性証明,Bellman-Ford,負閉路検出,Warshall-Floyd,DAG上の最短路を体系的に扱う.
有向グラフとトポロジカルソート ― 順序構造としてのグラフ
強連結成分(SCC),TarjanおよびKosarajuのアルゴリズム,DAGとトポロジカルソート,半順序との対応,DAG上のDPを解説する.
マッチングと被覆 ― 最適な組み合わせを見つける
増加路,Bergeの定理,Hallの結婚定理,Königの定理,安定マッチング(Gale-Shapley),重み付きマッチングを証明付きで扱う.
ネットワークフロー ― グラフを流れるもの
フローネットワーク,最大フロー最小カット定理,Ford-Fulkerson法,Edmonds-Karp,Dinic,二部マッチングへの帰着を体系的に解説する.
平面グラフ ― 平面に描けるグラフの世界
オイラーの多面体公式$V-E+F=2$,$E \leq 3V-6$,$K_5$と$K_{3,3}$の非平面性,Kuratowskiの定理,双対グラフを証明する.
グラフ彩色 ― 何色あれば塗り分けられるか
彩色数$\chi(G)$,貪欲彩色,Brooksの定理,彩色多項式,辺彩色とVizingの定理,四色定理の概要を体系的に解説する.
代数的グラフ理論入門 ― 行列で読むグラフの構造
隣接行列,ラプラシアン$L=D-A$,行列木定理,固有値と連結性,$A^k$の$(i,j)$成分が道の数を表すことを証明する.
マトロイドと貪欲法 ― グラフの奥にある構造
マトロイドの公理,グラフ的マトロイド,貪欲法の最適性定理,MSTの再解釈,マトロイド交差を証明付きで解説する.