일반화 페테르센 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''일반화 페테르센 그래프'''(一般化Petersen graph, {{llang|en|generalized Petersen graph}})는 같은 수의 꼭짓점을 갖는 정다각형과 별 모양에서 대응하는 꼭짓점들을 이어 얻는 [[그래프]]이다. 특히, 오각형과 오각 별을 이어 얻는 그래프를 '''페테르센 그래프'''({{llang|en|Petersen graph}})라고 한다.<ref>{{서적 인용|first=D. A.|last=Holton|이름2=J.|성2=Sheehan|title=The Petersen graph|url=https://archive.org/details/petersengraph0000holt|publisher=Cambridge University Press|날짜=1993|isbn=0-521-43594-3|doi=10.2277/0521435943}}</ref>

== 정의 ==
3 이상의 정수 <math>n\ge3</math>과, <math>n</math>의 배수가 아닌 정수 <math>k\in\mathbb Z</math>, <math>n\nmid k</math>가 주어졌다고 하자. 또한, 만약 <math>n</math>이 짝수라면 <math>n/2\nmid k</math>라고 하자.

'''일반화 페테르센 그래프''' <math>\operatorname{GPG}(n,k)</math>는 다음과 같은 [[그래프]]이다.
:<math>\operatorname V(\operatorname{GPG}(n,k))=\{u_i,v_i\colon i\in\mathbb Z/n\}</math>
:<math>\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\}</math>
여기서 첨자는 [[합동 산술|법]] <math>n</math>으로 계산한다. 즉, <math>u_{n+i}=u_i</math> 및 <math>v_{n+i}=u_i</math>로 간주한다.
일반화 페테르센 그래프의 변 가운데, <math>u_iv_i</math> 꼴의 변을 '''바큇살'''({{llang|en|spoke}})이라고 한다.

당연히
:<math>\operatorname{GPG}(n,k)=\operatorname{GPG}(n,k+n)=\operatorname{GPG}(n,-k)</math>
이므로, 보통
:<math>1\le k< n/2 </math>
를 가정한다.

== 성질 ==
=== 기초적 성질 ===
[[파일:Petersen-graph-factors.svg|섬네일|오른쪽|페테르센 그래프 <math>\operatorname{GPG}(5,2)</math> 속의 [[완벽 부합]]]]
일반화 페테르센 그래프 <math>\operatorname{GPG}(n,k)</math>는 <math>2n</math>개의 꼭짓점과 <math>3n</math>개의 변을 가지는 [[삼차 그래프]]이며, [[완벽 부합]]을 갖는다. 구체적으로, 위와 같은 표기에서, <math>\{u_iv_i\}_{i\in\mathbb Z/n}</math>은 [[완벽 부합]]을 이룬다.

=== 동형 ===
임의의 정수 <math>n\ge3</math> 및 정수 <math>1\le k,k'<n/2</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.<ref>{{저널 인용 | url=http://preprinti.imfm.si/PDF/00939.pdf | 이름=Marko | 성=Boben | 이름2=Tomaž | 성2=Pisanski | 이름3=Arjana | 성3=Žitni | 제목=I-graphs and the corresponding configurations | doi=10.1002/jcd.20054 | 날짜=2005-11 | 권=13 | 호=6 | 쪽=406–424 | 저널=Journal of Combinatorial Designs | 언어=en | access-date=2017-07-05 | archive-date=2018-07-23 | archive-url=https://web.archive.org/web/20180723051628/http://preprinti.imfm.si/PDF/00939.pdf | url-status= }}</ref>{{rp|Proposition 9}}<ref>{{저널 인용 | 제목 = The isomorphism classes of the generalized Petersen graphs | doi=10.1016/j.disc.2007.12.074 | 이름=Alice | 성=Steimle | 이름2=William | 성2= Staton | 저널=Discrete Mathematics |권= 309|호= 1|날짜=2009-01-06|쪽=231–237 | 언어=en}}</ref>
* <math>\operatorname{GPG}(n,k)\cong\operatorname{GPG}(n,k')</math>
* <math> kk' \equiv \pm1 \pmod n </math>
예를 들어, <math>\operatorname{GPG}(7,2)\cong\operatorname{GPG}(7,3)</math>이다.

=== 안둘레 ===
일반화 페테르센 그래프 <math>\operatorname{GPG}(n,k)</math>의 [[안둘레]]는 항상 <math>\min\{8,k+3,n/\gcd\{n,k\}\}</math> 이하이다.<ref name="FH">{{저널 인용 | url=http://danielaferrero.wp.txstate.edu/files/2015/03/Component-connectivity-generalized-Petersen-graphs.pdf | doi=10.1080/00207160.2013.878023 | 저널=International Journal of Computer Mathematics | 이름=Daniela | 성=Ferrero | 이름2=Sarah | 성2=Hanusch | 쪽=1940–1963 | 권=91 | 호=9 | 날짜=2014 | 제목=Component connectivity of generalized Petersen graphs | issn=0020-7160 | 언어=en | 확인날짜=2017-07-05 | 보존url=https://web.archive.org/web/20181020182041/http://danielaferrero.wp.txstate.edu/files/2015/03/Component-connectivity-generalized-Petersen-graphs.pdf | 보존날짜=2018-10-20 | url-status=dead }}</ref>{{rp|Theorem 2.1}}
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
일반화 페테르센 그래프의 꼭짓점 및 변은
:<math>\operatorname V(\operatorname{GPG}(n,k))=\{u_i,v_i\colon i\in\mathbb Z/n\}</math>
:<math>\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\}</math>
이다. 그 속에서
:<math>u_0 - v_0 - v_k - u_k - u_{k+1} - v_{k+1} - v_1 - u_1 - u_0</math>
는 길이 8의 [[순환 (그래프 이론)|순환]]이며,
:<math>u_0 - v_0 - v_k - u_k - u_{k-1} - \dotsb - u_1 - u_0</math>
는 길이 <math>k+3</math>의 [[순환 (그래프 이론)|순환]]이며,
:<math>v_0 - v_k - v_{2k} - \dotsb - v_0</math>
는 길이 <math>n/\gcd\{n,k\}</math>의 [[순환 (그래프 이론)|순환]]이다.
</div>
</div>

또한, 다음이 성립한다.
:<math>\operatorname{girth}(\operatorname{GPG}(ak\pm b,k))
\le a+b+2
</math>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
일반화 페테르센 그래프의 꼭짓점 및 변은
:<math>\operatorname V(\operatorname{GPG}(n,k))=\{u_i,v_i\colon i\in\mathbb Z/n\}</math>
:<math>\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\}</math>
이다. 그 속에서
:<math>u_0-v_0-v_k-\dotsb-v_{ak\equiv\pm b}-u_{\pm b}-u_{\pm(b-1)}-\dotsb-u_{\pm1}-u_0</math>
은 길이 <math>a+b+2</math>의 순환이다 ([[복부호 동순]]).
</div></div>

위 상계 가운데 적어도 하나가 포화된다. 즉, 만약 <math>1\le k<n/2</math>이며,
:<math>k=\min\left\{1\le k'<n/2\colon \operatorname{GPG}(n,k)\cong\operatorname{GPG}(n,k')\right\}</math>
일 때, 일반화 페테르센 그래프 <math>\operatorname{GPG}(n,k)</math>의 [[안둘레]]는 다음 표에서, 위에서부터 가장 먼저 해당하는 행에 의해 주어진다.<ref name="FH"/>{{rp|Theorem 2.8}}
:{| class=wikitable style="text-align: center"
! 조건 || [[안둘레]]
|-
| <math>n=3k</math> || 3
|-
| <math>n=4k</math>
| rowspan=2 | 4
|-
| <math>k=1</math>
|-
| <math>n=5k</math>
| rowspan=3 | 5
|-
| <math>n=5k/2</math>
|-
| <math>k=2</math>
|-
| <math>n=6k</math>
| rowspan=3 | 6
|-
| <math>k=3</math>
|-
| <math>n=2k+2</math>
|-
| <math>n=7k</math>
| rowspan=6 | 7
|-
| <math>n=7k/2</math>
|-
| <math>n=7k/3</math>
|-
| <math>k=4</math>
|-
| <math>n=2k+3</math>
|-
| <math>n=3k\pm2</math>
|-
| 그 밖의 경우 || 8
|}
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
일반화 페테르센 그래프의 꼭짓점 및 변은
:<math>\operatorname V(\operatorname{GPG}(n,k))=\{u_i,v_i\colon i\in\mathbb Z/n\}</math>
:<math>\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\}</math>
이다. 일반화 페테르센 그래프 속의 모든 [[순환 (그래프 이론)|순환]]은 당연히 짝수 개의 바큇살 <math>u_iv_i</math>을 포함한다.

모든 일반화 페테르센 그래프는 4개의 바큇살을 갖는 길이 8의 [[순환 (그래프 이론)|순환]]
:<math>u_0 - v_0 - v_k - u_k - u_{k+1} - v_{k+1} - v_1 - u_1 - u_0</math>
을 가지며, 바큇살 6개 이상의 순환의 길이는 항상 12 이상이다. 따라서, 2개의 바큇살 및 0개의 바큇살을 갖는 순환들만 고려하면 된다.

2개의 바큇살을 갖는 순환은 (편의상 첫 변을 <math>u_0-u_1</math>로 잡으면) 항상 다음과 같은 꼴이다.
:<math>u_0-u_1-\dotsb-u_b-v_b-v_{b\pm k}-v_{b\pm 2k}-\dotsb-v_{b\pm ak}-u_0</math>
이것이 존재하기 위해서는 <math>ak\pm b\mid n</math>이어야 하며, 이 경우 순환의 길이는 <math>a+b+2</math>이다.
* <math>k</math>가 최솟값이어야 하므로, <math>ak+b=n</math> 및 <math>ak+b=0</math>인 경우만 고려해도 된다.
** <math>ak+b=0</math>인 경우: <math>(a,b)=(1,-k)</math>인 경우가 최적이며, 이 경우 순환의 길이는 <math>k+3</math>이다.
** <math>ak+b=n</math>인 경우:
*** 만약 <math>n=ak\pm1</math>인 경우, <math>\operatorname{GPG}(n,k)\cong\operatorname{GPG}(n,a)</math>이다. 따라서, 이 경우 <math>k</math>는 최솟값을 갖지 못한다.
*** 만약 <math>n=ak</math>일 경우, 이 경우 0개의 바큇살을 갖는 길이 <math>a</math>의 순환이 더 짧다.
*** 만약 <math>n=2k-b</math>일 경우, <math>k\ge n/2</math>이다.
*** 위 경우를 제외하면, 이러한 순환의 길이가 8 미만인 경우는 남는 것은 <math>(a,b)=(2,2), (2,3), (3,2), (3,-2)</math>이다.

0개의 바큇살을 갖는 순환은 <math>u_i</math> 또는 <Math>v_i</math>로만 구성된다. <math>u_i</math>만으로 구성되는 유일한 순환의 길이는 <math>n</math>이며, <math>v_i</math>만으로 구성되는 순환의 길이는 <math>n/\gcd\{n,k\}</math>이다.
* 후자의 길이가 7 이하가 되려면, 가능한 경우는 <math>n/k\in\{3/1, 4/1, 5/1, 5/2, 6/1, 7/1, 7/2, 7/3\}</math>이다.
</div></div>

=== 케일리 그래프 ===
[[파일:Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen).svg|섬네일|오른쪽|나우루 그래프 <math>\operatorname{GPG}(12,5)</math>는 [[대칭군 (군론)|대칭군]] <math>\operatorname{Sym}(4)</math>의 [[케일리 그래프]]이다.]]
일반화 페테르센 그래프 <math>\operatorname{GPG}(n,k)</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.<ref>{{저널 인용|제목=Which generalized petersen graphs are Cayley graphs?|url=https://archive.org/details/sim_journal-of-graph-theory_1995-01_19_1/page/n4|이름=Roman|성=Nedela|이름2=Martin|성2=Škoviera|저널=Journal of Graph Theory|권=19|호=1|날짜=1995-01|쪽=1–11|doi=10.1002/jgt.3190190102|언어=en}}</ref>
* 어떤 [[유한군]]의 [[케일리 그래프]]와 동형이다.
* <math>k^2\equiv1\pmod n</math>
예를 들어, 나우루 그래프 <math>\operatorname{GPG}(12,5)</math>의 경우 <math>5^2\equiv 1\pmod{12}</math>이며, 이는 [[대칭군 (군론)|대칭군]] <math>\operatorname{Sym}(4)</math>의 [[케일리 그래프]]이다. 마찬가지로, [[각기둥]] 그래프 <math>\operatorname{GPG}(n,1)</math>는 크기 <math>2n</math>의 [[정이면체군]] <math>\operatorname{Dih}(n)</math>의 [[케일리 그래프]]이다. 반면, 페테르센 그래프 <math>\operatorname{GPG}(5,2)</math>는 [[케일리 그래프]]가 아니다.

=== 꼭짓점 색칠 ===
일반화 페테르센 그래프는 [[삼차 그래프]]이므로, 브룩스 정리({{llang|en|Brooks’ theorem}})에 의하여 그 [[색칠수]]는 2 또는 3이다.
일반화 페테르센 그래프 <math>\operatorname{GPG}(n,k)</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* [[이분 그래프]]이다. (즉, [[색칠수]]가 2이다.)
* <math>n</math>이 짝수이며, <Math>k</math>는 홀수이다.
다시 말해, 일반화 페테르센 그래프 <math>\operatorname{GPG}(n,k)</math>의 [[색칠수]]는 다음과 같다.
:<math>\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}</math>
여기서 <math>\land</math>는 [[논리곱]](AND), <math>\lor</math>는 [[논리합]](OR)이다. 예를 들어, 페테르센 그래프 <math>\operatorname{GPG}(5,2)</math>의 [[색칠수]]는 3이다.
<gallery>
Petersen_graph_3-coloring.svg|페테르센 그래프 <math>\operatorname{GPG}(5,2)</math>의 3색 [[그래프 색칠]]
Desargues graph 2COL.svg|데자르그 그래프 <math>\operatorname{GPG}(10,3)</math>의 2색 [[그래프 색칠]]
Dürer graph 3COL.svg|뒤러 그래프 <math>\operatorname{GPG}(6,2)</math>의 3색 [[그래프 색칠]]
</gallery>

=== 변 색칠 ===
페테르센 그래프의 [[변 색칠수]]는 4이다.<ref>{{저널 인용|제목=The Petersen graph is not 3-edge-colorable—a new proof|이름=Reza|성=Naserasr|이름2=Riste|성2=Škrekovski|doi=10.1016/S0012-365X(03)00138-9|저널=Discrete Mathematics|권=268|호=1–3|날짜=2003-07-06|쪽=325–326|언어=en}}</ref> 페테르센 그래프는 [[변 색칠수]]가 4 이상인 가장 작은 [[삼차 그래프]]이다. 반면, 페테르센 그래프가 아닌 다른 모든 일반화 페테르센 그래프의 [[변 색칠수]]는 3이다.<ref>{{저널 인용
 | last1 = Castagna | first1 = Frank
 | last2 = Prins | first2 = Geert Caleb Ernst
 | journal = Pacific Journal of Mathematics
 | title = Every generalized Petersen graph has a Tait coloring
 | volume = 40 | 호=1
 | year = 1972
 | doi = 10.2140/pjm.1972.40.53|issn=0030-8730|mr=304223|zbl=0236.05106|언어=en }}</ref>

일반화 페테르센 그래프 <math>\operatorname{GPG}(9,2)</math>는 (색들의 [[순열]]을 무시하면) 유일한 3색 [[변 색칠]]을 갖는다.

<gallery>
PetersenBarveniHran.svg|페테르센 그래프 <math>\operatorname{GPG}(5,2)</math>의 4색 [[변 색칠]]
Dürer graph 3color edge.svg|뒤러 그래프 <math>\operatorname{GPG}(6,2)</math>의 3색 [[변 색칠]]
3-colored dodecahedron.svg|정십이면체 그래프 <math>\operatorname{GPG}(10,2)</math>의 3색 [[변 색칠]]
Desargues graph 3color edge.svg|데자르그 그래프 <math>\operatorname{GPG}(10,3)</math>의 3색 [[변 색칠]]
Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); matrices.svg|나우루 그래프 <math>\operatorname{GPG}(12,5)</math>의 3색 [[변 색칠]]
</gallery>

=== 해밀턴 경로 ===
임의의 일반화 페테르센 그래프 <math>\operatorname{GPG}(n,k)</math> (<math>3\le n</math>, <math>1\le k<n/2</math>)에 대하여, 다음 두 가지 가운데 정확히 하나가 성립한다.<ref>{{저널 인용
 | last = Alspach | first = Brian R.
 | doi = 10.1016/0095-8956(83)90042-4
 | mr = 0714452
 | journal = Journal of Combinatorial Theory B
 | pages = 293–312
 | 제목 = The classification of Hamiltonian generalized Petersen graphs
 | 권 = 34
 | 날짜 = 1983 | 언어=en}}</ref>
* (가) [[해밀턴 순환]]을 갖는다.
* (나) <math>n\equiv5\pmod6</math>이며, <math>k\in\{2,(n-1)/2\}</math>이다.
또한, (나)의 경우, 임의의 꼭짓점을 제거하면 이는 [[해밀턴 순환]]을 갖는다. (특히, 모든 일반화 페테르센 그래프는 항상 [[해밀턴 경로]]를 갖는다.)

예를 들어, 페테르센 그래프 <math>\operatorname{GPG}(5,2)</math>는 [[해밀턴 경로]]를 가지지만, (나)의 경우에 해당하므로 [[해밀턴 순환]]을 가지지 못한다.

<gallery>
Dürer graph hamiltonicity.svg|뒤러 그래프 <math>\operatorname{GPG}(6,2)</math> 속의 [[해밀턴 순환]]. 맨 밖의 변들이 [[해밀턴 순환]]을 이룬다.
Möbius-kantor Graph hamiltonian.png|일반화 페테르센 그래프 <math>\operatorname{GPG}(8,3)</math> 속의 [[해밀턴 순환]]. 맨 밖의 변들이 [[해밀턴 순환]]을 이룬다.
Generalized_Petersen_9_2_Hamiltonicity.svg|일반화 페테르센 그래프 <math>\operatorname{GPG}(9,2)</math> 속의 [[해밀턴 순환]]. 해밀턴 순환에 속하는 변들은 굵게 칠해졌다.
Hamiltonian path.svg|정십이면체 그래프 <math>\operatorname{GPG}(10,2)</math> 속의 [[해밀턴 순환]]. 해밀턴 순환에 속하는 변들은 붉은 색으로 굵게 칠해졌다.
Nauru graph.svg|나우루 그래프 <math>\operatorname{GPG}(12,5)</math> 속의 [[해밀턴 순환]]. 맨 밖의 변들이 [[해밀턴 순환]]을 이룬다.
</gallery>

=== 교차수 ===
[[각기둥]] 그래프인 일반화 페테르센 그래프 <math>\operatorname{GPG}(n,1)</math>은 [[평면 그래프]]이다. 즉, [[그래프 교차수]]가 0이다.

페테르센 그래프 <math>\operatorname{GPG}(5,2)</math>의 [[그래프 교차수]]는 2이다. 나우루 그래프 <math>\operatorname{GPG}(12,5)</math>의 [[그래프 교차수]]는 8이다. 특히, 이 두 그래프 둘 다 [[평면 그래프]]가 아니다.

[[평면 그래프]]가 아닌 모든 그래프는 [[완전 그래프]] <math>K_5</math> 또는 [[완전 이분 그래프]] <math>K_{3,3}</math>를 [[그래프 마이너]]로 가지는데, 페테르센 그래프 <math>\operatorname{GPG}(5,2)</math>는 이 둘 다를 [[그래프 마이너]]로 갖는다.
<gallery>
Pentagonal prismatic graph.svg|오각기둥 그래프 <math>\operatorname{GPG}(5,1)</math>의 교차수는 0이다.
Petersen graph, two crossings.svg|페테르센 그래프 <math>\operatorname{GPG}(5,2)</math>의 교차수는 2이다.
Nauru 1-planar 8-crossing.svg|나우루 그래프 <math>\operatorname{GPG}(12,5)</math>의 교차수는 8이다.
</gallery>

== 예 ==
일부 일반화 페테르센 그래프는 다음과 같은 특별한 이름을 갖는다.
* '''페테르센 그래프'''는 일반화 페테르센 그래프 <math>\operatorname{GPG}(5, 2)</math>이다. 이는 [[완전 그래프]] <math>K_5</math>의 [[선 그래프]]의 [[여 그래프]]와 동형이다.
* '''뒤러 그래프'''({{llang|en|Dürer graph}})는 일반화 페테르센 그래프 <math>\operatorname{GPG}(6,2)</math>이다.
* 일반화 페테르센 그래프 <math>\operatorname{GPG}(10,2)</math>는 [[정십이면체]]의 꼭짓점 및 변들로 구성된 그래프와 같다.
* '''데자르그 그래프'''({{llang|en|Desargues graph}})는 일반화 페테르센 그래프 <math>\operatorname{GPG}(10, 3)</math>이다.
* 일반화 페테르센 그래프 <math>\operatorname{GPG}(n,1)</math>는 <math>n</math>각형 [[각기둥]]의 꼭짓점 및 변들로 구성된 그래프와 같다.
<gallery>
Triangular prismatic graph.svg|일반화 페테르센 그래프 <math>\operatorname{GPG}(3, 1)</math>
Cubical graph.svg|일반화 페테르센 그래프 (정육면체 그래프) <math>\operatorname{GPG}(4, 1)</math>
Pentagonal prismatic graph.svg|일반화 페테르센 그래프 <math>\operatorname{GPG}(5, 1)</math>
Petersen graph.svg|페테르센 그래프 <math>\operatorname{GPG}(5, 2)</math>
Hexagonal prismatic graph.svg|일반화 페테르센 그래프 <math>\operatorname{GPG}(6, 1)</math>
Dürer_graph.svg|뒤러 그래프 <math>\operatorname{GPG}(6,2)</math>
Heptagonal prismatic graph.svg|일반화 페테르센 그래프 <math>\operatorname{GPG}(7, 1)</math>
Octagonal prismatic graph.svg|일반화 페테르센 그래프 <math>\operatorname{GPG}(8, 1)</math>
Dodecahedral graph.neato.svg|[[정십이면체]] 그래프 <math>\operatorname{GPG}(10,2)</math>
DesarguesGraph.svg|데자르그 그래프 <math>\operatorname{GPG}(10,3)</math>
Independent set graph.svg|일반화 페테르센 그래프 <math>\operatorname{GPG}(12,4)</math>
파일:Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg|나우루 그래프 <math>\operatorname{GPG}(12,5)</math>
</gallery>

== 역사 ==
[[파일:Dürer_Melancholia_I.jpg|섬네일|오른쪽|[[알브레히트 뒤러]]의 판화 《멜란콜리아 1》]]
[[파일:Desargues theorem ter.svg|섬네일|오른쪽|데자르그의 정리에 등장하는 작도. 10개의 점 <math>(A,B,C,A',B',C',P,Q,R,S)</math>와 10개의 직선 <math>(a,b,c,a',b',c',p,q,r,s)</math>에 각각 어떤 그래프의 꼭짓점을 대응시키고, 인접하는 점과 직선에 대응하는 두 꼭짓점 사이를 변으로 이으면, 데자르그 그래프 <Math>\operatorname{GPG}(10,3)</math>를 얻는다.]]
[[파일:Flag_of_Nauru.svg|섬네일|오른쪽|[[나우루의 국기]]]]
독일의 판화가 [[알브레히트 뒤러]]의 1514년 [[판화]] 《멜란콜리아 1》({{llang|de|Melancholia Ⅰ}})에는 [[다면체]]가 등장하는데, 그 꼭짓점과 변으로 구성된 [[그래프]]는 뒤러 그래프이다.

1898년에 덴마크의 수학자 [[율리우스 페테르센]]이 이 그래프를 다룬 3쪽의 논문을 출판하였으며,<ref>{{저널 인용|first=Julius Peter Christian|last=Petersen|저자링크=율리우스 페테르센|title=Sur le théorème de Tait|journal=L’Intermédiaire des Mathématiciens|volume=5|날짜=1898|pages=225–227|url=https://babel.hathitrust.org/cgi/pt?id=mdp.39015069418591;view=1up;seq=241|언어=fr}}</ref>{{rp|227, Fig. 5}} 이로부터 명명되었다. 페테르센은 이 그래프를 다음과 같은 (잘못된) 추측에 대한 반례로 제시하였다.
:[[연결 그래프|연결]] [[삼차 그래프]] 가운데, 임의의 변을 제거하더라도 [[연결 그래프]]로 남는 것들의 경우, 모두 [[변 색칠수]]가 3 이하이다.

“데자르그 그래프”라는 이름은 프랑스의 수학자 [[지라르 데자르그]]의 이름을 딴 것이다. 데자르그가 연구한 [[사영기하학]]의 한 정리에서 등장하는 작도에서, 각 직선과 각 점에 그래프 꼭짓점을 대응시키며, 서로 인접하는 점과 직선(에 대응하는 두 꼭짓점) 사이를 변으로 이으면, 이는 데자르그 그래프가 된다.

[[해럴드 스콧 맥도널드 콕서터]]는 1950년에 일반화 페테르센 그래프를 도입하였다.<ref>{{저널 인용
 | first = Harold Scott MacDonald | last = Coxeter | 저자링크=해럴드 스콧 맥도널드 콕서터
 | title = Self-dual configurations and regular graphs
 | journal = Bulletin of the American Mathematical Society
 | volume = 56 | 날짜 = 1950 | pages = 413–455
 | doi = 10.1090/S0002-9904-1950-09407-5
 | issue = 5 | 언어=en}}</ref>{{rp|418, §2}} 콕서터는 일반화 페테르센 그래프 <math>\operatorname{GPG}(n,k)</math>를 <math>\{n\}+\{n/k\}</math>로 표기하였으며, 이에 특별한 이름을 부여하지 않았다.

1969년에 마크 왓킨스({{llang|en|Mark E. Watkins}})가 이 그래프 족을 “일반화 페테르센 그래프”({{llang|en|generalized Petersen graph}})라고 명명하였다.<ref>{{저널 인용
 | last = Watkins | first = Mark E.
 | doi = 10.1016/S0021-9800(69)80116-X
 | journal = Journal of Combinatorial Theory
 | pages = 152–164
 | title = A theorem on Tait colorings with an application to the generalized Petersen graphs
 | volume = 6
 | year = 1969 | 언어=en}}</ref>

“나우루 그래프”({{llang|en|Nauru graph}})라는 이름은 데이비드 아서 엡스타인({{llang|en|David Arthur Eppstein}})이 도입하였으며, 이 그래프의 구성에 등장하는 12각 별 모양이 [[나우루의 국기]]에 등장하는 별과 흡사하기 때문에 붙여졌다.

== 각주 ==
{{각주}}

== 외부 링크 ==
{{위키공용분류|Generalized Petersen graph|일반화 페테르센 그래프}}
{{위키공용분류|Petersen graph|페테르센 그래프}}
{{위키공용분류|Desargues graph|데자르그 그래프}}
{{위키공용분류|Nauru graph|나우루 그래프}}
* {{eom|title=Petersen graph}}
* {{매스월드|id=GeneralizedPetersenGraph|title=Generalized Petersen graph}}
* {{매스월드|id=PetersenGraph|title=Petersen graph}}
* {{매스월드|id=DesarguesGraph|title=Desargues graph}}
* {{매스월드|id=NauruGraph|title=Nauru graph}}
* {{매스월드|id=DuererGraph|title=Dürer graph}}
* {{매스월드|id=Moebius-KantorGraph|title=Möbius–Kantor graph}}
* {{매스월드|id=DodecahedralGraph|title=Dodecahedral graph}}
* {{매스월드|id=PrismGraph|title=Prism graph}}
* {{웹 인용|url=https://11011110.github.io/blog/2007/12/12/many-faces-of.html | 제목=The many faces of the Nauru graph|이름=David Arthur|성=Eppstein|날짜=2007-12-12|웹사이트=11011110|언어=en}}
* {{웹 인용|url=https://www.famnit.upr.si/files/files/seminarji/Koper%20Seminar-Ted%20Dobson.pdf | 이름=Edward | 성=Dobson | 제목=The isomorphism classes of all generalized Petersen graphs | 날짜=2011-05-09 | 기타= 프리모르스카 대학교({{llang|sl|Univerza na Primorskem}}) 세미나 | 언어=en}}

[[분류:그래프]]
[[분류:정규 그래프]]