この項目「グラフ (離散数学)」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en:Graph (discrete mathematics)14:39, 26 March 2021）
修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2021年3月）
.mw-parser-output .hatnote{margin:0.5em 0;padding:3px 2em;background-color:transparent;border-bottom:1px solid #a2a9b1;font-size:90%}

この項目では、グラフ理論の主題である辺で連結された頂点集合について説明しています。関数を視覚化するグラフについては「グラフ (関数)」をご覧ください。
頂点6つと辺7つから成るグラフの例

数学のグラフ理論におけるグラフ（英: graph）とは数学的構造の一つ。対象の集合で、対象の一部が相互に何らかの脈絡で「関係している」ようなものをいう。ここで対象とは頂点（節点やノードとも）と呼ばれる抽象物であり、互いに関係のある頂点の対は辺（枝やエッジとも）と呼ばれる[1]。一般的に、グラフは点または丸で表した頂点の集合に直線または曲線で辺を描き加えたダイアグラムで表現される。グラフは離散数学の研究対象の一つである。

辺には無向と有向の場合がある。例えば頂点をパーティ参加者として、2人が握手するとその間に辺が結ばれるとする場合、握手はお互い対等で行うものなので無向な辺といえる。対照的に、お金の貸し借り関係を辺とした場合、どちらか一方にのみ返済義務があるので有向な辺といえる。前者をグラフにしたものは無向グラフ (undirected graph) と呼ばれ、後者のグラフは有向グラフ (directed graph) と呼ばれる。

グラフはグラフ理論における基本的な研究対象である。「グラフ」という言葉は、1878年にジェームズ・ジョセフ・シルベスターによってこの意味で最初に使用された[2][3]。
定義

グラフ理論における定義はさまざまである。以下、グラフや関連する数学的構造の定義で基本的なものを幾つか挙げる。
グラフ頂点3つと辺3つから成るグラフ（無向グラフ）

グラフ（有向グラフと区別して「無向グラフ」とか、多重グラフと区別して「単純グラフ」とも呼ばれたりもする）[4][5]とは順序対 G = (V, E) である。ここで V は頂点 (vertex) と呼ばれる元の集合、E は頂点の対の集合でありその元は辺 (edge) と呼ばれる。

辺 {x, y} に含まれる頂点 xとy は、その辺の「端点」と呼ばれる。辺は頂点 x と y を「結び (join)」、x や y に「接続する (incident)」と言い表す。頂点がいかなる辺にも含まれないこともあり、その場合は他のどの頂点とも結ばれていない。多重グラフの例。赤が多重辺で、青がループ

頂点をそれ自身と結ぶ辺である「ループ（自己ループとも）」を許すグラフもある[6]。このように一般化されたグラフは「ループ付きグラフ (graphs with loops)」と呼ばれる。文脈からループを許すことが自明な場合は単にグラフと呼んだりもする。

「多重グラフ (multigraph) 」とは、2つの頂点間に複数の辺がある「多重辺」を許すように一般化したグラフである[7]。一部のテキストでは、多重グラフのことを単にグラフと呼んでいたりもする[8][9]。多重辺を許すにあたり、上述の辺に関する定義を頂点対の（通常の）集合ではなく、頂点対の多重集合に変更する必要がある。

一般に、頂点 V の集合は有限集合と想定されており、これはまた辺の集合も有限集合だということも意味する。時には「無限グラフ (Infinite graph) 」が考慮されることもあるが、殆どの場合は特別な種類の二項関係だと見なされる、というのも有限グラフで得られた結果の大部分が無限のケースに拡張できなかったり、だいぶ異なる証明を必要とするためである。

空グラフとは、頂点の集合が空である（したがって辺の集合も空である）グラフをいう。頂点の数 |V|をグラフの「位数」といい、辺の数 |E|をグラフの「サイズ」という[10]。ただし、アルゴリズムの計算複雑性を表現するなど一部の文脈では、サイズが |V| + |E|である（こうしないと、空ではないグラフのサイズが0となりえてしまう）。頂点の次数とは頂点に接続する辺の数のことで、ループ付きグラフの場合ループは2回カウントされる[1]。

位数 n のグラフにおける、各頂点の最大次数は n − 1（ループが許される場合は n ）、辺の最大数は n(n − 1)/2（ループが許される場合は n(n + 1)/2）となる。

グラフの辺は「隣接関係」と呼ばれる頂点間の対称関係を定義する。具体的には、{x, y} が辺であれば、2つの頂点 x と y は「隣接している (adjacent)」という。