정규 그래프(正規graph, regular graph)는 그래프 이론에서 모든 정점의 차수가 동일한 그래프이다.
정의
정규 그래프란 그래프에 속한 모든 정점이 동일한 차수를 가지는 그래프로, 모든 정점이 k개의 간선을 가질 경우 이를 k-정규 그래프(k-regular graph)라고 한다. 이때 k는 0 이상의 정수이다. 정규 그래프는 방향성이 없는 단순 그래프일 수도 있고, 방향 그래프일 수도 있다.
종류
- 0-정규 그래프: 간선이 전혀 없는 독립 정점들의 집합이다.
- 1-정규 그래프: 서로 연결된 정점 쌍의 집합으로 구성된 그래프이다. 각 연결 쌍은 독립적인 간선이다.
- 2-정규 그래프: 모든 정점이 차수 2를 가지므로, 이는 단순 순환 그래프 또는 그들의 합집합으로 구성된다.
- k-정규 그래프: 일반적인 형태로, 정점마다 정확히 k개의 인접 정점이 존재한다.
성질
- k-정규 그래프의 모든 정점 차수가 동일하므로, 간선 수는 (k×정점 수)/2이다.
- 정규 그래프는 대칭성이 높으며, 자주 대칭 그래프와 관련된다.
- k가 홀수이고 정점 수가 홀수이면 그러한 단순 정규 그래프는 존재하지 않는다.
- 정규 그래프의 인접 행렬은 정규 행렬로 해석될 수 있으며, 스펙트럼 그래프 이론에서 중요한 역할을 한다.
예시
- 완전 그래프 Kn은 (n-1)-정규 그래프이다.
- n-사이클(Cn)은 2-정규 그래프이다.
- 하이퍼큐브 Qn은 n-정규 그래프이다.
- 페테르센 그래프는 3-정규 그래프이며, 평면 그래프가 아닌 대표적인 예시이다.
응용
- 네트워크 구성: 통신 또는 컴퓨팅 노드의 연결 균형을 맞추는 데 사용된다.
- 이론 컴퓨터 과학: 라마누잔 그래프, 확장 그래프 등의 정규 그래프는 효율적인 알고리즘 설계에 유용하다.
- 수학적 모델링: 대칭성과 균형 특성 때문에 수학적 구조 해석에 자주 활용된다.
같이 보기
참고 문헌
- Diestel, R. (2017). *Graph Theory* (5th ed.). Springer.