정의
정규 그래프(regular graph)는 무방향 그래프 $G = (V, E)$에서 모든 정점 $v \in V$가 같은 차수$d$를 갖는 그래프를 말한다. 즉, 모든 정점이 정확히 $d$개의 인접 정점을 가진다. 이러한 $d$를 그래프의 정규도(regular degree)라 하며, $d$-정규 그래프($d$-regular graph)라고도 표현한다.
특성 및 성질
| 성질 | 설명 |
|---|---|
| 차수 합 공식 | 그래프의 모든 정점 차수의 합은 $ \sum_{v \in V}\deg(v) = d |
| 가능한 정규도 | $ |
| 완전 그래프와 사이클 | 0-정규 그래프는 독립 집합(에지 없음)이며, 1-정규 그래프는 각 연결 성분이 두 정점을 연결하는 단일 에지인 경우이다. 2-정규 그래프는 모든 연결 성분이 사이클(길이 ≥ 3)이다. |
| 이분 그래프와 정규도 | $d$-정규 이분 그래프는 두 부분집합이 각각 $k$개의 정점을 갖고, 각 정점이 반대쪽 모든 정점과 연결되는 경우(전완전 이분 그래프) 등 특수한 구조를 가진다. |
| 라플라시안 스펙트럼 | 정규 그래프는 라플라시안 행렬 $L = D - A$ (여기서 $D$는 차수 행렬, $A$는 인접 행렬)에서 가장 작은 고유값이 0이고, 그다음 고유값은 정규도 $d$와 관련된 대칭성을 보인다. |
예시
| 그래프 | 정규도 $d$ | 설명 |
|---|---|---|
| 완전 그래프 $K_n$ | $n-1$ | 모든 정점이 서로 연결된 그래프 |
| 순환 그래프 $C_n$ | 2 | 정점이 순환 형태로 연결된 2-정규 그래프 |
| 입방체 그래프 $Q_3$ | 3 | 8개의 정점이 3차원 입방체 형태로 연결된 3-정규 그래프 |
| Petersen 그래프 | 3 | 10개의 정점과 15개의 에지를 가진 3-정규 그래프, 비직교 그래프의 대표적인 예시 |
관련 개념
- 정규도(regular degree): 정규 그래프에서 모든 정점이 갖는 공통 차수.
- 정규성(regularity): 그래프가 정규인지 여부를 나타내는 속성.
- 준정규 그래프(semiregular graph): 이분 그래프에서 양쪽 파트가 각각 다른 정규도를 가질 때 사용되는 용어.
- 정규 라우프라시안(regular Laplacian): 정규 그래프의 라플라시안 행렬은 특정 대칭성을 띤다.
어원 및 사용 맥락
‘정규(regular)’는 라틴어 regularis에서 유래했으며, ‘규칙적인’, ‘일정한’이라는 뜻을 가진다. 그래프 이론에서는 ‘모든 정점이 동일한 차수를 가진’이라는 의미로 사용한다. 한국어 학술 논문·교재에서 ‘정규 그래프’라는 용어는 주로 조합론, 네트워크 설계, 라우팅 이론, 그리고 스펙트럴 그래프 이론 등에서 등장한다.
참고
- West, D. B. Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001.
- Diestel, R. Graph Theory, 5th ed., Springer, 2017.
- Bollobás, B. Modern Graph Theory, Springer, 1998.
