정규 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

정규 그래프(영어: regular graph)는 모든 꼭짓점이 동일한 수의 이웃을 가지는 그래프이다. 즉, 모든 꼭짓점이 같은 차수를 가진다. 각 꼭짓점이 k개의 이웃을 가지는 정규 그래프를 k-정규 그래프라고 부른다.

[편집]

0-정규 그래프는 무변 그래프이다. 1-정규 그래프의 연결 성분은 경로 그래프 K_2=P_2이다. 2-정규 그래프의 연결 성분은 순환 그래프나 무한 경로 그래프이다. 3-정규 그래프는 삼차 그래프라고 한다.

생성 조건[편집]

n개의 꼭짓점을 가진 k-정규 그래프의 필요 충분 조건은 n \geq k+1 이면서 nk가 짝수여야 한다.