グラフ (離散数学)
数学のグラフ理論におけるグラフ(英: graph)とは数学的構造の一つ。対象の集合で、対象の一部が相互に何らかの脈絡で「関係している」ようなものをいう。ここで対象とは頂点(節点やノードとも)と呼ばれる抽象物であり、互いに関係のある頂点の対は辺(枝やエッジとも)と呼ばれる。一般的に、グラフは点または丸で表した頂点の集合に直線または曲線で辺を描き加えたダイアグラムで表現される。グラフは離散数学の研究対象の一つである。
辺には無向と有向の場合がある。例えば頂点をパーティ参加者として、2人が握手するとその間に辺が結ばれるとする場合、握手はお互い対等で行うものなので無向な辺といえる。対照的に、お金の貸し借り関係を辺とした場合、どちらか一方にのみ返済義務があるので有向な辺といえる。前者をグラフにしたものは無向グラフ (undirected graph) と呼ばれ、後者のグラフは有向グラフ (directed graph) と呼ばれる。
グラフはグラフ理論における基本的な研究対象である。「グラフ」という言葉は、1878年にジェームズ・ジョセフ・シルベスターによってこの意味で最初に使用された。
有向単純グラフに対しては E {\displaystyle E} の定義を E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } {\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\}} と修正し、有向多重グラフに対しては φ {\displaystyle \phi } の定義を φ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } {\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\}} と修正することになる。曖昧さを避けるため、これらの種類のグラフは厳密にそれぞれ「ループを許す単純有向グラフ (directed simple graph permitting loops)」そして「ループを許す多重有向グラフ(またはクイバー)」と呼ばれる場合もある。
ループを許す単純有向グラフ G {\displaystyle G} において、辺は G {\displaystyle G} の頂点に関する自己関係を成す。これを ∼ {\displaystyle \sim } と表し、 G {\displaystyle G} の「隣接関係」と呼ぶ。具体的には、各辺 ( x , y ) {\displaystyle (x,y)} について、その端点 x {\displaystyle x} と y {\displaystyle y} は互いに「隣接する」と言い、 x ∼ y {\displaystyle x\sim y} と表記される。