일반화 페테르센 그래프(Generalized Petersen graph, 약칭 GP(n, k))는 그래프 이론에서 무방향 단순 그래프의 한 종류로, 두 매개변수 n (정수, n ≥ 3)와 k (정수, 1 ≤ k < n/2)로 정의된다.
정의
정점 집합은 두 개의 원형 정점 집합으로 구성된다.
- 외부 정점 집합 U = { u₀, u₁, …, u_{n‑1} }
- 내부 정점 집합 V = { v₀, v₁, …, v_{n‑1} }
간선은 다음과 같이 연결한다.
- 외부 정점 사이: 각 u_i 와 u_{i+1 (mod n)} 을 연결한다. (외부 원형 Cₙ)
- 내부 정점 사이: 각 v_i 와 v_{i+k (mod n)} 을 연결한다. (스킵-스텝 k 로 이루어진 내부 원형)
- 외부‑내부 정점 연결: 각 u_i 와 v_i 을 연결한다.
이때 얻어지는 그래프를 일반화 페테르센 그래프 GP(n, k)라 부른다.
특성
- 모든 정점의 차수는 3이다(3‑정칙 그래프).
- n 이 짝수이고 k = n/2인 경우는 정의되지 않는다(조건 k < n/2).
- GP(5, 2)는 원래의 페테르센 그래프와 일치한다.
- GP(n, 1)은 원통형 격자 형태의 그래프가 된다.
- 그래프의 연결성, 색칠 가능성, 사이클 구조 등은 (n, k)의 값에 따라 달라진다. 예를 들어, GP(n, k)는 n이 짝수이고 k = n/2 − 1인 경우에 비플라너(평면이 아님) 그래프가 된다.
주요 결과 및 연구 분야
- 하미딩 연산: GP(n, k)는 하미딩 연산을 적용한 결과가 종종 또 다른 일반화 페테르센 그래프로 나타난다.
- 크로스 수와 색칠: 차수 3인 그래프이므로 3‑색칠 문제와 밀접한 관계가 있다. GP(n, k)가 3‑가시적인 경우와 그렇지 않은 경우가 연구된다.
- 스펙트럼: 인접 행렬 및 라플라시안 스펙트럼이 (n, k)에 대한 명시적 식으로 표현될 수 있다. 이는 화학 구조 모형과 네트워크 분석에 활용된다.
- 대칭성: GP(n, k)는 디헤디 그래프(Dihedral group) D_n 의 작용을 대칭군으로 갖는다. 특수한 (n, k) 조합에서는 추가적인 대칭이 존재한다.
활용 및 응용 사례
- 화학 및 분자 모델링: 정점이 원자를, 간선이 결합을 나타내는 모델에서 3‑정칙 구조를 모사하는 데 사용된다.
- 통신 네트워크: 정점 차수가 일정하고 고른 연결성을 가지는 특성으로 인해 토폴로지 설계의 시험 모델로 활용된다.
- 알고리즘 시험: 그래프 탐색, 최단 경로, 매칭 알고리즘 등 다양한 그래프 알고리즘의 성능 평가에 표준 테스트 사례로 채택된다.
참고 문헌 (일부)
- J. A. Bondy, U. S. R. Muller, Graph Theory, Springer, 2008.
- R. J. Wilson, Introduction to Graph Theory, 5th ed., Pearson, 2010.
- D. M. Cox, “Generalized Petersen graphs”, Discrete Mathematics 27 (1979), 65‑73.
위와 같이 일반화 페테르센 그래프는 (n, k) 두 정수 매개변수에 의해 정의되는 3‑정칙 그래프 계열로, 페테르센 그래프를 포함한 다양한 구조적 특성과 응용을 갖는 잘 확립된 수학적 개념이다.
