グラフ
提供: Mathpedia
グラフとは、頂点とよばれる点的なオブジェクトと、辺とよばれる線的なオブジェクトのなす構造のことをいう。グラフの概念は現在組合せ論において非常に基本的な対象となっている。
定義
(無向)グラフとは、頂点集合 $V$ と辺集合 $E \subset [V]^2$ の組 $(V,E)$ のことをいう。ここで、$[V]^2$ とは、$V$ の異なるふたつの要素全体のなす集合のことをいう。つまりグラフとは、頂点集合と、頂点ふたつについてそのあいだに辺があるかないかのデータを付加した構造であるということができる。
変種
- ループを許すグラフとは、辺としてある頂点からおなじ頂点へつなぐものを認めたグラフのことをいう。たとえばループを許す無向グラフとは、頂点集合 $V$ と辺集合 $E \subset V \cup [V]^2$ の組のことをいう。
- 多重グラフとは、異なる辺であって、おなじ頂点の組をつなぐようなものを認めたグラフのことをいう。たとえば多重無向グラフとは、頂点集合 $V$ と辺集合 $E$ と写像 $E \to V \cup [V]^2$ の組のことをいう。
- 有向グラフとは、辺に向きの情報が与えられたもののことをいう。たとえば多重有向グラフとは、頂点集合 $V$ と辺集合 $E$ と始点をあらわす写像 $i\colon E \to V$ と終点をあらわす写像 $t\colon E \to V$ の組のことをいう。
用語
- グラフ $G = (V,E)$ について、$G$ の位数とは $V$ の濃度(要素の個数)のことをいう。有限グラフとは、位数が有限のグラフのことをいう。また無限グラフとは位数が無限のグラフのことをいう。
- グラフ $G = (V,E)$ について、頂点 $v$ が辺 $e$ に接続するとは、$v \in e$ が成り立つことをいう。すなわち、$e$ が $v$ となんらかの頂点をつないでいることをいう。
- グラフ $G = (V,E)$ について、頂点 $v$ が頂点 $v'$ に隣接するとは、$e = \{v, v'\}$ なる辺が存在することをいう。すなわち、$v$ と $v'$ をつなぐ辺が存在することをいう。
- グラフ $G = (V,E)$ について、頂点 $v$ の次数とは、$v$ に接続する辺の個数のことをいう。
- グラフ $G = (V,E)$ について、$G$ の道とは、$V$ の異なる頂点 $v_0, v_1, \ldots v_n$ と $E$ の辺 $e_0, e_1, \ldots e_{n-1}$ であって、$e_i$ が $v_i$ と $v_{i+1}$ をつなぐようなものの組のことをいう(有向グラフの場合は向きを考慮したものを考える: 向きを無視する場合は、向きを無視した道と呼ぶことにする)。
- グラフ $G = (V,E)$ について、$G$ の閉路とは、$V$ の異なる頂点 $v_0, v_1, \ldots v_n$ と $E$ の辺 $e_0, e_1, \ldots e_{n-1}, e_n$ であって、$0 \leq i \leq n-1$ について $e_i$ が $v_i$ と $v_{i+1}$ をつなぎ、$e_n$ が $v_n$ と $v_0$ をつなぐようなものの組のことをいう(有向グラフの場合は向きを考慮したものを考える: 向きを無視する場合は、向きを無視した閉路と呼ぶことにする)。
- グラフ $G = (V,E)$ について、$G$ の歩道とは、$V$ の(異ならなくともよい)頂点 $v_0, v_1, \ldots v_n$ と $E$ の辺 $e_0, e_1, \ldots e_{n-1}$ であって、$e_i$ が $v_i$ と $v_{i+1}$ をつなぐようなものの組のことをいう(有向グラフの場合は向きを考慮したものを考える: 向きを無視する場合は、向きを無視した歩道と呼ぶことにする)。
- グラフ $G = (V,E)$ について、$G$ の閉歩道とは、$V$ の(異ならなくともよい)頂点 $v_0, v_1, \ldots v_n$ と $E$ の辺 $e_0, e_1, \ldots e_{n-1}, e_n$ であって、$0 \leq i \leq n-1$ について $e_i$ が $v_i$ と $v_{i+1}$ をつなぎ、$e_n$ が $v_n$ と $v_0$ をつなぐようなものの組のことをいう(有向グラフの場合は向きを考慮したものを考える: 向きを無視する場合は、向きを無視した閉歩道と呼ぶことにする)。
- グラフ $G = (V,E)$ について、$G$ のEuler周遊とは、$G$ の閉歩道であって、すべての辺を一度ずつ通るもののことをいう。
- グラフ $G = (V,E)$ について、$G$ のHamilton周遊とは、$G$ の閉路であって、すべての頂点を一度ずつ通るもののことをいう。
information
情報源
- R. Diestel. "Graph Theory". Springer (2000).
関連記事
いくつかの基本的な概念についての解説については以下の記事群なども参照されたい。
