일반화 페테르센 그래프

그래프 이론에서 **일반화 페테르센 그래프**(一般化Petersen graph, generalized Petersen graph)는 같은 수의 꼭짓점을 갖는 정다각형과 별 모양에서 대응하는 꼭짓점들을 이어 얻는 그래프이다. 특히, 오각형과 오각 별을 이어 얻는 그래프를 **페테르센 그래프**(Petersen graph)라고 한다.doi=10.2277/0521435943
# 정의
3 이상의 정수 n\ge3과, n의 배수가 아닌 정수 k\in\mathbb Z, n\nmid k가 주어졌다고 하자. 또한, 만약 n이 짝수라면 n/2\nmid k라고 하자. **일반화 페테르센 그래프** \operatorname{GPG}(n,k)는 다음과 같은 그래프이다. :\operatorname V(\operatorname{GPG}(n,k))=\\{u_i,v_i\colon i\in\mathbb Z/n\\} :\operatorname E(\operatorname{GPG}(n,k))=\\{u_i u_{i+1}, u_i v_i, v_i v_{i+k}\colon i\in\mathbb Z/n\\} 여기서 첨자는 법 n으로 계산한다. 즉, u_{n+i}=u_i 및 v_{n+i}=u_i로 간주한다. 일반화 페테르센 그래프의 변 가운데, u_iv_i 꼴의 변을 **바큇살**(spoke)이라고 한다. 당연히 :\operatorname{GPG}(n,k)=\operatorname{GPG}(n,k+n)=\operatorname{GPG}(n,-k) 이므로, 보통 :1\le k< n/2 를 가정한다.
# 성질

## 기초적 성질
페테르센 그래프 \operatorname{GPG}(5,2) 속의 완벽 부합 일반화 페테르센 그래프 \operatorname{GPG}(n,k)는 2n개의 꼭짓점과 3n개의 변을 가지는 삼차 그래프이며, 완벽 부합을 갖는다. 구체적으로, 위와 같은 표기에서, \\{u_iv_i\\}_{i\in\mathbb Z/n}은 완벽 부합을 이룬다.
## 동형
임의의 정수 n\ge3 및 정수 1\le k,k'에 대하여, 다음 두 조건이 서로 동치이다.url-status=Proposition 9언어=en * \operatorname{GPG}(n,k)\cong\operatorname{GPG}(n,k') * kk' \equiv \pm1 \pmod n 예를 들어, \operatorname{GPG}(7,2)\cong\operatorname{GPG}(7,3)이다.
## 안둘레
일반화 페테르센 그래프 \operatorname{GPG}(n,k)의 안둘레는 항상 \min\\{8,k+3,n/\gcd\\{n,k\\}\\} 이하이다.url-status=deadTheorem 2.1

**증명:**

일반화 페테르센 그래프의 꼭짓점 및 변은 :\operatorname V(\operatorname{GPG}(n,k))=\\{u_i,v_i\colon i\in\mathbb Z/n\\} :\operatorname E(\operatorname{GPG}(n,k))=\\{u_i u_{i+1}, u_i v_i, v_i v_{i+k}\colon i\in\mathbb Z/n\\} 이다. 그 속에서 :u_0 - v_0 - v_k - u_k - u_{k+1} - v_{k+1} - v_1 - u_1 - u_0 는 길이 8의 순환이며, :u_0 - v_0 - v_k - u_k - u_{k-1} - \dotsb - u_1 - u_0 는 길이 k+3의 순환이며, :v_0 - v_k - v_{2k} - \dotsb - v_0 는 길이 n/\gcd\\{n,k\\}의 순환이다.

또한, 다음이 성립한다. :\operatorname{girth}(\operatorname{GPG}(ak\pm b,k)) \le a+b+2

**증명:**

일반화 페테르센 그래프의 꼭짓점 및 변은 :\operatorname V(\operatorname{GPG}(n,k))=\\{u_i,v_i\colon i\in\mathbb Z/n\\} :\operatorname E(\operatorname{GPG}(n,k))=\\{u_i u_{i+1}, u_i v_i, v_i v_{i+k}\colon i\in\mathbb Z/n\\} 이다. 그 속에서 :u_0-v_0-v_k-\dotsb-v_{ak\equiv\pm b}-u_{\pm b}-u_{\pm(b-1)}-\dotsb-u_{\pm1}-u_0 은 길이 a+b+2의 순환이다 (복부호 동순).

