그래프 그리기

틀:위키데이터 속성 추적 그래프 이론에서 그래프 그리기(틀:Llang)는 어떤 그래프 또는 다중 그래프를 어떤 곡면 위에, 변이 교차할 수 있게 표시한 것이다.

정의

다음이 주어졌다고 하자.

• 2차원 다양체 $\mathrm{\Sigma }$
• 다중 그래프 $\mathrm{\Gamma }$

다중 그래프 $\mathrm{\Gamma }$의, $X$ 속의 그리기는 다음 조건들을 모두 만족시키는 함수

$f:\mathrm{\Gamma }\to X$

이다.

• $\mathrm{\Gamma }$에 CW 복합체 위상을 주었을 때, $f$는 연속 함수이다.
• 임의의 $x\in X$에 대하여, $|f^{-1}(x)|\le 2$이다.
• 변의 교차점은 꼭짓점이 아니다. 즉, $\{x\in X:|f^{-1}(x)|=2\}\cap f(\mathrm{V}(\mathrm{\Gamma }))=\varnothing$이다.
• 임의의 두 변의 교차점은 유한 개이다. 즉, 임의의 두 변 $e,f\in \mathrm{E}(\mathrm{\Gamma })$에 대하여, $\{(s,t):f(s)=f(t),s\in t,t\in t\}$는 유한 집합이다. ($e\ne f$일 필요는 없다. 즉, 변은 스스로와 유한 번 교차할 수 있다.)
• 임의의 교차점 $x\in X$에 대하여, $f\upharpoonright U={\iota }_V\circ \tilde{f}\circ {\iota }_U$가 되는, 다음과 같은 $U,V,{\iota }_U,{\iota }_V$가 존재한다.

  $U\subseteq \mathrm{\Gamma }$는 열린집합이다.

  $V\subseteq X$는 열린집합이다.

  ${\iota }_V:{𝔻}^2\to X$는 열린 원판에서 $V$로 가는 위상 동형이다.

  ${\iota }_U:(-1,1)\bigsqcup (-1,1)\to U$는 두 열린구간의 분리합집합에서 $U$로 가는 위상 동형이다.

여기서 $\tilde{f}:(-1,1)\bigsqcup (-1,1)\to {𝔻}^2$는 다음과 같다.

$(-1,1)\bigsqcup (-1,1)\cong (-1,1)\times \{𝗑,𝗒\}$라면, $f(t,𝗑)=(0,t)$이며 $f(t,𝗒)=(t,0)$이다.

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

다중 그래프 $\mathrm{\Gamma }$의 그리기 $f:X\to \mathrm{\Gamma }$의 교차수는 기수

$|\{x\in X:|f^{-1}(x)|=2\}|$

이다. 다중 그래프 $\mathrm{\Gamma }$의 교차수는 평면 ${ℝ}^2$ 속의 그리기의 교차수의 최솟값이며, 이를 $\mathrm{cr}(\mathrm{\Gamma })$로 표기하자. 보다 일반적으로, 곡면 $\mathrm{\Sigma }$ 속의 그리기의 교차수의 최솟값을 ${\mathrm{cr}}_{\mathrm{\Sigma }}(\mathrm{\Gamma })$로 표기하자.

