グラフ理論（グラフりろん、英: Graph theory）は、ノード（節点・頂点、点）の集合とエッジ（枝・辺、線）の集合で構成されるグラフに関する数学の理論である。

グラフ（データ構造）などの応用がある。
概要

グラフによって、様々なものの関連を表すことができる。6つの節点と7つの辺から成るグラフの一例

例えば、鉄道や路線バス等の路線図を考える際には、駅（節点）がどのように路線（辺）で結ばれているかが問題となる一方、線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。

したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。つまり、路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。

このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり[1]、グラフがもつ様々な性質を探求するのがグラフ理論である。

つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフ、または、ダイグラフという。矢印のないグラフは、無向グラフという。

グラフを表現するのに、図ではなく、隣接行列を用いることがある。無向グラフの隣接行列は、対称行列になる。例えば、上のグラフは、次の隣接行列で表現できる。 ( 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 ) {\displaystyle {\begin{pmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}
グラフの例詳細は「グラフ (離散数学)」を参照

日常的な問題や工学的問題の多くをグラフとして考えることができる。

路線図: 前節のとおり。

電気回路: 回路図を書く場合、実際のリード線どおりの形状に図を描いたりはしない。この場合も、「接点がどうつながっているか」だけが問題であって、「つながり方」を保ちつつできるだけ見やすい形に絵を描く。回路図は一種のグラフである。

WWWの構造: WWWにおけるウェブページの、ハイパーリンク・被リンク関係がなす構造は、有向グラフの一種である[2]。

起源

グラフ理論は、1736年に「ケーニヒスベルクの問題」と呼ばれるパズルに対してオイラーが解法を示した[3][4]のが起源のひとつとされる[5]。この問題は、一筆書きと深く関連している[6]。
形式的な定義
有向グラフ

集合 V, E と、E の元（げん、要素）に、二つの V を元の対で対応させる写像 f :   E → V × V {\displaystyle f\colon \ E\to V\times V}

の三つ組 G := ( f , V , E ) {\displaystyle G:=(f,V,E)}

を有向グラフという。V の元を G の頂点またはノード、E の元を G の辺または弧と呼ぶ。f(e) = (v,v) となる e ∈ E はループに対応し、f(a) = f(b) となる a, b ∈ E は多重辺に対応する。
無向グラフ

?(V) を V の冪集合とする。E の元に V の 部分集合を対応させる写像 g :   E → P ( V ) {\displaystyle g\colon \ E\to {\mathfrak {P}}(V)}

があって、E の任意の元 e について、e の像 g(e) の濃度が1または2であるとき、三つ組 G := ( g , V , E ) {\displaystyle G:=(g,V,E)}

を無向グラフという[7]。 V の元を G の頂点、E の元を G の辺と呼ぶ。g(e) の濃度が1となる e ∈ E はループに対応し、f(a) = f(b) となる a, b ∈ E は多重辺に対応する。

単純グラフに限って言えば、E を最初からある集合の部分集合と考え、写像を用いずにグラフを定義することもできる：有向グラフでは、E を V × V の部分集合、無向グラフでは、E を ?(V) の部分集合で、2つの元の集合だけからなるものとすればよい。
用語

以下では単にグラフといった時には無向グラフを指す。
頂点と辺

頂点の集合は V、辺の集合は E で表す。グラフ G が先に与えられている場合には、頂点集合を V(G)、辺集合を E(G) と表すこともある[8]。