グラフ

概要

定義

単にグラフ (graph)というと、通常は次の無向グラフをいうが、広い意味でのグラフは、後に述べるさまざまなものがある。

無向グラフ (nondirected graph) とは、頂点集合 $V$ と辺集合 $E \subset [V]^2$ の組 $(V,E)$ のことをいう。ここで、$[V]^2$ とは、$V$ の異なるふたつの要素全体のなす集合のことをいう。つまりグラフとは、頂点集合と、頂点ふたつについてそのあいだに辺があるかないかのデータを付加した構造であるということができる。
グラフにおいて$\{v, w\}\in [V]^2$ を単に $vw$ であらわすこともある。もちろん $vw=wv$ である。

グラフの概念には、以下の拡張がある（これらの拡張に対して、無向かつループや重複する辺をもたないグラフを単純グラフ (simple graph) と呼ぶこともある）。

ループを許すグラフ とは、辺としてある頂点からおなじ頂点へつなぐものを認めたグラフのことをいう。たとえばループを許す無向グラフとは、頂点集合 $V$ と辺集合 $E \subset V \cup [V]^2$ の組のことをいう。
多重グラフ (multigraph) とは、異なる辺であって、おなじ頂点の組をつなぐようなものを認めたグラフのことをいう。たとえば多重無向グラフとは、頂点集合 $V$ と辺集合 $E$ と写像 $E \to V \cup [V]^2$ の組のことをいう。
有向グラフ (directed graph あるいは digraph)とは、辺に向きの情報が与えられたもののことをいう。たとえば多重有向グラフ (directed multigraph) とは、頂点集合 $V$ と辺集合 $E$ と始点をあらわす写像 $i\colon E \to V$ と終点をあらわす写像 $t\colon E \to V$ の組のことをいう。

用語

