레귤러 그래프

레귤러 그래프

정의 1

  1. 모든 버텍스의 차수가 같은 그래프레귤러 그래프Regular Graph라고 한다. 특히 모든 버텍스의 차수가 $r$ 이면 $r$-레귤러 그래프라고 한다. 다시 말해, 다음을 만족시키는 그래프 $G$ 를 $r$-레귤러 그래프라고 한다. $$ \deg (v) = r \qquad , \forall v \in V(G) $$
  2. $2$-레귤러 연결 그래프사이클Cycle이라고 한다.

예시

레귤러 그래프

사이클

사이클은 가장 단순한 형태의 그래프로써 순수 그래프 이론에서 많은 관심을 받는다. 물론 정말 사이클 그래프 자체는 아니고, 그래프 안에서 사이클 모양을 한 부분에 대한 이야기다. [ NOTE: 사이클에서 단 하나의 에지를 제거한 그래프를 패스Path라 부르기도 한다. ] 사이클의 모양을 직접 보면 왜 $2$-레귤러를 사이클이라고 부르는지 한 눈에 이해할 수 있다.

20200211\_141819.png

한편 다음은 사이클이 되려면 왜 연결되어야하는지에 대한 예시다. 두 컴포넌트로 이루어진 다음의 그래프 $G = A \cup B$ 는 분명 $2$-레귤러긴 하지만 두 사이클의 유니언으로 표현되므로 진정 사이클이라고 하기엔 부적절함을 알 수 있다. 물론 $A$ 와 $B$ 그 각각은 사이클이다.

20200211\_142214.png


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

댓글