일반화 페테르센 그래프

틀:위키데이터 속성 추적 그래프 이론에서 일반화 페테르센 그래프(一般化Petersen graph, 틀:Llang)는 같은 수의 꼭짓점을 갖는 정다각형과 별 모양에서 대응하는 꼭짓점들을 이어 얻는 그래프이다. 특히, 오각형과 오각 별을 이어 얻는 그래프를 페테르센 그래프(틀:Llang)라고 한다.^[1]

정의

3 이상의 정수 $n \geq 3$ 과, $n$ 의 배수가 아닌 정수 $k \in ℤ$ , $n ∤ k$ 가 주어졌다고 하자. 또한, 만약 $n$ 이 짝수라면 $n / 2 ∤ k$ 라고 하자.

일반화 페테르센 그래프 $GPG (n, k)$ 는 다음과 같은 그래프이다.

V (GPG (n, k)) = {u_{i}, v_{i} : i \in ℤ / n}

E (GPG (n, k)) = {u_{i} u_{i + 1}, u_{i} v_{i}, v_{i} v_{i + k} : i \in ℤ / n}

여기서 첨자는 법 $n$ 으로 계산한다. 즉, $u_{n + i} = u_{i}$ 및 $v_{n + i} = u_{i}$ 로 간주한다. 일반화 페테르센 그래프의 변 가운데, $u_{i} v_{i}$ 꼴의 변을 바큇살(틀:Llang)이라고 한다.

당연히

GPG (n, k) = GPG (n, k + n) = GPG (n, - k)

이므로, 보통

1 \leq k < n / 2

를 가정한다.

성질

기초적 성질

일반화 페테르센 그래프 $GPG (n, k)$ 는 $2 n$ 개의 꼭짓점과 $3 n$ 개의 변을 가지는 삼차 그래프이며, 완벽 부합을 갖는다. 구체적으로, 위와 같은 표기에서, ${u_{i} v_{i}}_{i \in ℤ / n}$ 은 완벽 부합을 이룬다.

동형