グラフ $G = (V, E)$ について、$G$ の位数 (order) とは $V$ の濃度 $\abs{V}$ のことをいう。有限グラフ (finite graph) とは、位数が有限のグラフのことをいう。この場合、位数は $V$ の要素の個数に等しい。また無限グラフ (infinite graph) とは位数が無限のグラフのことをいう。
グラフ $G = (V, E)$ について、$G$ の大きさ (size) $e(G)$ とは $E$ の濃度 $\abs{E}$ のことをいう。有限グラフの場合、大きさは $E$ の要素の個数に等しい。
グラフ $G = (V, E)$ について、頂点 $v$ が辺 $e$ に接続するとは、$v \in e$ が成り立つことをいう。すなわち、$e$ が $v$ となんらかの頂点をつないでいることをいう。無向グラフの場合にはこれは $e=\{v, w\}$ となる $w\in V$ が存在することに同値である。有向グラフの場合にはこれは $e=(v, w)$ あるいは $e=(w, v)$ となる $w\in V$ が存在することに同値である。有向グラフの場合、$e=(v, w)$ を $v$ から $w$ に向かう辺、あるいは $v$ で始まり $w$ で終わる辺という。
グラフ $G = (V, E)$ について、頂点 $v$ が頂点 $v^\prime$ に隣接する (adjacent to $v^\prime$) とは、$v$ と $v'$ をつなぐ辺が存在することをいう。無向グラフの場合にはこれは $e = \{v, v^\prime\}$ となる辺が存在することに同値である。有向グラフの場合にはこれは $e = (v, v^\prime)$ あるいは $e = (v^\prime, v)$ となる辺が存在することに同値である。
グラフ $G = (V, E)$ について、頂点 $v$ の近傍 (neighborhood) $\Gamma(x)$ とは、$v$ に隣接する頂点全体の集合 $\{w: \{v, w\}\in E\}$ のことである。
グラフ $G = (V, E)$ について、頂点 $v$ の次数 (degree) とは、$v$ に接続する辺の個数のことをいう。有向グラフの場合、$v$ の出次数 (out-degree) とは、$(v, w)$ の形の辺、つまり $v$ で始まる辺の個数、$v$ の入次数 (in-degree) とは、$(u, v)$ の形の辺、つまり $v$ で終わる辺の個数をいう。いずれも多重グラフの場合には重複度も含めて数える。
グラフ $G = (V, E)$ について、$G$ の歩道 (walk) とは、$V$ の(異ならなくともよい)頂点 $v_0, v_1, \ldots, v_\ell$ と $E$ の辺 $e_1=\{v_0, v_1\}, e_2=\{v_1, v_2\}, \ldots, e_\ell=\{e_{\ell -1}, e_\ell\}$、つまり $e_i$ が $v_{i-1}$ と $v_i$ をつなぐようなものの組のことをいう。このとき、この歩道は $v_0$ と $v_\ell$ を結ぶという。$\ell$ を、この歩道の長さ (length) という。ただし、有向グラフの場合は $e_i=(v_{i-1}, v_i)$ とする。つまり向きを考慮したものを考える。有向グラフで向きを無視する場合は、向きを無視した歩道と呼ぶことにする。
グラフ $G = (V, E)$ について、$G$ の道 (path) とは、$V$ の歩道のうち、頂点が $v_0, v_1, \ldots, v_\ell$ が相異なるものをいう。$v_0, v_\ell$ をこの道の端点 (endvertex) といい、$\ell$ を、この道の長さという。ただし有向グラフの場合は向きを考慮したものを考える。この場合は $v_0$ をこの道の始点 (initial vertex)、$v_\ell$ をこの道の終点 (terminal vertex) という。有向グラフで向きを無視する場合は、向きを無視した道と呼ぶことにする。
グラフ $G = (V, E)$ について、$G$ の閉路あるいはサイクル (cycle) とは、$V$ の歩道のうち、$v_0=v_\ell$ で $v_1, \ldots, v_\ell$ が相異なるものをいう。つまり $V$ の異なる頂点 $v_1, v_2, \ldots, v_\ell$ と $E$ の辺 $e_1=\{v_1, v_2\}, \ldots, e_{\ell -1}=\{v_{\ell-1}, v_\ell\}, e_\ell=\{v_\ell, v_1\}$、つまり $1 \leq i \leq \ell-1$ について $e_i$ が $v_i$ と $v_{i+1}$ をつなぎ、$e_\ell$ が $v_\ell$ と $v_1$ をつなぐようなものの組のことをいう。$\ell$ を、この閉路の長さという。ただし有向グラフの場合は向きを考慮したものを考える。有向グラフで向きを無視する場合は、向きを無視した閉路と呼ぶことにする。
グラフ $G = (V, E)$ について、$G$ の小道 (trail) とは、$V$ の歩道のうち、辺 $e_1, \ldots, e_\ell$ が相異なるものをいう。$\ell$ を、この小道の長さという。ただし有向グラフの場合は向きを考慮したものを考える。有向グラフで向きを無視する場合は、向きを無視した小道と呼ぶことにする。
グラフ $G = (V, E)$ について、$G$ の閉歩道 (circuit) とは、$V$ の小道のうち、$v_0=v_\ell$ となるものをいう。つまり (異ならなくともよい)頂点 $v_1, v_2, \ldots v_\ell$ と $E$ の異なる辺 $e_1=\{v_1, v_2\}, \ldots, e_{\ell -1}=\{v_{\ell-1}, v_\ell\}, e_\ell=\{v_\ell, v_1\}$、つまり $1 \leq i \leq \ell-1$ について $e_i$ が $v_i$ と $v_{i+1}$ をつなぎ、$e_\ell$ が $v_\ell$ と $v_1$ をつなぐようなものの組のことをいう。$\ell$ を、この閉歩道の長さという。ただし有向グラフの場合は向きを考慮したものを考える。有向グラフで向きを無視する場合は、向きを無視した閉歩道と呼ぶことにする。
グラフ $G = (V, E)$ について、$G$ のEuler周遊 (Euler circuit) とは、$G$ の閉歩道であって、すべての辺を一度ずつ通るもののことをいう。
グラフ $G = (V, E)$ について、$G$ のHamilton周遊 (Hamiltoniam cycle) とは、$G$ の閉路であって、すべての頂点を一度ずつ通るもののことをいう。
グラフ $G_1 = (V_1, E_1)$ とグラフ $G_2 = (V_2, E_2)$ が同型 (isomorphic) であるとは、$\abs{V_1}=\abs{V_2}$ で、頂点の集合の全単射 $f\colon V_1\to V_2$ が存在し、$\{x, y\}\in E_1\Longleftrightarrow \{f(x), f(y)\}\in E_2$ となることをいう。グラフの構造について議論するときは、同型なグラフを同一視して議論することも多い。
グラフ $G = (V, E)$ が連結 (connected) であるとは、$G$ の任意の $2$ 頂点 $u, v\in V$ について $u$ と $v$ を結ぶ道が存在することをいう。

