Overview

Graph Theory를 응용하는 여러가지 주제를 설명한다.

Graph Isomorphism

Graph Isomorphism(그래프 동형사상)은 두 개의 simple graph $G$와 $H$에 대하여,

$uv \in E(G) \iff f(u)f(v) \in E(G)$

를 만족시키는 함수

$f : V(G) → V(H)$

가 존재하는 bijection(일대일 대응)이다.

• Isomorphism(동형 사상)은 서로 구조가 같은 두 대상 사이에, 모든 구조를 보존하는 사상(寫像)이다.
• 두 그래프 $G$와 $H$ 간에 동형사상이 존재하면, 두 그래프는 isomorphic(동형)이라고 하고 $G \simeq H$라고 쓴다.

Graph Coloring

Graph Coloring(그래프 색칠)은 그래프의 vertices에 같은 색이 인접하지 않도록 색을 부여하는 방법이다.

Chromatic Number

그래프 $G$의 Chromatic Number(색칠수) $\chi(G)$는 coloring에 필요한 수의 최솟값이다.

4색 정리

지도 위의 모든 나라를 색칠하는데, 인접한 나라끼리 색이 겹치지 않도록 칠하려면 4가지 색만으로도 충분한지를 따지는 문제다. (참으로 증명되었다.)

• 모든 유한 평면 그래프 $G$에 대하여, $\chi(G) ≤ 4$이다.