정규 그래프 편집하기

정규 그래프(正規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.
==각주==
[[분류:그래프]]
[[분류:그래프 이론]]