그래프 그리기

그래프 이론에서 **그래프 그리기**()는 어떤 그래프 또는 다중 그래프를 어떤 곡면 위에, 변이 교차할 수 있게 표시한 것이다.

## 정의
다음이 주어졌다고 하자.
* 2차원 다양체 \Sigma
* 다중 그래프 \Gamma

다중 그래프 \Gamma의, X 속의 **그리기**는 다음 조건들을 모두 만족시키는 함수
:f\colon\Gamma\to X
이다.
* \Gamma에 CW 복합체 위상을 주었을 때, f는 연속 함수이다.
* 임의의 x\in X에 대하여, |f^{-1}(x)| \le 2 이다.
* 변의 교차점은 꼭짓점이 아니다. 즉, \{x\in X\colon |f^{-1}(x)| = 2\} \cap f(\operatorname V(\Gamma)) = \varnothing 이다.
* 임의의 두 변의 교차점은 유한 개이다. 즉, 임의의 두 변 e,f\in\operatorname E(\Gamma)에 대하여, \{(s,t) \colon f(s) = f(t),\; s \in t, t\in t\}는 유한 집합이다. (e\ne f일 필요는 없다. 즉, 변은 스스로와 유한 번 교차할 수 있다.)
* 임의의 교차점 x\in X에 대하여, f\restriction U=\iota_V\circ \tilde f\circ \iota_U가 되는, 다음과 같은 U,V,\iota_U,\iota_V가 존재한다.
*:U\subseteq\Gamma는 열린집합이다.
*:V\subseteq X는 열린집합이다.
*:\iota_V\colon \mathbb D^2\to X는 열린 원판에서 V로 가는 위상 동형이다.
*:\iota_U\colon (-1,1)\sqcup (-1,1)\to U는 두 열린구간의 분리합집합에서 U로 가는 위상 동형이다.
여기서 \tilde f\colon(-1,1)\sqcup (-1,1)\to\mathbb D^2는 다음과 같다.
:(-1,1)\sqcup (-1,1)\cong(-1,1)\times\{\mathsf x,\mathsf y\}라면, f(t,\mathsf x)=(0,t)이며 f(t,\mathsf y)=(t,0)이다.

특히, 유한 그래프의 그리기는 유한 개의 꼭짓점을 갖는다.

다중 그래프 \Gamma의 그리기 f\colon X\to\Gamma의 **교차수**는 기수
:|\{x\in X\colon |f^{-1}(x)| = 2\}|
이다. 다중 그래프 \Gamma의 **교차수**는 평면 \mathbb R^2 속의 그리기의 교차수의 최솟값이며, 이를 \operatorname{cr}(\Gamma)로 표기하자. 보다 일반적으로, 곡면 \Sigma 속의 그리기의 교차수의 최솟값을 \operatorname{cr}_\Sigma(\Gamma)로 표기하자.

