グラフ理論
グラフ理論（グラフりろん、）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。
グラフによって、様々なものの関連を表すことができる。
例えば、鉄道や路線バス等の路線図を考える際には、駅（ノード）がどのように路線（エッジ）で結ばれているかが問題となる。
線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。
したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。
路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。
このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり、
グラフがもつ様々な性質を探求するのがグラフ理論である。
つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフまたは、ダイグラフという。矢印のないグラフは、無向グラフという。
グラフを表現するのに、図ではなく、隣接行列を用いることがある。無向グラフの隣接行列は、対称行列になる。例えば、上のグラフは、次の隣接行列で表現できる。
日常的な問題や工学的問題の多くをグラフとして考えることができる。
グラフ理論は、1736年に「ケーニヒスベルクの問題」と呼ばれるパズルに対してオイラーが解法を示したのが起源のひとつとされる。この問題は、一筆書きと深く関連している。
集合 "V" , "E" と、"E" の元（げん、要素）に、二つの "V" を元の対で対応させる写像
の三つ組
を有向グラフという。"V" の元を "G" の頂点またはノード、"E" の元を "G" の辺または弧と呼ぶ。
P("V") を "V" の冪集合とする。"E" の元に "V" の 部分集合を対応させる写像
があって、"E" の任意の元 "e" の像が "g"("e") = {"v", "v"} のようにちょうど二つの元の集合になっているとする。このとき、三つ組
を無向グラフという。"V" の元を "G" の頂点、"E" の元を "G" の辺と呼ぶ。"g" の値が常に"k" > 2個の元の集合となっているとき、k-ハイパーグラフという。
"E" を最初からある集合の部分集合と考えれば、写像を用いずにグラフを定義することもできる：有向グラフでは、"E" を "V"×"V" の部分集合、無向グラフでは、"E" を P("V") の部分集合で、二つの元の集合だけからなるものとすればよい。
以下では単にグラフといった時には無向グラフを指す。
頂点の集合は formula_6、辺の集合は formula_7 で表す。
グラフ formula_8 が先に与えられている場合には、頂点集合を formula_9、辺集合を formula_10 と表すこともある。
数学以外の分野では、頂点を節点、辺を枝と呼ぶことが多い。辺を弧やリンクと呼ぶこともある。
グラフの辺に重み（コスト）が付いているグラフを、重み付きグラフと呼ぶ。乗換案内図の場合、駅間の所要時間が「重み」にあたる。重み付きグラフはネットワークとも呼ばれる（フローネットワーク, ベイジアンネットワーク, ニューラルネットワークなど）。
辺 formula_11 の両端の点を端点といい、端点は 辺 formula_11 に接合 (または、接続) しているという。また、辺と辺がある頂点を共有しているとき、その辺どうしは隣接 しているという。
2頂点間(隣接している必要はない)を経由する辺数を長さと呼び、特に最短経路における辺数を距離と呼ぶ。グラフ "G" の最大頂点間距離を直径と呼び、diam("G") と表す。
ある辺の両端点が等しいとき、ループ（自己ループ）という。また、2 頂点間に複数の辺があるとき、多重辺という。ループも多重辺も含まないグラフのことを単純グラフといい、ループや多重辺を含むグラフのことを多重グラフという。
二つのグラフ formula_8 と formula_14 について、formula_15 の頂点集合と辺集合が共に formula_8 の頂点集合と辺集合の部分集合になっているとき、formula_14は formula_8 の部分グラフである、または formula_8 は formula_14 の拡大グラフであるといい、formula_21 と表す。特に、formula_8とformula_14の頂点集合が等しいとき、formula_14はformula_8の全域部分グラフであるという。また、formula_8 の頂点集合 formula_6 の部分集合 formula_28 を取り出して、両端点が formula_28 に属する全ての辺を辺集合とする "G" の部分グラフ formula_30 を、誘導部分グラフという。グラフ formula_8 からある辺 formula_11 を取り除き、その辺の両端点を一つの頂点にまとめることを（辺の）縮約といい、縮約の結果得られるグラフを formula_33 と表す。
なお、誘導部分グラフの「誘導」はinducedの訳語である。induceの訳としてはこの「誘導する」の他に「生成する」がある。このため、誘導部分グラフのことを生成部分グラフということもある。一方、生成部分グラフは全域部分グラフのことを指すこともある。このため、生成部分グラフという語を使う際は、混乱がないか気を付ける必要がある。
頂点 formula_34 に接続する枝の数を次数といい、formula_35 で表す。
有向グラフにおいては、formula_34 に入ってくる辺数のことを入次数、formula_34 から出て行く辺数のことを出次数という。すべての頂点が同数の隣接点、つまり次数をもつグラフを正則グラフと呼ぶ。任意の頂点 formula_34 について、formula_39 が成り立つとき、"k" -正則という。"k" -正則なグラフのことを"k" -正則グラフという。グラフ formula_8 が持つ頂点の次数の最小値を formula_41、最大値を formula_42 で表す。また、次数 0 の頂点のことを孤立点という。
隣接している頂点同士をたどった formula_43 の系列を長さ "n" (≥ 0) の歩道（鎖・ウォーク）という。辺の重複を許さない歩道を路（小径・トレイル）という。頂点の重複を許さない場合、つまり、両端の2頂点の次数が1、それ以外のすべての頂点の次数が2であるグラフを、道（パス）、開いた歩道をパスという場合は単純パスという。また、始点と終点が同じ路のことを閉路（回路・循環 ・サーキット、サイクル）、始点と終点が同じ道（つまりformula_44という路でformula_45が相異なるもの）のことを閉道（サイクル）という。
任意の 2 頂点間に枝があるグラフのことを完全グラフ（完備グラフ）という
。formula_46 頂点の完全グラフは、formula_47 で表す。formula_48 は三角形と呼ばれる。また、完全グラフになる誘導部分グラフのことをクリークという。大きさ（サイズ） formula_46 のクリークを含むグラフは「"n"-クリークである」という。辺をもつグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また "n"-クリークであって、直径が "n" 未満となるグラフを "n"-クランという。
2022年から導入される新学習指導要領の数学C(公式配布されるのは2024年4月である)には「"図、表、統計グラフ、離散グラフ及び行列などを用いて、日常の事象や社会の事象などを数学的に表現し、考察すること。"」とあり、日本では初めてグラフ理論にかかわる分野が高校の数学教科書に掲載される予定である。