グラフ

グラフの定義

まずはグラフを定義する。

有限集合$V$と$V$の部分集合の族$E$の対$G=(V,E)$をハイパーグラフ (hypergraph)と呼ぶ。

$E$が異なる$k$個の元からなる$V$の部分集合の族のとき、$G=(V, E)$ を$k$-ハイパーグラフという。特に$E$が異なる$2$元からなる$V$の部分集合の族のとき、$G=(V,E)$を単純グラフと呼ぶ。

$V$ の異なる $k$ 個の要素全体のなす集合を $[V]^k$ によりあらわす。$k$-ハイパーグラフは、$E\subset [V]^k$ となる、対 $(V, E)$ のことであり、グラフは、$E\subset [V]^2$ となる、対 $(V, E)$ のことである。

以下では単純グラフのことをグラフ (graph)と呼ぶ。

グラフ$G=(V,E)$の集合$V$を頂点集合、集合$E$を辺集合と呼びそれぞれ$V(G)$, $E(G)$と書く。

$V(G)$の元を頂点 (vertex)、 $E(G)$の元を辺 (edge)と呼ぶ。

$\set{u,v}\in E(G)$を単に$uv$あるいは$vu$と書く。

グラフ$G$の頂点の数 $\abs{V}$ をオーダーあるいは位数 (order)、辺の数 $\abs{E}$ をサイズあるいは大きさ (size)と呼ぶ。$G$ のオーダーを $\abs{G}$ によりあらわし、サイズを $e(G)$ によりあらわす。

$G=(V, E)$ がオーダー$n$ のグラフであるとき、
$$0\leq \abs{E}\leq \binom{n}{2}=\frac{n(n-1)}{2}$$
となる。

頂点$e=uv\in E(G)$のとき、$u$と$v$は隣接する (adjacent)と言い、$u$と$e$は接続する (incident) と言う。また $e$ は $u$ と $v$ を結ぶ (join) と言い、頂点 $u$, $v$ を辺 $e$ の端点 (endvertex) という。

グラフ$H$が$V(H)\subset V(G)$かつ$E(H)\subset E(G)$を満たすとき、$H$を$G$のサブグラフあるいは部分グラフ (subgraph)と呼ぶ。
$V(H)=V^\p\subset V$ で、$E(H)$ が $x, y\in V^\p$ となる辺 $xy\in E(G)$ をすべて含んでいるとき、$H$ を $V^\p$ により誘導される (induced, spanned) 部分グラフであるといい、$G[V^\p]$ によりあらわす。

$V(G)$をどのように二つの集合$X,Y$に分割してもある$x\in X,y\in Y$が存在して$xy\in E(G)$となるとき、$G$を連結グラフ (connected graph) と呼ぶ。

グラフ $G_1 = (V_1, E_1)$ と グラフ $G_2 = (V_2, E_2)$ が同型 (isomorphic) であるとは、頂点の集合の全単射 $\psi\colon V_1\to V_2$, $x\mapsto \psi_x$ が存在し、$xy\in E_1\Longleftrightarrow \psi_x\psi_y\in E_2$ となることをいう。グラフの構造について議論するときは、同型なグラフを同一視して議論することも多い。

代表的なグラフ

グラフ理論の議論をする際によく表れる代表的なグラフを定義する。

任意の頂点が隣接するグラフを完全グラフ (complete graph)と呼び、オーダー$n$の完全グラフを$K_n$と書く。$\displaystyle e(K_n)=\binom{n}{2}=\frac{n(n-1)}{2}$ となる。

どの頂点も隣接しないグラフを空グラフ (empty graph)と呼び、オーダー$n$の完全グラフを$E_n$と書く。$e(E_n)=0$ となる。また、$E_1=K_1$ である。

隣り合う頂点のみが隣接するように一列に並べられるグラフをパスグラフと呼び、オーダー$n+1$のパスグラフを$P_n$と書く。$P_n$ の長さ (length)を $n$ と定める。パスグラフを単にパスあるいは道 (path) ともいう。

隣り合う頂点のみが隣接するように円周上に並べられるグラフをサイクルグラフと呼び、オーダー$n$のサイクルグラフを$C_n$と書く。$C_n$ の長さを $n$ と定める。サイクルグラフを単にサイクルあるいは閉路 (cycle) ともいう。$C_n$ を$n$角形ともいう。

任意の頂点の次数が等しいグラフを正則グラフ (regular graph)と呼ぶ。