📂グラフ理論

グラフ理論における歩行、道、経路、サイクル

定義 ¹

グラフ $G$ が与えられたとする。

1. エッジの有限 シーケンスを ウォークと呼び、以下のように表す。 $$ v_{0} v_{1} , v_{1} v_{2} , \cdots , v_{m-1} v_{m} \\ v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{m-1} \rightarrow v_{m} $$ ここで、$v_{0}$ を 始点、$v_{m}$ を 終点、$m$ を 長さと呼ぶ。
2. ウォークのエッジが全て異なる場合、トレイルと呼ぶ。
3. ウォークの頂点が全て異なる場合、パスと呼ぶ。
4. ウォークの始点と終点が同じ場合、閉じていると呼ぶ。
5. 閉じたパスを サイクルと呼ぶ。

これらの概念は、有向グラフに対しても同様に定義でき、以下のように無限グラフに対しても定義できる。

$G$が無限グラフだとする。以下の定義ではウォークはトレイル、パス、サイクルに置き換えられる。 6. (有限)ウォークは一般的なグラフのウォークと全く同じである。 7. 一方向無限ウォークは次のように定義される。 $$ v_{0} \to v_{1} \to v_{2} \to \cdots $$ 8. 双方向無限ウォークは次のように定義される。 $$ \cdots \to v_{-2} \to v_{-1} \to v_{0} \to v_{1} \to v_{2} \to \cdots $$

説明

パスの定義において、始点と終点は例外である。つまり、$v_{0} = v_{m}$である場合にはパスとなり、したがって「閉じたパス」が存在することになる。また、パスとトレイルの定義においては、頂点が全て異なればエッジも全て異なるため、パスはトレイルでもある。

サイクルは、簡単に言うと、グラフで見つけることができる「輪の形」で、グラフ理論全体で広く使用される概念である。例として、次の図を見ると、グラフで合計三つのサイクルを見つけることができる：

また、サイクルに関して次の定理が知られている。

定理

有限グラフ $G$ の全ての頂点の 次数が $2$ 以上であれば、$G$ にはサイクルが含まれる。

証明

$G$ がループやマルチプルエッジを持てば当然サイクルが存在するため、$G$は単純グラフと仮定する。

任意の頂点 $v_{0} \in V(G)$ 一つを選び、以下のようなパスを考える。 $$ v_{0} \to v_{1} \to v_{2} \to \cdots $$ 仮定により、全ての頂点の次数は $2$ 以上であるため、少なくとも二つの頂点と隣接している。したがって、$v_{i+1}$ は直前の頂点 $v_{i}$ に隣接している頂点の中から $v_{i-1}$ を除いた任意の頂点を選び続けることができる。しかし、$G$ は有限グラフであるため、いずれはすでにパスに含まれている頂点 $v_{k}$ を選ばなければならなくなる。そうすると、始点と終点が $v_{k}$ であるパス $v_{k} \to \cdots \to v_{k}$ は、$G$においてサイクルとして存在することがわかる。

■