📂グラフ理論

無限グラフ

定義 ¹

1. グラフ $G$ の頂点集合 $V(G)$ や辺集合 $E(G)$ が無限集合である場合、$G$ を無限グラフという。
2. $V(G)$ と $E(G)$ が両方とも可算集合である無限グラフ $G$ を可算グラフという。
3. 無限グラフ $G$ の頂点 $v \in V(G)$ に対して、$A(v)$ を次のように定義しよう。 $$A(v) := \left\{ w : vw \in E(G) \right\}$$ 無限グラフ $G$ の頂点の次数は、$A(v)$ の基数として定義される。 $$\deg (v) = | A(v) |$$ $\deg (v) < \infty$ なら有限次数、$\deg (v) = \aleph_{0}$ なら可算次数という。
4. 無限グラフ $G$ の全ての頂点の次数が有限であれば、局所的に有限という。
5. 無限グラフ $G$ の全ての頂点の次数が可算であれば、局所的に可算という。

---

• アレフ $\aleph_{0}$ は可算集合の基数を意味する。

解説

無限グラフは一見想像しにくいかもしれないが、数学的にはただの自然な一般化に過ぎない。例えば、整数集合 $\mathbb{Z}$ を頂点として持つグラフを想像してみよう。任意の $v,w \in V(G) = \mathbb{Z}$ に対して、$\gcd(v,w) = 1$ であれば、$vw \in E(G)$ と定義すると、これをグラフと呼ぶには全く問題がない。当然、このグラフは無限グラフであり、特に可算グラフである。