레귤러 그래프

레귤러 그래프

Regular graph

정의 1

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

예시

레귤러 그래프

  • 피터슨 그래프Petersen Graph 200px-Petersen1\_tiny.svg.png
  • 플라톤 그래프Platonic Graph: 정다면체를 그래프로 나타낸 것이다. 피터슨 그래프와 마찬가지로 $3$-레귤러 그래프로써, 다음의 다섯가지만 존재한다.
    160px-3-simplex\_graph.svg.png 160px-3-cube\_column\_graph.svg.png 160px-3-cube\_t2.svg.png 160px-Icosahedron\_A2\_projection.svg.png 160px-Dodecahedral\_graph.neato.svg.png
  • 컴플리트 그래프: 그래프의 버텍스가 $n$ 이라면 $(n-1)$-레귤러 그래프는 컴플리트 그래프가 된다.

사이클

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

20200211\_141819.png

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

20200211\_142214.png


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

댓글