차수

매우 중요한 개념인 차수(degree)를 이야기해 볼까 합니다. 무방향 그래프의 경우 어떤 정점 v의 차수 d(v)는 정점 v가 부속된 에지 개수입니다. 여기서 부속되었다(incident)는 표현은 정점 u와 정점 v 사이에 에지 (u, v)가 존재할 때 에지 (u, v)를 정점 u에 부속되었다, 정점 v에 부속되었다고 표현합니다. 그림으로 확인해 볼까요?

▲ 그림 6-8 무방향 그래프의 차수

그림 6-8을 보면 정점 2에 부속된 에지가 세 개이므로 d(2)=3입니다. 방향 그래프는 어떨까요? 방향 그래프에서는 차수를 두 가지로 나눕니다. 진입 차수(in-degree)는 정점 v가 head인 경우입니다. 다시 말해 정점 v로 들어오는 에지 개수입니다. in-d(v)라고 표기합니다. 진출 차수(out-degree)는 tail인 경우입니다. 정점 v에서 나가는 에지 개수입니다. out-d(v)라고 표기합니다. 방향 그래프에서 차수는 진입 차수와 진출 차수의 합입니다. d(v)라고 표기합니다.