グラフ

グラフ（graph）、詳しくは単純無向グラフ（simple undirected graph）とは、集合 $V$ と $E\subset[V]^2$ の組 $G=(V,E)$ のことをいう。$V$ の元を $G$ の頂点（vertex）、$E$ の元を $G$ の辺（edge）といい、$V=V(G)$、$E=E(G)$ とも書く。辺 $\{u,v\}$ を $uv$ とも書く。$uv=vu$ である。
$|V|$ を $G$ の位数（order）といい $|G|$ とも書く。$|E|$ を $G$ の大きさ（size）といい $e(G)$ とも書く。位数が有限のグラフを有限グラフ、そうでないグラフを無限グラフという。頂点を持たないグラフ $(\emptyset,\emptyset)$ も許す。

$G=(V,E)$ をグラフとする。

1. 頂点 $u,v$ が隣接する（adjacent）とは $uv\in E$ となることをいう。このとき $u$ と $v$ は辺 $uv$ の端点（end）であるという。
2. 頂点 $v$ と辺 $e$ が接続する（incident）とは $v\in e$ となることをいう。
3. 頂点 $v$ の近傍（neighbourhood）とは、$v$ に隣接する頂点全体の集合 $N_G(v):=\{u\in V\mid uv\in E\}$ のことをいう。$N_G(v)$ の元を $v$ の隣接頂点という。
4. 2 本の辺が隣接するとは、共通の端点を持つことをいう。

$G=(V,E)$ をグラフとする。

1. $G$ の歩道（walk）とは、頂点の有限列 $v_0,v_1,\dots,v_\ell$（$\ell\ge0$）であって、各 $i=1,\dots,\ell$ について $v_{i-1}v_i\in E$ となるものをいう。$\ell$ をこの歩道の長さ（length）といい、歩道は $v_0$ と $v_\ell$ を結ぶという。$v_0$ を始点、$v_\ell$ を終点ともいう。$v_0=v_\ell$ のとき閉歩道（closed walk）という。
2. 辺 $v_0v_1,\ v_1v_2,\ \dots,\ v_{\ell-1}v_\ell$ が相異なる歩道を小道（trail）といい、閉歩道である小道を閉小道（circuit）という。
3. 頂点 $v_0,\dots,v_\ell$ が相異なる歩道を道（path）といい、$v_0,v_\ell$ をその端点という。長さ $0$ の道は 1 個の頂点だけからなる。
4. $G$ の閉路（cycle）とは、閉歩道 $v_0,v_1,\dots,v_\ell$（$v_\ell=v_0$）であって、$\ell\ge3$ かつ $v_1,\dots,v_\ell$ が相異なるものをいう。$\ell$ をこの閉路の長さといい、長さが奇数・偶数の閉路をそれぞれ奇閉路・偶閉路という。

グラフ $G=(V,E)$ が連結（connected）であるとは、$V\neq\emptyset$ であって、任意の 2 頂点 $u,v\in V$ に対し $u$ と $v$ を結ぶ道が存在することをいう。$V$ 上の関係「$u$ と $v$ を結ぶ道が存在する」は同値関係であり（prop-graph-connected-components）、その各同値類 $C$ に対し、$C$ の頂点と、両端点が $C$ に属する辺すべてからなるグラフ $G[C]:=(C,\ E\cap[C]^2)$ を $G$ の連結成分（connected component）という。

グラフ $G=(V,E)$ の補グラフ（complement）とは、$G$ で隣接していない頂点対をすべて辺で結んだグラフ $\overline{G}:=(V,\ [V]^2\setminus E)$ のことをいう。$G^c$ とも書く。
頂点集合が交わらない 2 つのグラフ $G$、$H$ に対し、$G\cup H:=(V(G)\cup V(H),\ E(G)\cup E(H))$ を $G$ と $H$ の非交和（disjoint union）といい、これに $V(G)$ の各頂点と $V(H)$ の各頂点を結ぶ辺をすべて加えたグラフ
$$G+H:=\bigl(V(G)\cup V(H),\ E(G)\cup E(H)\cup\{\{v,w\}\mid v\in V(G),\ w\in V(H)\}\bigr)$$
を $G$ と $H$ の結合（join）という。

グラフ $G=(V,E)$ から $G'=(V',E')$ への同型（isomorphism）とは、全単射 $f\colon V\to V'$ であって、任意の $u,v\in V$ について
$$uv\in E\iff f(u)f(v)\in E'$$
となるものをいう。同型が存在するとき $G$ と $G'$ は同型（isomorphic）であるといい、$G\cong G'$ と書く。

グラフの概念には次の変種がある。

1. 有向グラフ（directed graph, digraph）とは、集合 $V$ と順序対の集合 $A\subset V\times V$ の組 $D=(V,A)$ のことをいう。$A$ の元 $(u,v)$ を $u$ から $v$ への有向辺（arc）といい、$u$ をその始点（tail）、$v$ を終点（head）という。$(v,v)$ の形の有向辺をループといい、これを許す流儀と許さない流儀がある。
2. 多重グラフ（multigraph）とは、集合 $V$、集合 $E$、および写像 $\partial\colon E\to[V]^2$ の組 $(V,E,\partial)$ のことをいう。$\partial(e)$ を辺 $e$ の端点の対といい、$\partial(e)=\partial(e')$ かつ $e\neq e'$ である辺を平行辺（parallel edges）という。本サイトでは多重グラフは平行辺を許しループを許さないものとし、$\partial$ の値域を $[V]^2\cup\{\{v\}\mid v\in V\}$ に広げてループ（$\partial(e)=\{v\}$）も許すものはループを許す多重グラフ（擬グラフ、pseudograph）とよんで区別する。
3. 多重有向グラフ（directed multigraph）とは、集合 $V$、集合 $E$、および始点と終点を与える 2 つの写像 $i,t\colon E\to V$ の組 $(V,E,i,t)$ のことをいう。
4. 辺の集合を $E\subset V\cup[V]^2$ とし、$\{v\}\in E$ となる元を頂点 $v$ におけるループとして扱うことで、平行辺は許さずループだけを許すループを許す単純グラフを考える流儀もある。