グラフ理論
最短経路問題
ハミルトン閉路問題
巡回セールスマン問題
中国人郵便配達問題
最小全域木問題
最大クリーク問題
頂点被覆問題
最大流最小カット定理
グラフ彩色問題 - 四色定理
ワーシャル-フロイド法 (Warshall-Floyd 問題)
次数直径問題
安定結婚問題
グラフ・マイナー定理(英語版)
グラフサンドウィッチ問題(英語版)
小石運動問題(英語版)
グラフ理論(グラフりろん、英: Graph theory)は、ノード(節点・頂点、点)の集合とエッジ(枝・辺、線)の集合で構成されるグラフに関する数学の理論である。
グラフ(データ構造)などの応用がある。
グラフ理論は化学および物理学において分子を研究するためにも使われる。凝縮系物理学では、シミュレーションした複雑な原子構造の3次元構造は、原子のトポロジーに関連したグラフ理論的性質に関する統計量を集めることによって定量的に研究することができる。また、ファインマンの計算のグラフと規則は、理解したい実験的数字と密接に関係した形式で量子場理論を要約する。化学では、グラフは分子についての自然な模型を作り、ここでは頂点が原子、辺が結合を表わす。このアプローチは分子構造の計算処理(分子エディタからデータベース探索まで)において特に使われる。統計物理学では、グラフは系の相互作用している部位間の局所的つながりや、こういった系における物理的過程のダイナミクスを表わすことができる。同様に、計算論的神経科学では、グラフは様々な認知過程を生じさせるために相互作用する脳領域間の機能的結合を表わすために使うことができる。ここでは、頂点が脳の異なる領域を表わし、辺がそれらの領域間の結合を表わす。グラフ理論は電気回路網の電気的モデリングにおいて重要な役割を果たす。ここで、重みはネットワーク構造の電気的性質を得るために有線部分の抵抗と関連付けられる。グラフは多孔質材料のミクロスケールチャネルを表わすらために使うこともできる。ここでは、頂点が孔を表わし、辺が孔間をつなぐより小さなチャネルを表わす。化学グラフ理論は分子をモデル化する手段として分子グラフを使用する。