About: グラフ (離散数学)

数学のグラフ理論におけるグラフ（英: graph）とは数学的構造の一つ。対象の集合で、対象の一部が相互に何らかの脈絡で「関係している」ようなものをいう。ここで対象とは頂点（節点やノードとも）と呼ばれる抽象物であり、互いに関係のある頂点の対は辺（枝やエッジとも）と呼ばれる。一般的に、グラフは点または丸で表した頂点の集合に直線または曲線で辺を描き加えたダイアグラムで表現される。グラフは離散数学の研究対象の一つである。 辺には無向と有向の場合がある。例えば頂点をパーティ参加者として、2人が握手するとその間に辺が結ばれるとする場合、握手はお互い対等で行うものなので無向な辺といえる。対照的に、お金の貸し借り関係を辺とした場合、どちらか一方にのみ返済義務があるので有向な辺といえる。前者をグラフにしたものは無向グラフ (undirected graph) と呼ばれ、後者のグラフは有向グラフ (directed graph) と呼ばれる。 グラフはグラフ理論における基本的な研究対象である。「グラフ」という言葉は、1878年にジェームズ・ジョセフ・シルベスターによってこの意味で最初に使用された。