교차수가 0인 그래프 그리기를 **그래프 매장**(埋藏, )이라고 한다. 다중 그래프 \Gamma의 **종수**(種數, )는 \Gamma가 매장을 갖는 연결 콤팩트 2차원 유향 다양체 (\mathbb T^2)^{\#g}의 최소 종수 g\in\mathbb N이다.
:\operatorname{genus}(\Gamma) = \min \left\{g\in\mathbb N \colon \operatorname{cr}_{(\mathbb T^2)^{\#g}}(\Gamma) = 0\right\}

## 교차수 부등식
임의의 유한 그래프 \Gamma에 대하여, 다음이 성립한다.
* 만약 |\operatorname E(\Gamma)| > 7|\operatorname V(\Gamma)|라면, 29 \operatorname{cr}(\Gamma) |\operatorname V(\Gamma)|^2 \ge |\operatorname E(\Gamma)|^3이다.
* 만약 |\operatorname E(\Gamma)| > 4 |\operatorname V(\Gamma)|라면, 64 \operatorname{cr}(\Gamma) |\operatorname V(\Gamma)|^2 \ge |\operatorname E(\Gamma)|^3이다.

## 예
모든 평면 그래프 \Gamma의 교차수와 종수는 정의에 따라 \operatorname{cr}(\Gamma)=\operatorname{genus}(\Gamma)=0이다.

### 완전 그래프
완전 그래프의 교차수는 아직 완전히 알려지지 않있다. 다만, 다음과 같은 부등식이 알려져 있다.
:\operatorname{cr}(K_n) \le \frac14 \left\lfloor \frac n2\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor \left\lfloor \frac {n-2}2\right\rfloor \left\lfloor \frac {n-3}2\right\rfloor 
이 부등식은 n\le 12에 대하여 등식이라는 것이 알려져 있다. 이 부등식이 n>12인 경우에 대하여 역시 등식이 된다고 추측되지만, 이는 미해결 난제이다.

유한 완전 그래프의 종수는 다음과 같다. 
:\operatorname{genus}(K_n) = \begin{cases}
\left\lceil (n-3)(n-4)/12 \right\rceil & n \ge 3\\
0 & n \le 4
\end{cases}

Complete Graph K3.svg|K_3는 평면 그래프이다. 즉, 그 교차수와 종수는 0이다.
K4 planar.svg|K_4는 평면 그래프이다. 즉, 그 교차수와 종수는 0이다.
RAC drawings.svg|K_5(왼쪽)의 교차수는 1이며, K_{3,4}(오른쪽)의 교차수는 2이다.


### 완전 이분 그래프
완전 이분 그래프의 교차수는 아직 완전히 알려지지 않있다. 다만, 다음과 같은 상계가 알려져 있다.
:\operatorname{cr}(K_{m,n}) \le  \left\lfloor \frac m2\right\rfloor \left\lfloor \frac {m-1}2\right\rfloor\left\lfloor \frac n2\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor  

**[[상계 (수학)|상계]]의 증명**:

K_{m,n}이 주어졌다고 하고, m개의 검은 꼭짓점 및 n개의 흰 꼭짓점으로 그래프 색칠을 부여하자. 그렇다면, 유클리드 평면에 이들을 다음과 같이 배열한다.
* m개의 검은 꼭짓점들은 x축에 다음과 같이 배열된다.
*: (-\lfloor m/2\rfloor,0),\dotsc, (-2,0), (-1,0),  (1,0), (2,0), \dotsc,(\lceil m/2\rceil,0) 
* n개의 흰 꼭짓점들은 y축에 다음과 같이 배열된다.
*: (0,-\lfloor n/2\rfloor),\dotsc, (0,-2), (0,-1),  (0,1), (0,2), \dotsc,(0,\lceil n/2\rceil) 
이제, 이를 이으면 평면 속의 K_{m,n}의 그리기가 된다.

이 그리기의 교차수는 다음과 같다. 우선, 제1 사분면에서, 변 (a,0)-(0,b)와 (a',0)-(0,b')이 교차할 필요 충분 조건은 (a-a')(b-b')인 것이다. 즉, 제1 사분면에서 교차하는 변의 쌍의 수는
:
\begin{aligned}
\left|\left\{(a,a',b,b')\colon 0
이다. 나머지 사분면들도 마찬가지로 계산된다. 즉, 이 그래프 그리기의 교차점의 수는 다음과 같다.
:\begin{aligned}
\operatorname{cr}(K_{m,n}) &\le
\frac14
\left(
\left\lceil \frac m2-1\right\rceil \left\lceil \frac m2\right\rceil
+ \left\lfloor \frac m2-1\right\rfloor \left\lfloor \frac m2\right\rfloor
\right)
\left(
\left\lceil \frac n2-1\right\rceil \left\lceil \frac n2\right\rceil
+
\left\lfloor \frac n2-1\right\rfloor \left\lfloor \frac n2\right\rfloor
\right) \\
&=\left\lfloor \frac m2\right\rfloor \left\lfloor \frac {m-1}2\right\rfloor\left\lfloor \frac n2\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor
\end{aligned}


또한, 이 부등식이 등식이 될 다음과 같은 충분 조건이 알려져 있다.
* \min\{m,n\} \le 6일 때
* 7 = \min\{m,n\} \le \max\{ m,n \} \le 9 
**자란키에비치 추측**(Zarankiewicz推測, )에 따르면, 이 부등식이 항상 등식이 된다고 추측되지만, 이는 미해결 난제이다.

유한 완전 이분 그래프의 종수는 다음과 같다.
:\operatorname{genus}(K_{m,n}) =
\begin{cases}\left\lceil (m-2)(n-2)/4 \right\rceil & \min\{m,n\} \ge2 \\
0 & \min\{m,n\} \le 2
\end{cases}
 


GraphMinorExampleA.png|K_{1,4}의 교차수는 0이다.
Circle graph C4.svg|K_{2,2}의 교차수는 0이다.
Graph homeomorphism example 1.svg|K_{2,3}의 교차수는 0이다.
K33 one crossing.svg|K_{3,3}의 교차수는 1이다.
Zarankiewicz K4,7.svg|K_{4,7}의 교차수는 18이다.


### 일반화 페테르센 그래프
각기둥 그래프 \operatorname{GPG}(n,1)은 평면 그래프이므로, 교차수와 종수가 0이다. \operatorname{GPG}(6,2) 역시 평면 그래프이다.

페테르센 그래프 \operatorname{GPG}(5,2)의 교차수는 2이다.
일반화 페테르센 그래프 \operatorname{GPG}(8,3)의 교차수는 4이며, 그 종수는 1이다. 데자르그 그래프 \operatorname{GPG}(10,3)의 교차수는 6이다. 나우루 그래프 \operatorname{GPG}(12,5)의 교차수는 8이다. 특히, 이 두 그래프 둘 다 평면 그래프가 아니다.


Octagonal prismatic graph.svg|팔각 기둥 그래프 \operatorname{GPG}(8,1)은 평면 그래프이므로, 그 교차수와 종수는 0이다.
Petersen graph, two crossings.svg|페테르센 그래프 \operatorname{GPG}(5,2)의 교차수는 2이다.
Nauru 1-planar 8-crossing.svg|나우루 그래프 \operatorname{GPG}(12,5)의 교차수는 8이다.
Möbius–Kantor_torus.svg|\operatorname{GPG}(8,3)의, 원환면 \mathbb T^2 속의 매장. 따라서, \operatorname{GPG}(8,3)의 종수는 1이다.


## 역사
하나니-텃 정리는 하임 하나니(, 舊名 , 1912~1991)가 1934년에 증명하였으나, 하나니는 이를 논문에 매우 간접적으로 언급하였다. 1970년에 윌리엄 토머스 텃이 이 정리를 (직접적으로) 다시 언급하였다.

섬네일|헝가리의 한 벽돌 공장의 철로
섬네일|카지미에시 자란키에비치(). 1935년 사진
섬네일|right|카지미에시 우르바니크(). 1981년 사진
완전 이분 그래프의 교차수를 계산하는 문제는 투란 팔이 1944년에 최초로 제시하였다. 이에 대하여 투란은 다음과 같이 적었다.

투란에게서 이 문제를 들은 카지미에시 자란키에비치(, 1902~1959)와 카지미에시 우르바니크(, 1930~2005)는 둘 다 각각 1950년대 초에 이 문제를 “해결”하는 논문을 출판하였으나, 이들의 증명은 훗날 오류가 있어, 오직 교차수의 상계만을 증명한다는 것이 밝혀졌다.

교차수 부등식은 1980년대 초에  어이터이 미클로시(, 1946~) · 바츨라프 흐바탈(, 1946~) · 몬로 몬티 뉴본(, 1938~) · 세메레디 엔드레와 프랭크 톰슨 레이턴(, 1956~)이 최초로 증명하였으며, 이후 후대 수학자들이 그 상수를 개선하였다.

## 각주

## 외부 링크
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 


분류:그래프 이론