📂그래프이론

레귤러 그래프

정의 ¹

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

예시

레귤러 그래프

• 피터슨 그래프^{petersen Graph}
• 플라톤 그래프^{platonic Graph}: 정다면체를 그래프로 나타낸 것이다. 피터슨 그래프와 마찬가지로 $3$-레귤러 그래프로써, 다음의 다섯가지만 존재한다.
  
• 컴플리트 그래프: 그래프의 버텍스가 $n$ 이라면 $(n-1)$-레귤러 그래프는 컴플리트 그래프가 된다.

사이클

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

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