그래프 이론에서의 차수

그래프 이론에서의 차수

정의 1

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

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

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

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

설명

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

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

유향 그래프

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

20200130\_151646.png

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

차수

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

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

20200130\_150454.png

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

레귤러 그래프

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


  1. Wilson. (1970). Introduction to Graph Theory: p12. ↩︎

댓글