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

Def. Graph Property. Isomorphism에 대해 닫혀있는 그래프의 모임을 graph property라고 한다. 예를 들어, '삼각형'을 포함하는 것은 graph property에 해당한다.

Proof. 우선, 삼각형을 포함하는 그래프를 다음과 같이 정의하자: 그래프 $G = (V, E)$에 대하여 $xy, yz, zx \in E$를 만족하는 세 정점 $x, y, z \in V$가 존재한다. 이제, $G$와 isomorphic한 모든 그래프가 삼각형을 포함한다는 것을 보일 수 있다면, '삼각형을 포함한다'는 조건을 만족하는 그래프의 모임은 isomorphism에 대해 닫혀있음을 알 수 있으므로 이가 graph property임을 증명할 수 있다.

 

$G$와 isomorphic한 임의의 그래프 $H=(W, F)$, isomorphism $\varphi$를 생각해보자. $G$에서 삼각형을 구성하는 세 정점 $x, y, z \in V$에 대해 isomorphism의 정의에 의해 $\left\{\varphi(x), \varphi(y) \right\}, \left\{\varphi(y), \varphi(z) \right\}, \left\{\varphi(z), \varphi(x) \right\} \in F$가 성립한다. 따라서 그래프 $H$는 $\varphi(x), \varphi(y), \varphi(z) \in W$라는 세 점으로 구성된 삼각형을 포함한다. 즉, $G$와 isomorphic한 임의의 그래프는 삼각형을 포함하므로, 삼각형을 포함하는 그래프의 모임은 isomorphism에 대해 닫혀있다. $\blacksquare$  

 

 

Def. Graph Invariant. 그래프를 인자로 받는 mapping 중 isomorphic한 그래프에 같은 값을 할당하는 mapping을 graph invariant라고 한다. 예를 들어 간선의 개수, 정점의 개수 등이 있다.  

 

 

Def. Disjoint and Subgraph. 두 그래프 $G=(V, E), G'=(V', E')$에 대하여 $G \cup G'=(V \cup V', E \cup E'), G \cap G'=(V \cap V', E \cap E')$으로 정의한다. 만약 $G \cap G'=\emptyset$ 이라면 $G$와 $G'$이 disjoint(서로소)라고 한다. 만약 $V' \subset V, E' \subset E$라면 $G'$이 $G$의 subgraph(부분 그래프)라고 하여 $G' \subset G$로 나타낸다. 

 

 

Def. Induced Subgraph. 두 그래프 $G=(V, E), G'=(V', E')$, $G'$의 모든 정점 $x, y \in V'$에 대하여 $xy \in E$라면 $G'$을 $G$의 induces subgraph라고 한다. 

 

위의 예시에서 보면, $G', G''$모두 $G$의 subgraph이다. 그러나, $G'$은 $G$의 induced subgraph인 반면 $G''$은 아니다. 그 이유는, 가운데 위치한 정점이 $G''$에 포함되었으나 $G$의 간선중 $E(G'')$에 포함되지 않은 간선이 존재하기 때문이다. 

 

 

Def. Spanning Subgraph. 어떤 정점 집합 $U$에 대하여 $G[U]$는, $U$에 포함된 $G$의 정점과, $U$ 위의 두 정점만을 끝점으로 가지는 간선으로 구성된 그래프를 나타낸다. 두 그래프 $G=(V, E), G'=(V', E')$에 대하여 $G' \subset G$일 때, $V'$이 $G'$을 span 한다고 표현한다. 만약 $V'=V$라면, 즉 $G'$이 $G$에서 정점은 모두 유지하고 간선의 일부만 제거된 subgraph라면, $G'$는 $G$의 spanning subgraph라고 한다. 

 

 

Def. 정점 집합 $U$에 대해 $G[V\setminus U]$를 $G-U$로 나타낸다. 비슷하게 정점 $v$에 대해서 $G-v$, 간선 집합 $F$에 대해서 $G-F, G+F$, 간선 $e$에 대해서 $G-e, G+e$를 정의한다. 

 

 

Def. Edge Maximal. 그래프 $G$와 어떤 성질에 대하여 $G$는 그 성질을 만족하지만, $G$에 어떠한 간선을 하나라도 추가하는 순간 그 성질을 만족하지 않는다면, 즉 그 성질을 만족하는 $E \subset F$인 그래프 $(V, F)$가 존재하지 않는다면, $G$는 그 성질에 대하여 edge maximal이라고 정의한다.  

 

 

Def. Complement. 그래프 $G=(V, E)$에 대해 동일한 정점 $V$와 간선 $[V]^2 \setminus E$를 갖는 그래프를 $G$의 complement라고 하며 $\bar{G}$로 나타낸다. 

 

 

Theorem. 서로소인 두 그래프 $G$, $G'$에 대해 두 그래프의 정점을 모두 연결한 그래프를 $G*G'$으로 나타낸다. 또한, $n$개의 정점이 서로 모두 adjacent한 그래프를 complete라고 하며 $K^n$으로 나타낸다. 이때, 서로소인 $K^n$과 $K^m$에 대하여 $K^n*K^m=K^{n+m}$이 성립한다.

Proof. 우선 $K^n*K^m$의 정점의 개수는 $n+m$개이다. 이 정점에서 어떻게 한 쌍을 뽑더라도 adjacent함을 보이자. $K^n*K^m$에서 두 정점을 뽑았을 때 경우의 수는 총 세 가지 밖에 없다. 두 점 모두 $K^n$의 원소이거나, 두 점 모두 $K^m$의 원소이거나, 또는 한 점은 $K^n$의 원소이고 한 점은 $K^m$의 원소이다. 이때, complete graph의 정의에 의하여 두 점이 기존 같은 그래프의 정점이라면 adjacent이다. 또한, $K^n*K^m$의 정의에 의하여 한 점은 $K^n$의 원소이고 한 점은 $K^m$의 원소라면 두 점은 adjacent이다. 따라서 $K^n*K^m$의 모든 점은 adjacent하므로, $K^n*K^m$는 complete하여 $K^n*K^m=K^{n+m}$가 성립한다. $\blacksquare$