교차수가 0인 그래프 그리기를 그래프 매장(埋藏, 틀:Llang)이라고 한다. 다중 그래프 $\mathrm{\Gamma }$의 종수(種數, 틀:Llang)는 $\mathrm{\Gamma }$가 매장을 갖는 연결 콤팩트 2차원 유향 다양체 $({𝕋}^2{)}^{\mathrm{\#}g}$의 최소 종수 $g\in \mathbb{N}$이다.

$\mathrm{genus}(\mathrm{\Gamma })=\min \{g\in \mathbb{N}:{\mathrm{cr}}_{({𝕋}^2{)}^{\mathrm{\#}g}}(\mathrm{\Gamma })=0\}$

교차수 부등식

임의의 유한 그래프 $\mathrm{\Gamma }$에 대하여, 다음이 성립한다.

• 만약 $|\mathrm{E}(\mathrm{\Gamma })|>7|\mathrm{V}(\mathrm{\Gamma })|$라면, $29\mathrm{cr}(\mathrm{\Gamma })|\mathrm{V}(\mathrm{\Gamma }){|}^2\ge |\mathrm{E}(\mathrm{\Gamma }){|}^3$이다.
• 만약 $|\mathrm{E}(\mathrm{\Gamma })|>4|\mathrm{V}(\mathrm{\Gamma })|$라면, $64\mathrm{cr}(\mathrm{\Gamma })|\mathrm{V}(\mathrm{\Gamma }){|}^2\ge |\mathrm{E}(\mathrm{\Gamma }){|}^3$이다.

예

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

완전 그래프

완전 그래프의 교차수는 아직 완전히 알려지지 않있다. 다만, 다음과 같은 부등식이 알려져 있다.

$\mathrm{cr}(K_n)\le \frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\rfloor$

이 부등식은 $n\le 12$에 대하여 등식이라는 것이 알려져 있다. 이 부등식이 $n>12$인 경우에 대하여 역시 등식이 된다고 추측되지만, 이는 미해결 난제이다.

유한 완전 그래프의 종수는 다음과 같다. 틀:OEIS

$\mathrm{genus}(K_n)=\{\begin{array}{cc}\lceil (n-3)(n-4)/12\rceil & n\ge 3\\ 0& n\le 4\end{array}$

• 
  $K_3$는 평면 그래프이다. 즉, 그 교차수와 종수는 0이다.
• 
  $K_4$는 평면 그래프이다. 즉, 그 교차수와 종수는 0이다.
• 
  $K_5$(왼쪽)의 교차수는 1이며, $K_{3,4}$(오른쪽)의 교차수는 2이다.

완전 이분 그래프

완전 이분 그래프의 교차수는 아직 완전히 알려지지 않있다. 다만, 다음과 같은 상계가 알려져 있다.

$\mathrm{cr}(K_{m,n})\le \lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor$

상계의 증명:

$K_{m,n}$이 주어졌다고 하고, $m$개의 검은 꼭짓점 및 $n$개의 흰 꼭짓점으로 그래프 색칠을 부여하자. 그렇다면, 유클리드 평면에 이들을 다음과 같이 배열한다.

• $m$개의 검은 꼭짓점들은 $x$축에 다음과 같이 배열된다.

  $(-\lfloor m/2\rfloor ,0),\dots ,(-2,0),(-1,0),(1,0),(2,0),\dots ,(\lceil m/2\rceil ,0)$

• $n$개의 흰 꼭짓점들은 $y$축에 다음과 같이 배열된다.

  $(0,-\lfloor n/2\rfloor ),\dots ,(0,-2),(0,-1),(0,1),(0,2),\dots ,(0,\lceil n/2\rceil )$

이제, 이를 이으면 평면 속의 $K_{m,n}$의 그리기가 된다.

이 그리기의 교차수는 다음과 같다. 우선, 제1 사분면에서, 변 $(a,0)-(0,b)$와 $(a^{\prime },0)-(0,b^{\prime })$이 교차할 필요 충분 조건은 $(a-a^{\prime })(b-b^{\prime })<0$인 것이다. 즉, 제1 사분면에서 교차하는 변의 쌍의 수는

$\begin{array}{cc}\left|\{(a,a^{\prime },b,b^{\prime }):0<a<a^{\prime }\le \lceil \frac{m}{2}\rceil ,0<b^{\prime }<b\le \lceil \frac{n}{2}\rceil \}\right|& =(1+2+\cdots +\lceil \frac{m}{2}-1\rceil )(1+2+\cdots +\lceil \frac{n}{2}-1\rceil )\\ & =\frac{1}{4}\lceil \frac{m}{2}-1\rceil \lceil \frac{m}{2}\rceil \lceil \frac{n}{2}-1\rceil \lceil \frac{n}{2}\rceil \end{array}$

이다. 나머지 사분면들도 마찬가지로 계산된다. 즉, 이 그래프 그리기의 교차점의 수는 다음과 같다.

$\begin{array}{cc}\mathrm{cr}(K_{m,n})& \le \frac{1}{4}(\lceil \frac{m}{2}-1\rceil \lceil \frac{m}{2}\rceil +\lfloor \frac{m}{2}-1\rfloor \lfloor \frac{m}{2}\rfloor )(\lceil \frac{n}{2}-1\rceil \lceil \frac{n}{2}\rceil +\lfloor \frac{n}{2}-1\rfloor \lfloor \frac{n}{2}\rfloor )\\ & =\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \end{array}$

또한, 이 부등식이 등식이 될 다음과 같은 충분 조건이 알려져 있다.

• $\min \{m,n\}\le 6$일 때
• $7=\min \{m,n\}\le \max \{m,n\}\le 9$

자란키에비치 추측(Zarankiewicz推測, 틀:Llang)에 따르면, 이 부등식이 항상 등식이 된다고 추측되지만, 이는 미해결 난제이다.

유한 완전 이분 그래프의 종수는 다음과 같다.

$\mathrm{genus}(K_{m,n})=\{\begin{array}{cc}\lceil (m-2)(n-2)/4\rceil & \min \{m,n\}\ge 2\\ 0& \min \{m,n\}\le 2\end{array}$

• 
  $K_{1,4}$의 교차수는 0이다.
• 
  $K_{2,2}$의 교차수는 0이다.
• 
  $K_{2,3}$의 교차수는 0이다.
• 
  $K_{3,3}$의 교차수는 1이다.
• 
  $K_{4,7}$의 교차수는 18이다.

일반화 페테르센 그래프

각기둥 그래프 $\mathrm{GPG}(n,1)$은 평면 그래프이므로, 교차수와 종수가 0이다. $\mathrm{GPG}(6,2)$ 역시 평면 그래프이다.

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

• 
  팔각 기둥 그래프 $\mathrm{GPG}(8,1)$은 평면 그래프이므로, 그 교차수와 종수는 0이다.
• 
  페테르센 그래프 $\mathrm{GPG}(5,2)$의 교차수는 2이다.
• 
  나우루 그래프 $\mathrm{GPG}(12,5)$의 교차수는 8이다.
• 
  $\mathrm{GPG}(8,3)$의, 원환면 ${𝕋}^2$ 속의 매장. 따라서, $\mathrm{GPG}(8,3)$의 종수는 1이다.

역사

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

헝가리의 한 벽돌 공장의 철로

카지미에시 자란키에비치(틀:Llang). 1935년 사진

카지미에시 우르바니크(틀:Llang). 1981년 사진

완전 이분 그래프의 교차수를 계산하는 문제는 투란 팔이 1944년에 최초로 제시하였다. 이에 대하여 투란은 다음과 같이 적었다. 틀:인용문2 투란에게서 이 문제를 들은 카지미에시 자란키에비치(틀:Llang, 1902~1959)와 카지미에시 우르바니크(틀:Llang, 1930~2005)는 둘 다 각각 1950년대 초에 이 문제를 “해결”하는 논문을 출판하였으나, 이들의 증명은 훗날 오류가 있어, 오직 교차수의 상계만을 증명한다는 것이 밝혀졌다.

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

외부 링크

• 틀:Eom
• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:웹 인용