グラフの定義
まずはグラフを定義する。
有限集合との部分集合の族の対をハイパーグラフ (hypergraph)と呼ぶ。
が異なる個の元からなるの部分集合の族のとき、 を-ハイパーグラフという。特にが異なる元からなるの部分集合の族のとき、を単純グラフと呼ぶ。
の異なる 個の要素全体のなす集合を によりあらわす。-ハイパーグラフは、 となる、対 のことであり、グラフは、 となる、対 のことである。
以下では単純グラフのことをグラフ (graph)と呼ぶ。
グラフの集合を頂点集合、集合を辺集合と呼びそれぞれ, と書く。
の元を頂点 (vertex)、 の元を辺 (edge)と呼ぶ。
を単にあるいはと書く。
グラフの頂点の数 をオーダーあるいは位数 (order)、辺の数 をサイズあるいは大きさ (size)と呼ぶ。 のオーダーを によりあらわし、サイズを によりあらわす。
がオーダー のグラフであるとき、
となる。
頂点のとき、とは隣接する (adjacent)と言い、とは接続する (incident) と言う。また は と を結ぶ (join) と言い、頂点 , を辺 の端点 (endvertex) という。
グラフがかつを満たすとき、をのサブグラフあるいは部分グラフ (subgraph)と呼ぶ。
で、 が となる辺 をすべて含んでいるとき、 を により誘導される (induced, spanned) 部分グラフであるといい、 によりあらわす。
をどのように二つの集合に分割してもあるが存在してとなるとき、を連結グラフ (connected graph) と呼ぶ。
グラフ と グラフ が同型 (isomorphic) であるとは、頂点の集合の全単射 , が存在し、 となることをいう。グラフの構造について議論するときは、同型なグラフを同一視して議論することも多い。
代表的なグラフ
グラフ理論の議論をする際によく表れる代表的なグラフを定義する。
任意の頂点が隣接するグラフを完全グラフ (complete graph)と呼び、オーダーの完全グラフをと書く。 となる。
どの頂点も隣接しないグラフを空グラフ (empty graph)と呼び、オーダーの完全グラフをと書く。 となる。また、 である。
隣り合う頂点のみが隣接するように一列に並べられるグラフをパスグラフと呼び、オーダーのパスグラフをと書く。 の長さ (length)を と定める。パスグラフを単にパスあるいは道 (path) ともいう。
隣り合う頂点のみが隣接するように円周上に並べられるグラフをサイクルグラフと呼び、オーダーのサイクルグラフをと書く。 の長さを と定める。サイクルグラフを単にサイクルあるいは閉路 (cycle) ともいう。 を角形ともいう。
任意の頂点の次数が等しいグラフを正則グラフ (regular graph)と呼ぶ。