degree

$G = (V , E)$가 non-empty graph라고 할 때, 임의의 점 $v \in V$에 대해 이웃한 점(neighbours)의 집합을 $N _G (v)$ 또는 간략하게 $N(v)$라고 나타낸다. 이걸 더 일반적으로 확장시켜서, 어떤 점 집합 $U \subset V$에 대해 $N(U)$는 $U = \{ u_1 , u_2 , \cdots , u_n \}$으로 놓았을 때 다음과 같이 정의한다.

$$N(U) = \bigcup _{i=1} ^n N(u_i) \setminus U$$

예를 들면 위 그래프에서 $d(A) = 3$, $U = \{A,B,C,G\}$일 때, $d(U) = 5$이다.

어떤 점 $v$에 대해 $d(v) = 0$이면 $v$는 '고립되었다(isolated)'라고 한다.

$G$의 minimum degree는 graph $G$의 점 집합 $V$에 대해 $\delta(G) := \min \{d(v) | v \in V \}$, maximum degree는 $\Delta(v) := \max \{d(v) | v \in V \}$ 로 정의한다.

어떤 그래프가 모든 점에 대해 degree가 $k$로 같으면 $k$-regular라고 한다.

어떤 그래프의 average degree는 다음과 같이 정의한다.

$$d(G) = \frac {1}{|V|} \sum _{v \in V} d(v)$$