グラフ (離散数学)
ただし、多くの設問では頂点を識別不能として扱う方が都合が良い(もちろん、頂点はグラフ自体の属性によって、例えば接続辺の数などで、依然として識別できる場合もある)。同じことが辺にも適用されるため、ラベル付けされた辺を持つグラフは「ラベル付き辺を持つ」と呼ばれる。辺または頂点にラベルが与えられているグラフは「ラベル付き」と呼ばれるのが一般的である。したがって、頂点にも辺にも区別がないグラフを「ラベルなし (unlabeled)」と呼ぶ。
全てのグラフの圏はコンマ圏( S e t ↓ D {\displaystyle \mathbf {Set} \downarrow D} )である。ここで D : S e t → S e t {\displaystyle D:\mathbf {Set} \rightarrow \mathbf {Set} } は、集合 s {\displaystyle s} を s × s {\displaystyle s\times s} に対応付ける関手である。
一般に、頂点 V の集合は有限集合と想定されており、これはまた辺の集合も有限集合だということも意味する。時には「無限グラフ (Infinite graph) 」が考慮されることもあるが、殆どの場合は特別な種類の二項関係だと見なされる、というのも有限グラフで得られた結果の大部分が無限のケースに拡張できなかったり、だいぶ異なる証明を必要とするためである。
空グラフとは、頂点の集合が空である(したがって辺の集合も空である)グラフをいう。頂点の数 |V|をグラフの「位数」といい、辺の数 |E|をグラフの「サイズ」という。ただし、アルゴリズムの計算複雑性を表現するなど一部の文脈では、サイズが |V| + |E|である(こうしないと、空ではないグラフのサイズが0となりえてしまう)。頂点の次数とは頂点に接続する辺の数のことで、ループ付きグラフの場合ループは2回カウントされる。
位数 n のグラフにおける、各頂点の最大次数は n − 1(ループが許される場合は n )、辺の最大数は n(n − 1)/2(ループが許される場合は n(n + 1)/2)となる。
グラフの辺は「隣接関係」と呼ばれる頂点間の対称関係を定義する。