ノードの集合とエッジの集合で構成されるグラフの数理についての理論である、情報科学の一分野。1736年、「ケーニヒスベルクの問題」に対してオイラーが解法を示したのが起源とされる。
情報科学におけるグラフG
とは、頂点集合V
と辺集合E
から構成される。E
はV
の要素2つからなるタプル(ペア)である。E
の要素を辺(Edge)という。辺の方向を考慮する場合には、そのグラフは有向グラフと呼ばれ、そうでない場合は無向グラフと呼ばれる。
このような構造が与えられた時に、どのようなアルゴリズムで特定の情報を計算するか、がグラフ理論の取り扱う領域である。
具体例: ある有向グラフ G と、その頂点 v1 と v2 が与えられた時に、 v1 から v2 へ到達する最短経路を求めよ。(aka 最短経路問題) -> ダイクストラ法が一般的な解法(の一つ)