📂그래프이론

무한 그래프

정의 ¹

1. 그래프 $G$ 의 버텍스 집합 $V(G)$ 나 에지 집합 $E(G)$ 가 무한 집합이면 $G$ 를 무한 그래프라고 한다.
2. $V(G)$ 와 $E(G)$ 가 모두 가산 집합인 무한 그래프 $G$ 를 가산 그래프^{countable Graph}라 한다.
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$ 의 모든 버텍스의 차수가 유한하면 국소적으로 유한^{locally Finite}하다고 한다.
5. 무한 그래프 $G$ 의 모든 버텍스의 차수가 가산이면 국소적으로 가산^{locally Countable}하다고 한다.

---

• 알레프 $\aleph_{0}$ 는 가산 집합의 기수를 의미한다.

설명

무한 그래프는 언뜻 상상하기 어렵지만 수학적으로는 자연스러운 일반화에 지나지 않는다. 예로써 정수 집합 $\mathbb{Z}$ 을 버텍스로 가지는 그래프를 상상해보자. 임의의 $v,w \in V(G) = \mathbb{Z}$ 에 대해 $\gcd(v,w) = 1$ 이면 $vw \in E(G)$ 이라고 정의하면 이는 그래프라 불리기에 부족함이 전혀 없다. 당연하게도 이 그래프는 무한 그래프며, 특히 가산 그래프가 된다.