[그래프이론] #1. The Basics

 

 

그래프 이론을 공부해보고자 한다. Reinhard Diestel의 Graph Theory 5th edition의 내용을 정리한 글이다.

 

 

Def. Graph. 그래프란, 집합 $V$와 $E \subset [V]^2$의 쌍 $G=(V, E)$로 정의된다. (이때 $[V]^2$는 원소의 개수가 2개인 $V$의 모든 부분집합의 모임)이때 $V$의 원소는 그래프 $G$의 vertices (또는 nodes, points, 정점, 꼭짓점)라고 하며 $E$의 원소는 그래프 $G$의 edges (또는 lines, 변, 모서리)라고 한다. 쉽게 이해하기 위하여 다음과 같이 정점과 변으로 구성된 그래프를 살펴보자. 

이 그래프의 꼭짓점은 $V=\left\{1, 2, 3, 4, 5, 6, 7 \right\}$이다. 이 그래프에서 존재할 수 있는 간선은 다음과 같다. 

$$V^2=\left\{ \left\{1, 2\right\} , \left\{1, 3\right\} , \cdots, \left\{6, 7\right\} \right\}$$

이 중에서 이 그래프는 $E= \left\{ \left\{1, 2\right\}, \left\{1, 5\right\}, \left\{2, 5\right\}, \left\{3, 4\right\}, \left\{5, 7\right\}\right\} \subset V^2$ 로 구성되어있으며, $G=(V, E)$로 나타낼 수 있다. 

 

그래프의 정점 집합이 $V$로 주어지면 그 그래프는 $V$ 위의 그래프라고 표현한다. 주어진 그래프  $G$의 정점 집합은 $V(G)$, 간선 집합은 $E(G)$로 나타낸다. 어떤 정점  $v$가 그래프 $G$의 정점이라면 $v \in V(G)$로 나타낼 수도 있지만 간단하게  $v \in G$로 나타내며 동일하게 간선 $e$에 대해서 $e \in G$로 나타낸다. 

 

 

Def. Order of Graph. 그래프 $G$의 정점의 개수를 그래프의 order(위수)라고 하며 $|G|$로 나타낸다. 그래프의 위수에 따라 그래프는 유한, 무한, countable 그래프로 분류할 수 있다. 위수가 0 또는 1 (즉, 정점이 없거나 하나)인 그래프를 trivial 그래프라고 한다. 그래프 $G$의 간선의 개수는 $||G||$로 나타낸다. 

 

 

Def. Incident, Ends, and Joins. 정점 $v$가 간선 $e$의 원소라면, 즉 $v \in e$라면 $v$ is incident with $e$($v$가 $e$에 근접하다)고 정의한다. 두 정점 $a, b$에 대하여 $a, b$를 잇는 간선 $d= \left\{a, b\right\}$가 존재할 때, 간선 $d$가 두 정점을 join 한다(연결한다, 결합한다)고 정의하며, $a, b$는 $d$의 endvertices(또는 ends, 끝점, 양 끝 정점)이라고 한다. 간선 $\left\{x, y \right\}$는 간단하게 $xy$ 또는 $yx$로 나타낸다. 

 

 

Def. Adjacent, Neighbours, and Independent. 그래프 $G$의 두 정점 $x, y$를 잇는 간선 $\left\{x, y\right\}$가 존재하면 두 정점은 adjacent 하다(또는 neighbours, 이웃하다)고 한다. 또한, 서로 다른 두 간선이 하나의 끝점을 공유하면 이때도 adjacent라고 한다. Adjacent하지 않은 정점 또는 간선은 independent라고 한다. 

 

 

Def. Homomorphism. 두 그래프 $G=(V, E), G'=(V', E')$와 mapping $\varphi : V \rightarrow V'$에 대하여 이 mapping이 모든 정점의 adjacency를 유지한다면, 즉 모든 $ \left\{x, y\right\} \in E$에 대하여  $\left\{\varphi(x), \varphi(y) \right\} \in E'$이라면 $\varphi$는 $G$에서 $G'$로의 homomorphism이다. 

 

 

 

두 그래프를 위와 같이 정의하자. 

$$V= \left\{a, b, c, d, e\right\}, E=\left\{\left\{a,b \right\}, \left\{b,c \right\} , \left\{c,d \right\} , \left\{d,e \right\} , \left\{e,a \right\}\right\}, G=(V, E)$$

$$V'=\left\{x,y,z\right\}, E'=\left\{\left\{x,y \right\},\left\{y,z \right\} ,\left\{z,x \right\}\right\}, G'=(V', E')$$

이제 $G$에서 $G'$로의 homomorphism $f:V \rightarrow V'$을 찾아보자.  Homomorphism의 정의를 만족하기 위해서는 $E$의 모든 간선 $\left\{e_1, e_2 \right\} \in E$에 대하여 $\left\{ f(e_1), f(e_2) \right\} \in E'$가 성립해야 한다. 다음과 같이 $f : V \rightarrow V'$를 정의해보자.

$$f(a)=x, f(b)=y, f(c)=z, f(d)=x, f(e)=z$$

그러면 어렵지 않게 모든 간선에 대하여 위의 조건이 만족함을 확인할 수 있다. Mapping $f$의 domain $V$에서 서로 다른 정점이 $V'$의 한 정점으로 대응될 수도 있다. 위에 예시에서도 $f(a)=f(d)=x$임을 확인할 수 있다. (당연히 $G$의 위수보다 $G'$의 위수가 작으면 이런 일이 일어날 수 있다.) 이때 다음이 성립한다.

 

Theorem. 그래프 $G$에서 $G'$으로의 homomorphism $\varphi$, $\varphi$의 image의 모든 정점 $x'$에 대하여 inverse image $\varphi^{-1}(x')$는 $G$의 독립인 정점의 집합이다. 

Proof. Inverse image $\varphi^{-1}(x')$가 독립이 아니라고 가정하자. 즉, $G$의 어떤 인접한 두 정점 $u, v$에 대하여 $u, v \in \varphi^{-1}(x')$라고 하자. Homomorphism의 정의에 따라 $\left\{ \varphi(u), \varphi(v) \right\} \in E'$가 만족한다. 이때 $u, v$ 모두 $\varphi^{-1}(x')$의 원소이므로, $\varphi(u) = \varphi(v) = x'$이 성립한다. 즉, $\left\{ \varphi(u), \varphi(v) \right\} = \left\{x', x' \right\} = \left\{x' \right\}$이므로, 모순이 발생한다. $\blacksquare$

 

 

Def. Isomorphism. 그래프 $G$, $G'$와 homomorphism $\varphi : V \rightarrow V'$에 대하여 $\varphi$가 전단사 함수인 동시에 $\varphi^{-1}$ 또한 homomorphism이라면, 즉 $xy \in E \Leftrightarrow \varphi(x)\varphi(y) \in E'$이라면, $\varphi$를 isomorphism, $G$와 $G'$을 isomorphic하다고 한다. 이때 $G \simeq G'$로 나타낸다.  일반적으로 isomorphic한 그래프를 딱히 구분하지 않는다고 하며, 그냥 $G = G'$로 나타낸다.