임의의 정수 $n \geq 3$ 및 정수 $1 \leq k, k^{'} < n / 2$ 에 대하여, 다음 두 조건이 서로 동치이다.^[2]틀:Rp^[3]

$GPG (n, k) ≅ GPG (n, k^{'})$
$k k^{'} \equiv \pm 1 (\mod n)$

예를 들어, $GPG (7, 2) ≅ GPG (7, 3)$ 이다.

안둘레

일반화 페테르센 그래프 $GPG (n, k)$ 의 안둘레는 항상 $\min {8, k + 3, n / \gcd {n, k}}$ 이하이다.^[4]틀:Rp

증명:

일반화 페테르센 그래프의 꼭짓점 및 변은

V (GPG (n, k)) = {u_{i}, v_{i} : i \in ℤ / n}

E (GPG (n, k)) = {u_{i} u_{i + 1}, u_{i} v_{i}, v_{i} v_{i + k} : i \in ℤ / 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} - \dots - u_{1} - u_{0}

는 길이 $k + 3$ 의 순환이며,

v_{0} - v_{k} - v_{2 k} - \dots - v_{0}

는 길이 $n / \gcd {n, k}$ 의 순환이다.

또한, 다음이 성립한다.

girth (GPG (a k \pm b, k)) \leq a + b + 2

증명:

일반화 페테르센 그래프의 꼭짓점 및 변은

V (GPG (n, k)) = {u_{i}, v_{i} : i \in ℤ / n}

E (GPG (n, k)) = {u_{i} u_{i + 1}, u_{i} v_{i}, v_{i} v_{i + k} : i \in ℤ / n}

이다. 그 속에서

u_{0} - v_{0} - v_{k} - \dots - v_{a k \equiv \pm b} - u_{\pm b} - u_{\pm (b - 1)} - \dots - u_{\pm 1} - u_{0}

은 길이 $a + b + 2$ 의 순환이다 (복부호 동순).

위 상계 가운데 적어도 하나가 포화된다. 즉, 만약 $1 \leq k < n / 2$ 이며,

k = \min {1 \leq k^{'} < n / 2 : GPG (n, k) ≅ GPG (n, k^{'})}

일 때, 일반화 페테르센 그래프 $GPG (n, k)$ 의 안둘레는 다음 표에서, 위에서부터 가장 먼저 해당하는 행에 의해 주어진다.^[4]틀:Rp

조건	안둘레
$n = 3 k$	3
$n = 4 k$	4
$k = 1$	4
$n = 5 k$	5
$n = 5 k / 2$
$k = 2$
$n = 6 k$	6
$k = 3$
$n = 2 k + 2$
$n = 7 k$	7
$n = 7 k / 2$
$n = 7 k / 3$
$k = 4$
$n = 2 k + 3$
$n = 3 k \pm 2$
그 밖의 경우	8

증명:

일반화 페테르센 그래프의 꼭짓점 및 변은

V (GPG (n, k)) = {u_{i}, v_{i} : i \in ℤ / n}

E (GPG (n, k)) = {u_{i} u_{i + 1}, u_{i} v_{i}, v_{i} v_{i + k} : i \in ℤ / n}

이다. 일반화 페테르센 그래프 속의 모든 순환은 당연히 짝수 개의 바큇살 $u_{i} v_{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} - \dots - u_{b} - v_{b} - v_{b \pm k} - v_{b \pm 2 k} - \dots - v_{b \pm a k} - u_{0}

이것이 존재하기 위해서는 $a k \pm b ∣ n$ 이어야 하며, 이 경우 순환의 길이는 $a + b + 2$ 이다.

k가 최솟값이어야 하므로, ak+b=n 및 ak+b=0인 경우만 고려해도 된다.
- $a k + b = 0$ 인 경우: $(a, b) = (1, - k)$ 인 경우가 최적이며, 이 경우 순환의 길이는 $k + 3$ 이다.
- ak+b=n인 경우:
  - 만약 $n = a k \pm 1$ 인 경우, $GPG (n, k) ≅ GPG (n, a)$ 이다. 따라서, 이 경우 $k$ 는 최솟값을 갖지 못한다.
  - 만약 $n = a k$ 일 경우, 이 경우 0개의 바큇살을 갖는 길이 $a$ 의 순환이 더 짧다.
  - 만약 $n = 2 k - b$ 일 경우, $k \geq 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}$ 이다.

케일리 그래프

일반화 페테르센 그래프 $GPG (n, k)$ 에 대하여, 다음 두 조건이 서로 동치이다.^[5]

어떤 유한군의 케일리 그래프와 동형이다.
$k^{2} \equiv 1 (\mod n)$

예를 들어, 나우루 그래프 $GPG (12, 5)$ 의 경우 $5^{2} \equiv 1 (\mod 12)$ 이며, 이는 대칭군 $Sym (4)$ 의 케일리 그래프이다. 마찬가지로, 각기둥 그래프 $GPG (n, 1)$ 는 크기 $2 n$ 의 정이면체군 $Dih (n)$ 의 케일리 그래프이다. 반면, 페테르센 그래프 $GPG (5, 2)$ 는 케일리 그래프가 아니다.

꼭짓점 색칠

일반화 페테르센 그래프는 삼차 그래프이므로, 브룩스 정리(틀:Llang)에 의하여 그 색칠수는 2 또는 3이다. 일반화 페테르센 그래프 $GPG (n, k)$ 에 대하여, 다음 두 조건이 서로 동치이다.

이분 그래프이다. (즉, 색칠수가 2이다.)
$n$ 이 짝수이며, $k$ 는 홀수이다.

다시 말해, 일반화 페테르센 그래프 $GPG (n, k)$ 의 색칠수는 다음과 같다.

χ (GPG (n, k)) = {\begin{matrix} 2 & 2 ∣ n \land 2 ∤ k \\ 3 & 2 ∤ n \lor 2 ∣ k \end{matrix}

여기서 $\land$ 는 논리곱(AND), $\lor$ 는 논리합(OR)이다. 예를 들어, 페테르센 그래프 $GPG (5, 2)$ 의 색칠수는 3이다.

페테르센 그래프 $GPG (5, 2)$ 의 3색 그래프 색칠
데자르그 그래프 $GPG (10, 3)$ 의 2색 그래프 색칠
뒤러 그래프 $GPG (6, 2)$ 의 3색 그래프 색칠

변 색칠

페테르센 그래프의 변 색칠수는 4이다.^[6] 페테르센 그래프는 변 색칠수가 4 이상인 가장 작은 삼차 그래프이다. 반면, 페테르센 그래프가 아닌 다른 모든 일반화 페테르센 그래프의 변 색칠수는 3이다.^[7]

일반화 페테르센 그래프 $GPG (9, 2)$ 는 (색들의 순열을 무시하면) 유일한 3색 변 색칠을 갖는다.

페테르센 그래프 $GPG (5, 2)$ 의 4색 변 색칠
뒤러 그래프 $GPG (6, 2)$ 의 3색 변 색칠
정십이면체 그래프 $GPG (10, 2)$ 의 3색 변 색칠
데자르그 그래프 $GPG (10, 3)$ 의 3색 변 색칠
나우루 그래프 $GPG (12, 5)$ 의 3색 변 색칠

해밀턴 경로

임의의 일반화 페테르센 그래프 $GPG (n, k)$ ( $3 \leq n$ , $1 \leq k < n / 2$ )에 대하여, 다음 두 가지 가운데 정확히 하나가 성립한다.^[8]

(가) 해밀턴 순환을 갖는다.
(나) $n \equiv 5 (\mod 6)$ 이며, $k \in {2, (n - 1) / 2}$ 이다.

또한, (나)의 경우, 임의의 꼭짓점을 제거하면 이는 해밀턴 순환을 갖는다. (특히, 모든 일반화 페테르센 그래프는 항상 해밀턴 경로를 갖는다.)

예를 들어, 페테르센 그래프 $GPG (5, 2)$ 는 해밀턴 경로를 가지지만, (나)의 경우에 해당하므로 해밀턴 순환을 가지지 못한다.

뒤러 그래프 $GPG (6, 2)$ 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다.
일반화 페테르센 그래프 $GPG (8, 3)$ 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다.
일반화 페테르센 그래프 $GPG (9, 2)$ 속의 해밀턴 순환. 해밀턴 순환에 속하는 변들은 굵게 칠해졌다.
정십이면체 그래프 $GPG (10, 2)$ 속의 해밀턴 순환. 해밀턴 순환에 속하는 변들은 붉은 색으로 굵게 칠해졌다.
나우루 그래프 $GPG (12, 5)$ 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다.

교차수

각기둥 그래프인 일반화 페테르센 그래프 $GPG (n, 1)$ 은 평면 그래프이다. 즉, 그래프 교차수가 0이다.

페테르센 그래프 $GPG (5, 2)$ 의 그래프 교차수는 2이다. 나우루 그래프 $GPG (12, 5)$ 의 그래프 교차수는 8이다. 특히, 이 두 그래프 둘 다 평면 그래프가 아니다.

평면 그래프가 아닌 모든 그래프는 완전 그래프 $K_{5}$ 또는 완전 이분 그래프 $K_{3, 3}$ 를 그래프 마이너로 가지는데, 페테르센 그래프 $GPG (5, 2)$ 는 이 둘 다를 그래프 마이너로 갖는다.

오각기둥 그래프 $GPG (5, 1)$ 의 교차수는 0이다.
페테르센 그래프 $GPG (5, 2)$ 의 교차수는 2이다.
나우루 그래프 $GPG (12, 5)$ 의 교차수는 8이다.

예

일부 일반화 페테르센 그래프는 다음과 같은 특별한 이름을 갖는다.

페테르센 그래프는 일반화 페테르센 그래프 $GPG (5, 2)$ 이다. 이는 완전 그래프 $K_{5}$ 의 선 그래프의 여 그래프와 동형이다.
뒤러 그래프(틀:Llang)는 일반화 페테르센 그래프 $GPG (6, 2)$ 이다.
일반화 페테르센 그래프 $GPG (10, 2)$ 는 정십이면체의 꼭짓점 및 변들로 구성된 그래프와 같다.
데자르그 그래프(틀:Llang)는 일반화 페테르센 그래프 $GPG (10, 3)$ 이다.
일반화 페테르센 그래프 $GPG (n, 1)$ 는 $n$ 각형 각기둥의 꼭짓점 및 변들로 구성된 그래프와 같다.

일반화 페테르센 그래프 $GPG (3, 1)$
일반화 페테르센 그래프 (정육면체 그래프) $GPG (4, 1)$
일반화 페테르센 그래프 $GPG (5, 1)$
페테르센 그래프 $GPG (5, 2)$
일반화 페테르센 그래프 $GPG (6, 1)$
뒤러 그래프 $GPG (6, 2)$
일반화 페테르센 그래프 $GPG (7, 1)$
일반화 페테르센 그래프 $GPG (8, 1)$
정십이면체 그래프 $GPG (10, 2)$
데자르그 그래프 $GPG (10, 3)$
일반화 페테르센 그래프 $GPG (12, 4)$
나우루 그래프 $GPG (12, 5)$

역사

독일의 판화가 알브레히트 뒤러의 1514년 판화 《멜란콜리아 1》(틀:Llang)에는 다면체가 등장하는데, 그 꼭짓점과 변으로 구성된 그래프는 뒤러 그래프이다.

1898년에 덴마크의 수학자 율리우스 페테르센이 이 그래프를 다룬 3쪽의 논문을 출판하였으며,^[9]틀:Rp 이로부터 명명되었다. 페테르센은 이 그래프를 다음과 같은 (잘못된) 추측에 대한 반례로 제시하였다.

연결 삼차 그래프 가운데, 임의의 변을 제거하더라도 연결 그래프로 남는 것들의 경우, 모두 변 색칠수가 3 이하이다.

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

해럴드 스콧 맥도널드 콕서터는 1950년에 일반화 페테르센 그래프를 도입하였다.^[10]틀:Rp 콕서터는 일반화 페테르센 그래프 $GPG (n, k)$ 를 ${n} + {n / k}$ 로 표기하였으며, 이에 특별한 이름을 부여하지 않았다.

1969년에 마크 왓킨스(틀:Llang)가 이 그래프 족을 “일반화 페테르센 그래프”(틀:Llang)라고 명명하였다.^[11]

“나우루 그래프”(틀:Llang)라는 이름은 데이비드 아서 엡스타인(틀:Llang)이 도입하였으며, 이 그래프의 구성에 등장하는 12각 별 모양이 나우루의 국기에 등장하는 별과 흡사하기 때문에 붙여졌다.

각주

틀:각주

외부 링크

틀:위키공용분류 틀:위키공용분류 틀:위키공용분류 틀:위키공용분류

[1] 틀:서적 인용

[2] 틀:저널 인용

[3] 틀:저널 인용

[FH-4] 4.0 ^4.1 틀:저널 인용

[5] 틀:저널 인용

[6] 틀:저널 인용

[7] 틀:저널 인용

[8] 틀:저널 인용

[9] 틀:저널 인용

[10] 틀:저널 인용

[11] 틀:저널 인용

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

일반화 페테르센 그래프

목차

정의