TL;DR
要素を点（頂点、ノード）、要素どうしの関係を線（辺、エッジ）で表したグラフの性質を研究する数学の分野。1736 年に Euler が「ケーニヒスベルクの七つの橋」の問題を解いたことが、起源の 1 つとされる。
なぜ必要か
路線図や回路図では、位置や形よりも「どこがどこにつながっているか」が大事な情報になる。グラフとして抽象化すると、つながり方だけに注目して問題を扱える。
仕組み
グラフは、頂点の集合と辺の集合の組として定義される。辺に向きがあるものを有向グラフ、ないものを無向グラフと呼ぶ。グラフは隣接行列でも表せ、無向グラフの隣接行列は対称行列になる。道路網のように、辺に距離や費用などの重みを持たせたものを重み付きグラフと呼ぶ。
例
- 計算機科学: Web ページのリンク構造、デッドロックの検出、ファイルシステム
- 化学: 原子を頂点、結合を辺として分子の構造を表す
- 社会科学: 人間関係を分析するソーシャルネットワーク分析
- 重み付きグラフを使った経路探索