グラフ

頂点と辺からなる構造。 $G=(V,E)$

対象どうしの「つながり」を抽象化したもの。 道路網、通信網、分子構造、依存関係など、 つながりが本質の問題はすべてこれで表せる。

種類#

種類	特徴
無向 / 有向	辺に向きがあるか
重み付き	辺にコストがある
単純 / 多重	自己ループや多重辺を許すか
連結	どの 2 頂点も辿り着ける

表現#

表現	記憶量	隣接判定
隣接行列	$𝒪(V^2)$	$𝒪(1)$
隣接リスト	$𝒪(V+E)$	$𝒪(\mathrm{deg}v)$

疎なグラフでは隣接リスト、密なら隣接行列。

隣接行列は対称行列（無向の場合）なので、 固有値が実数になり、 スペクトルグラフ理論という分野が成立する。 グラフラプラシアンの固有値が連結性やクラスタ構造を教える。

難しさの分かれ目#

問題	計算量
最短経路	多項式時間（Dijkstra）
最小全域木	多項式時間
Max-Cut	NP 困難
TSP	NP 困難

見た目が似ていても難易度が大きく違う。

参考文献#

• Thomas H. Cormen et al. Introduction to Algorithms, 4th ed. MIT Press, 2022. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html