部分グラフ

グラフ $G^\prime=(V^\prime, E^\prime)$ がグラフ $G=(V, E)$ の部分グラフ (subgraph) であるとは、$V^\prime\subset V$ かつ $E^\prime\subset E$ となることである。このことを、単に $G^\prime\subset G$ によりあらわす。
とくに、$E$ に属する辺で、$V^\prime$ の頂点同士を結ぶものをすべて含むグラフ、つまり $E^\prime=E\cap [V^\prime]^2$ となる部分グラフ $G^\prime=(V^\prime, E^\prime)$ を、$V^\prime$ により誘導される (induced) 部分グラフといい、$G[V^\prime]$ によりあらわす。
また、$V^\prime=V$ となる部分グラフ $(V, E^\prime)$ を、$G$ の全域的な (spanning) 部分グラフという。

補グラフ

グラフ $G=(V, E)$ の補グラフ (complement graph) とは、$V$ を頂点集合にもち、$G$ において隣接していない頂点同士を結ぶ辺からなるグラフ $(V, [V]^2\setminus E)$ のことである。$G$ の補グラフを $\bar G$, $G^c$ とかくこともある。

グラフの和

$2$ つのグラフ $G=(V(G), E(G)), H=(V(H), E(H))$ に対して
$$V=V(G)\cup V(H), E=E(G)\cup E(H)$$
により定まるグラフを $G\cup H=(V, E)$ によりあらわす。これに、$G$ と $H$ の頂点 $v\in G$ と $w\in H$ の間を結ぶ辺をすべて加えたグラフ、つまり
$$V=V(G)\cup V(H), E=E(G)\cup E(H)\cup\{(v, w): v\in G, w\in H\}$$
により定まるグラフを $G+H=(V, E)$ によりあらわす。

例

完全グラフ (complete graph) とは、$E=[V]^2$ となるグラフをいう。$\abs{V}=n$ となる完全グラフを $K_n$ であらわす。
空グラフ (empty graph) とは、辺をもたないグラフ、つまり $E=\emptyset$ となるグラフをいう。$\abs{V}=n$ となる空グラフを $E_n$ であらわす。$E_n=\bar K_n$ となる。
二部グラフ (bipartite graph) とは、$V=V_1\cup V_2$ となる、共通部分をもたない頂点集合 $V_1, V_2$ が存在して、$E$ の任意の辺が $\{v_1, v_2\} ~ (v_1\in V_1, v_2\in V_2)$ の形になっているものをいう。とくに、$E$ がこの形の辺全体と一致するものを完全二部グラフ (complete bipartite graph) という。$\abs{V_1}=m$, $\abs{V_2}=n$ となる完全二部グラフを $K_{m, n}$ であらわす。
閉路をもたないグラフを森 (forest)、閉路をもたない連結なグラフを木 (tree) という。
長さ $n$ の閉路を、$n$ 角形 ($n$-gon) という。