📂그래프이론

그래프 이론에서의 차수

정의 ¹

유향 그래프 $G$ 가 주어져있다고 하자.

에지 $vw$ 가 존재하면 에지가 $v$ 에서 나가고 $w$ 로 들어간다고 말한다.

• 버텍스 $v$ 로 들어오는 에지의 수를 입력 차수^indegree라 하고 $\deg^{-} (v)$ 와 같이 나타낸다.
• 버텍스 $v$ 에서 나가는 에지의 수를 출력 차수^outdegree라 하고 $\deg^{+}(v)$ 와 같이 나타낸다.
• $\deg^{-} (v) = 0$ 인 버텍스를 소스^source , $\deg^{+} (v) = 0$ 인 버텍스를 싱크^sink라 부른다. 싱크도 소스도 아닌 점을 인터널^internal이라 한다.

에지 $vw$ 가 존재하면 버텍스 $v,w$ 가 에지 $vw$ 에 딸려있다^incident고 말한다.

• 버텍스 $v$ 가 딸려있는 에지의 수를 차수^degree라 하고 $\deg (v)$ 와 같이 나타낸다.
• 차수가 $0$ 인 버텍스를 고립 버텍스^{isolated Vertex}라 한다.
• 차수가 $1$ 인 버텍스를 엔드 버텍스^{end Vertex}라 한다.

그래프 $G$ 의 가장 큰 차수를 $\Delta (G)$, 가장 작은 차수를 $\delta (G)$ 와 같이 나타낸다.

설명

참고로 딸려Incident있다라는 표현이 별로 좋은 순화는 아니다. 두 버텍스 $v,w$ 가 에지 $e$ 로 이어져있을 때 $v$ 와 $w$ 는 인접Adjacent하다고 표현하며, 딸려있다는 말은 그렇게 에지 $e$ 에 붙어있는 $v,w$ 를 묘사하기 위해 쓰인다. 원래 형용사 Incident는 부속되는, 따르는 등의 뜻으로 쓰이는 영단어다.

차수의 개념은 그래프 이론에서 쉽게 생각할 수 있는 ‘수’기 때문에 오랫동안 많은 관심을 받아왔으며, 특히 순수 수학에서는 심플 그래프를 자주 다뤄서 차수에 대한 연구가 많다.

유향 그래프

예로써 다음 그래프에서 빨간색은 입력 차수, 파란색은 출력 차수를 나타낸다. 당연하지만 입력 차수와 출력 차수의 합은 같다.

여기서 입력 차수가 $0$ 인 버텍스는 소스라고 불린다. 들어오는 것 없이 나가기만 한다는 점에서 소스라고 부르는 것은 타당한 명명이라고 할 수 있다. 이는 동역학에서의 싱크, 소스와 비슷하다.

차수

예로써 다음 그래프에서 각 버텍스의 차수를 계산해볼 수 있다. 차수는 유향 그래프를 그냥 심플 그래프로 나타내었을 때 입력 차수와 출력 차수의 합계와 같음을 확인해보자. [ NOTE: 이렇게 방향을 없앤 그래프를 원래 유향 그래프의 기저 그래프^{underlying Graph}라 한다. ]

다음 그래프에서 버텍스 $C$ 와 $F$ 는 엔드 버텍스, $H$ 는 고립 버텍스다.

참고로 응용수학에서는 위와 같은 네트워크에서 $H$ 만 없다면, 그러니까 모두 연결된 네트워크일 때 $D$ 와 같은 노드를 허브Hub라고 부른다. 보통 허브는 네트워크 전체에 큰 영향력을 미치거나 모든 통신을 중개할 수 있는 요소를 묘사한다.

레귤러 그래프

특히 $\delta (G) = \Delta (G)$, 즉 모든 버텍스의 차수가 같은 그래프를 레귤러 그래프라 한다.