グラフ理論（グラフりろん、英: 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]。

数学以外の分野では、頂点を節点、辺を枝と呼ぶことが多い。辺を弧やリンクと呼ぶこともある。
重み付きグラフ

グラフの辺に重み（コスト）が付いているグラフを、重み付きグラフと呼ぶ[9]。乗換案内図の場合、駅間の所要時間が「重み」にあたる。重み付きグラフはネットワークとも呼ばれる（フローネットワーク, ベイジアンネットワーク, ニューラルネットワークなど）。
接合と隣接

辺 e の両端の点を端点といい、端点は辺 e に接合（または接続）しているという。また、辺と辺がある頂点を共有しているとき、その辺どうしは隣接しているという[8]。
距離と直径

2頂点間（隣接している必要はない）を経由する辺数を長さと呼び、特に最短経路における辺数を距離と呼ぶ。グラフ G の最大頂点間距離を直径と呼び、diam(G) と表す[10]。
ループと多重グラフ

ある辺の両端点が等しいとき、ループ（自己ループ）という。また、2頂点間に複数の辺があるとき、多重辺という。ループも多重辺も含まないグラフのことを単純グラフといい、ループや多重辺を含むグラフのことを多重グラフという[11]。
部分グラフと拡大グラフ縮約の図示

2つのグラフ G と G' について、G' の頂点集合と辺集合が共に G の頂点集合と辺集合の部分集合になっているとき、G' は G の部分グラフである、または G は G' の拡大グラフであるといい、G' ⊂ G と表す[8]。特に、G と G' の頂点集合が等しいとき、G' は G の全域部分グラフであるという。また、G の頂点集合 V の部分集合 U を取り出して、両端点が U に属する全ての辺を辺集合とする G の部分グラフ G[U] を、誘導部分グラフという。グラフ G からある辺 e を取り除き、その辺の両端点を一つの頂点にまとめることを（辺の）縮約といい、縮約の結果得られるグラフを G/e と表す。

なお、誘導部分グラフの「誘導」はinducedの訳語である。induceの訳としてはこの「誘導する」の他に「生成する」がある[12][13]。このため、誘導部分グラフのことを生成部分グラフということもある[14]。一方、生成部分グラフは全域部分グラフのことを指すこともある。このため、生成部分グラフという語を使う際は、混乱がないか気を付ける必要がある。
次数と正則グラフ「次数 (グラフ理論)」も参照3-正則グラフの例

頂点 v に接続する枝の数を次数といい、d(v) で表す。有向グラフにおいては、v に入ってくる辺数のことを入次数、v から出て行く辺数のことを出次数という。