정규 그래프

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

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

0-정규 그래프는 변이 없는 그래프고, 1-정규 그래프는 연결되지 않은 변(edge)들로 이루어졌으며, 2-정규 그래프는 회로(cycle)로 구성된 그래프이다. 3-정규 그래프는 큐빅 그래프라고도 부른다.

생성조건[편집]

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