위 상계 가운데 적어도 하나가 포화된다. 즉, 만약 1\le k이며, :k=\min\left\\{1\le k' 일 때, 일반화 페테르센 그래프 \operatorname{GPG}(n,k)의 안둘레는 다음 표에서, 위에서부터 가장 먼저 해당하는 행에 의해 주어진다.Theorem 2.8 :{| class=wikitable || 안둘레 |- | n=3k || 3 |- | n=4k | rowspan=2 | 4 |- | k=1 |- | n=5k | rowspan=3 | 5 |- | n=5k/2 |- | k=2 |- | n=6k | rowspan=3 | 6 |- | k=3 |- | n=2k+2 |- | n=7k | rowspan=6 | 7 |- | n=7k/2 |- | n=7k/3 |- | k=4 |- | n=2k+3 |- | n=3k\pm2 |- | 그 밖의 경우 || 8 |}

**증명:**

일반화 페테르센 그래프의 꼭짓점 및 변은 :\operatorname V(\operatorname{GPG}(n,k))=\\{u_i,v_i\colon i\in\mathbb Z/n\\} :\operatorname E(\operatorname{GPG}(n,k))=\\{u_i u_{i+1}, u_i v_i, v_i v_{i+k}\colon i\in\mathbb Z/n\\} 이다. 일반화 페테르센 그래프 속의 모든 순환은 당연히 짝수 개의 바큇살 u_iv_i을 포함한다. 모든 일반화 페테르센 그래프는 4개의 바큇살을 갖는 길이 8의 순환 :u_0 - v_0 - v_k - u_k - u_{k+1} - v_{k+1} - v_1 - u_1 - u_0 을 가지며, 바큇살 6개 이상의 순환의 길이는 항상 12 이상이다. 따라서, 2개의 바큇살 및 0개의 바큇살을 갖는 순환들만 고려하면 된다. 2개의 바큇살을 갖는 순환은 (편의상 첫 변을 u_0-u_1로 잡으면) 항상 다음과 같은 꼴이다. :u_0-u_1-\dotsb-u_b-v_b-v_{b\pm k}-v_{b\pm 2k}-\dotsb-v_{b\pm ak}-u_0 이것이 존재하기 위해서는 ak\pm b\mid n이어야 하며, 이 경우 순환의 길이는 a+b+2이다. * k가 최솟값이어야 하므로, ak+b=n 및 ak+b=0인 경우만 고려해도 된다. ** ak+b=0인 경우: (a,b)=(1,-k)인 경우가 최적이며, 이 경우 순환의 길이는 k+3이다. ** ak+b=n인 경우: *** 만약 n=ak\pm1인 경우, \operatorname{GPG}(n,k)\cong\operatorname{GPG}(n,a)이다. 따라서, 이 경우 k는 최솟값을 갖지 못한다. *** 만약 n=ak일 경우, 이 경우 0개의 바큇살을 갖는 길이 a의 순환이 더 짧다. *** 만약 n=2k-b일 경우, k\ge n/2이다. *** 위 경우를 제외하면, 이러한 순환의 길이가 8 미만인 경우는 남는 것은 (a,b)=(2,2), (2,3), (3,2), (3,-2)이다. 0개의 바큇살을 갖는 순환은 u_i 또는 v_i로만 구성된다. u_i만으로 구성되는 유일한 순환의 길이는 n이며, v_i만으로 구성되는 순환의 길이는 n/\gcd\\{n,k\\}이다. * 후자의 길이가 7 이하가 되려면, 가능한 경우는 n/k\in\\{3/1, 4/1, 5/1, 5/2, 6/1, 7/1, 7/2, 7/3\\}이다.

## 케일리 그래프
대칭군 \operatorname{Sym}(4)의 케일리 그래프이다.]] 일반화 페테르센 그래프 \operatorname{GPG}(n,k)에 대하여, 다음 두 조건이 서로 동치이다.언어=en * 어떤 유한군의 케일리 그래프와 동형이다. * k^2\equiv1\pmod n 예를 들어, 나우루 그래프 \operatorname{GPG}(12,5)의 경우 5^2\equiv 1\pmod{12}이며, 이는 대칭군 \operatorname{Sym}(4)의 케일리 그래프이다. 마찬가지로, 각기둥 그래프 \operatorname{GPG}(n,1)는 크기 2n의 정이면체군 \operatorname{Dih}(n)의 케일리 그래프이다. 반면, 페테르센 그래프 \operatorname{GPG}(5,2)는 케일리 그래프가 아니다.
## 꼭짓점 색칠
일반화 페테르센 그래프는 삼차 그래프이므로, 브룩스 정리(Brooks’ theorem)에 의하여 그 색칠수는 2 또는 3이다. 일반화 페테르센 그래프 \operatorname{GPG}(n,k)에 대하여, 다음 두 조건이 서로 동치이다. * 이분 그래프이다. (즉, 색칠수가 2이다.) * n이 짝수이며, k는 홀수이다. 다시 말해, 일반화 페테르센 그래프 \operatorname{GPG}(n,k)의 색칠수는 다음과 같다. :\chi(\operatorname{GPG}(n,k))=\begin{cases} 2&2\mid n \land 2\nmid k\\\ 3&2\nmid n \lor 2\mid k \end{cases} 여기서 \land는 논리곱(AND), \lor는 논리합(OR)이다. 예를 들어, 페테르센 그래프 \operatorname{GPG}(5,2)의 색칠수는 3이다. 그래프 \operatorname{GPG}(5,2)의 3색 그래프 색칠 Desargues graph 그래프 \operatorname{GPG}(10,3)의 2색 그래프 색칠 Dürer graph 그래프 \operatorname{GPG}(6,2)의 3색 그래프 색칠
## 변 색칠
페테르센 그래프의 변 색칠수는 4이다.언어=en 페테르센 그래프는 변 색칠수가 4 이상인 가장 작은 삼차 그래프이다. 반면, 페테르센 그래프가 아닌 다른 모든 일반화 페테르센 그래프의 변 색칠수는 3이다.언어=en 일반화 페테르센 그래프 \operatorname{GPG}(9,2)는 (색들의 순열을 무시하면) 유일한 3색 변 색칠을 갖는다. 그래프 \operatorname{GPG}(5,2)의 4색 변 색칠 Dürer graph 3color 그래프 \operatorname{GPG}(6,2)의 3색 변 색칠 3-colored 그래프 \operatorname{GPG}(10,2)의 3색 변 색칠 Desargues graph 3color 그래프 \operatorname{GPG}(10,3)의 3색 변 색칠 Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); 그래프 \operatorname{GPG}(12,5)의 3색 변 색칠
## 해밀턴 경로
임의의 일반화 페테르센 그래프 \operatorname{GPG}(n,k) (3\le n, 1\le k)에 대하여, 다음 두 가지 가운데 정확히 하나가 성립한다.언어=en * (가) 해밀턴 순환을 갖는다. * (나) n\equiv5\pmod6이며, k\in\\{2,(n-1)/2\\}이다. 또한, (나)의 경우, 임의의 꼭짓점을 제거하면 이는 해밀턴 순환을 갖는다. (특히, 모든 일반화 페테르센 그래프는 항상 해밀턴 경로를 갖는다.) 예를 들어, 페테르센 그래프 \operatorname{GPG}(5,2)는 해밀턴 경로를 가지지만, (나)의 경우에 해당하므로 해밀턴 순환을 가지지 못한다. Dürer graph 그래프 \operatorname{GPG}(6,2) 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다. Möbius-kantor Graph 페테르센 그래프 \operatorname{GPG}(8,3) 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다. 페테르센 그래프 \operatorname{GPG}(9,2) 속의 해밀턴 순환. 해밀턴 순환에 속하는 변들은 굵게 칠해졌다. Hamiltonian 그래프 \operatorname{GPG}(10,2) 속의 해밀턴 순환. 해밀턴 순환에 속하는 변들은 붉은 색으로 굵게 칠해졌다. Nauru 그래프 \operatorname{GPG}(12,5) 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다.
## 교차수
각기둥 그래프인 일반화 페테르센 그래프 \operatorname{GPG}(n,1)은 평면 그래프이다. 즉, 그래프 교차수가 0이다. 페테르센 그래프 \operatorname{GPG}(5,2)의 그래프 교차수는 2이다. 나우루 그래프 \operatorname{GPG}(12,5)의 그래프 교차수는 8이다. 특히, 이 두 그래프 둘 다 평면 그래프가 아니다. 평면 그래프가 아닌 모든 그래프는 완전 그래프 K_5 또는 완전 이분 그래프 K_{3,3}를 그래프 마이너로 가지는데, 페테르센 그래프 \operatorname{GPG}(5,2)는 이 둘 다를 그래프 마이너로 갖는다. Pentagonal prismatic 그래프 \operatorname{GPG}(5,1)의 교차수는 0이다. Petersen graph, two 그래프 \operatorname{GPG}(5,2)의 교차수는 2이다. Nauru 1-planar 그래프 \operatorname{GPG}(12,5)의 교차수는 8이다.
# 예
일부 일반화 페테르센 그래프는 다음과 같은 특별한 이름을 갖는다. * **페테르센 그래프**는 일반화 페테르센 그래프 \operatorname{GPG}(5, 2)이다. 이는 완전 그래프 K_5의 선 그래프의 여 그래프와 동형이다. * **뒤러 그래프**(Dürer graph)는 일반화 페테르센 그래프 \operatorname{GPG}(6,2)이다. * 일반화 페테르센 그래프 \operatorname{GPG}(10,2)는 정십이면체의 꼭짓점 및 변들로 구성된 그래프와 같다. * **데자르그 그래프**(Desargues graph)는 일반화 페테르센 그래프 \operatorname{GPG}(10, 3)이다. * 일반화 페테르센 그래프 \operatorname{GPG}(n,1)는 n각형 각기둥의 꼭짓점 및 변들로 구성된 그래프와 같다. Triangular prismatic 페테르센 그래프 \operatorname{GPG}(3, 1) Cubical 페테르센 그래프 (정육면체 그래프) \operatorname{GPG}(4, 1) Pentagonal prismatic 페테르센 그래프 \operatorname{GPG}(5, 1) Petersen 그래프 \operatorname{GPG}(5, 2) Hexagonal prismatic 페테르센 그래프 \operatorname{GPG}(6, 1) 그래프 \operatorname{GPG}(6,2) Heptagonal prismatic 페테르센 그래프 \operatorname{GPG}(7, 1) Octagonal prismatic 페테르센 그래프 \operatorname{GPG}(8, 1) Dodecahedral 그래프 \operatorname{GPG}(10,2) 그래프 \operatorname{GPG}(10,3) Independent set 페테르센 그래프 \operatorname{GPG}(12,4) 파일:Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); 그래프 \operatorname{GPG}(12,5)
# 역사
알브레히트 뒤러의 판화 《멜란콜리아 1》 데자르그의 정리에 등장하는 작도. 10개의 점 (A,B,C,A',B',C',P,Q,R,S)와 10개의 직선 (a,b,c,a',b',c',p,q,r,s)에 각각 어떤 그래프의 꼭짓점을 대응시키고, 인접하는 점과 직선에 대응하는 두 꼭짓점 사이를 변으로 이으면, 데자르그 그래프 \operatorname{GPG}(10,3)를 얻는다. 나우루의 국기 독일의 판화가 알브레히트 뒤러의 1514년 판화 《멜란콜리아 1》(Melancholia Ⅰ)에는 다면체가 등장하는데, 그 꼭짓점과 변으로 구성된 그래프는 뒤러 그래프이다. 1898년에 덴마크의 수학자 율리우스 페테르센이 이 그래프를 다룬 3쪽의 논문을 출판하였으며,언어=fr227, Fig. 5 이로부터 명명되었다. 페테르센은 이 그래프를 다음과 같은 (잘못된) 추측에 대한 반례로 제시하였다. :연결 삼차 그래프 가운데, 임의의 변을 제거하더라도 연결 그래프로 남는 것들의 경우, 모두 변 색칠수가 3 이하이다. “데자르그 그래프”라는 이름은 프랑스의 수학자 지라르 데자르그의 이름을 딴 것이다. 데자르그가 연구한 사영기하학의 한 정리에서 등장하는 작도에서, 각 직선과 각 점에 그래프 꼭짓점을 대응시키며, 서로 인접하는 점과 직선(에 대응하는 두 꼭짓점) 사이를 변으로 이으면, 이는 데자르그 그래프가 된다. 해럴드 스콧 맥도널드 콕서터는 1950년에 일반화 페테르센 그래프를 도입하였다.언어=en418, §2 콕서터는 일반화 페테르센 그래프 \operatorname{GPG}(n,k)를 \\{n\\}+\\{n/k\\}로 표기하였으며, 이에 특별한 이름을 부여하지 않았다. 1969년에 마크 왓킨스(Mark E. Watkins)가 이 그래프 족을 “일반화 페테르센 그래프”(generalized Petersen graph)라고 명명하였다.언어=en “나우루 그래프”(Nauru graph)라는 이름은 데이비드 아서 엡스타인(David Arthur Eppstein)이 도입하였으며, 이 그래프의 구성에 등장하는 12각 별 모양이 나우루의 국기에 등장하는 별과 흡사하기 때문에 붙여졌다.