그래프 데카르트 곱

섬네일|right|그래프 데카르트 곱의 예. 5개의 꼭짓점 및 5개의 변을 갖는 그래프와 4개의 꼭짓점 및 3개의 변을 갖는 그래프의 데카르트 곱은 5×4=20개의 꼭짓점을 가지며, 5×3+4×5=35개의 변을 가진다.
섬네일|right|그래프 데카르트 곱의 예. 5개의 꼭짓점 및 6개의 변을 갖는 그래프와 2개의 꼭짓점 및 1개의 변을 갖는 그래프의 데카르트 곱은 5×2=10개의 꼭짓점을 가지며, 5×1+2×6=17개의 변을 가진다.
그래프 이론에서 **그래프 데카르트 곱**(graph Descartes곱, )은 두 그래프를 합치는 이항 연산이다. 이렇게 얻은 그래프의 꼭짓점의 수는 원래 두 그래프의 꼭짓점의 수들의 곱과 같다.

## 정의
그래프의 족 (\Gamma_i)_{i\in I}의 **그래프 데카르트 곱**
:\Gamma = {\prod\!\!\!\!\!\!\!\!}\!\coprod_{i\in I}  \Gamma_i
은 다음과 같은 그래프이다.
:\mathsf V(\Gamma) = \prod_{i\in I}\mathsf V(\Gamma_i)
:uv \in \mathsf E(\Gamma) \iff \exists i\in I \colon \left( u_iv_i \in \mathsf E(\Gamma_i) \land \forall j \in I \setminus\{i\} \colon u_i = v_j \right)
즉, 데카르트 곱 \Gamma는 다음과 같은 그래프이다.
* 그 꼭짓점 v \in \mathsf V(\Gamma)은 각 성분 \Gamma_i의 꼭짓점들의 열 (v_i)_{i\in I}, v_i \in \mathsf V(\Gamma_i)이다.
* 두 꼭짓점 u,v \in \mathsf V(\Gamma)이 변으로 연결되어 있을 필요 충분 조건은 어떤 성분 i\in I에 대하여, u_i와 v_i가 그래프 \Gamma_i에서 변으로 연결되며, 나머지 성분들이 모두 일치하는 것이다.

두 그래프 \Gamma, \Gamma'의 데카르트 곱은 \Gamma\,\square\, \Gamma'으로 표기한다.

## 성질
그래프 데카르트 곱은 (표준적 그래프 동형 아래) 결합 법칙과 교환 법칙을 따른다. 그래프 데카르트 곱의 항등원은 한원소 그래프 \mathsf K_1이다.

두 그래프 \Gamma, \Gamma'에 대하여 다음이 성립한다.
:\left|\mathsf V\left( {\prod\!\!\!\!\!\!\!\!}\!\coprod_{i\in I}  \Gamma_i\right)\right| = \prod_{i\in I}|\mathsf V(\Gamma_i)|
:\left|\mathsf E\left({\prod\!\!\!\!\!\!\!\!}\!\coprod_{i\in I}  \Gamma_i\right)\right| = 
\sum_{i\in I}|\mathsf E(\Gamma_i)|\prod_{j\in I\setminus\{i\}} |\mathsf V(\Gamma_j)|
(무한 그래프의 경우 이는 기수의 연산으로 해석한다.)

### 인접 행렬
두 유한 그래프 \Gamma, \Gamma'의 데카르트 곱의 인접 행렬은 다음과 같다.
:\mathsf A_{\Gamma\,\square\Gamma'} = \mathsf A_\Gamma \otimes 1_{\mathsf V(\Gamma')} + 1_{\mathsf V(\Gamma)} \otimes \mathsf A_{\Gamma'}
여기서 \otimes는 행렬의 크로네커 곱이다.

특히, \Gamma\,\square\,\Gamma'의 스펙트럼(인접 행렬의 고윳값의 중복집합)은 \Gamma와 \Gamma'의 스펙트럼의 합이다.
:\operatorname{Spec}(\Gamma \,\square\,\Gamma') = \operatorname{Spec}(\Gamma) + \operatorname{Spec}(\Gamma') = \{\lambda + \lambda' \colon \lambda \in \operatorname{Spec}\Gamma,\;\lambda' \in \operatorname{Spec}\Gamma'\}

### 채색수
유한한 채색수를 가진, 하나 이상의 꼭짓점을 갖는 두 (유한 또는 무한) 그래프 \Gamma, \Gamma'의 데카르트 곱의 채색수는 각 그래프의 채색수 가운데 최댓값이다. (두 그래프 가운데 하나가 꼭짓점을 갖지 않는다면 그 데카르트 곱의 채색수는 자명하게 0이다.)
:\chi(\Gamma\,\square\,\Gamma') = 
\begin{cases}
\max_{i\in I}\{\chi(\Gamma),\chi(\Gamma')\} & (\Gamma \ne \varnothing \ne \Gamma')\\
0 & (\varnothing \in \{\Gamma,\Gamma'\})
\end{cases}


**증명:**

\Gamma 또는 \Gamma' 가운데 적어도 하나가 꼭짓점을 갖지 않는 경우는 자명하다. 따라서 둘 다 공그래프가 아니라고 가정하자.

편의상
:N = \max\{\chi(\Gamma),\chi(\Gamma')\}
으로 표기하자. 채색
:c \colon \mathsf V(\Gamma) \to \mathbb Z/(N)
:c' \colon \mathsf V(\Gamma') \to \mathbb Z/(N)
이 주어졌을 때,
:C \colon \mathsf V(\Gamma\,\square\,\Gamma') \to \mathbb Z/(N)
:C \colon (v,v') \mapsto c(v) + c'(v') 
는 \Gamma\,\square\,\Gamma 위의 채색을 이룬다. 따라서
:\chi(\Gamma\,\square\,\Gamma') \le N
이다. 그러나 \Gamma와 \Gamma'은 둘 다 \Gamma\,\square\,\Gamma'의 부분 그래프이다. 따라서
:\chi(\Gamma\,\square\,\Gamma') \ge N
이다.


특히, 두 그래프의 데카르트 곱이 이분 그래프일 필요 충분 조건은 다음과 같다.
* 둘 다 이분 그래프이거나, 또는 둘 가운데 하나가 \varnothing이다.

### 데카르트 곱 분해
한원소 그래프 \mathsf K_1이 아닌 두 그래프의 데카르트 곱으로 표현될 수 없는 그래프를 **데카르트 소 그래프**(Descartes素graph,)라고 하자.

모든 연결 유한 그래프는 소 그래프들의 데카르트 곱으로 표현될 수 있으며, 이러한 표현은 (순서를 무시하면) 유일하다. 그러나 연결 그래프가 아닌 그래프의 경우 이러한 표현은 일반적으로 유일하지 않다. 예를 들어, 다음이 성립한다.
:(\mathsf K_1 \sqcup \mathsf K_2 \sqcup \mathsf K_2^{\square 2}) \,\square\, (\mathsf K_1 \sqcup \mathsf K_2^{\square 3}) = (\mathsf K_1 \sqcup \mathsf K_2^{\square2} \sqcup \mathsf K_2^{\square4})\,\square(\mathsf K_1 \sqcup \mathsf K_2)

## 예
작은 그래프의 데카르트 곱에 대하여 다음이 성립한다. 여기서 \mathsf K_i는 완전 그래프이며, \bar{\mathsf K}_i는 무변 그래프이며, \mathsf C_i는 순환 그래프이며, \mathsf P_i는 경로 그래프이다. \Gamma는 임의의 그래프이다.
:\mathsf K_1 \, \square\, \Gamma = \Gamma
:\mathsf K_2 \,\square\, \mathsf K_2 = \mathsf C_4
:\mathsf K_2 \, \square\, \mathsf C_4 =  정육면체 그래프
:\bar{\mathsf K}_i \,\square\,\bar{\mathsf K}_j = \bar{\mathsf K}_{ij}
:\bar{\mathsf K}_i \,\square\, \Gamma = \Gamma^{\sqcup i}


Circle graph C4.svg|\mathsf K_2 \,\square\,\mathsf K_2
0-regular graph.svg|\bar{\mathsf K}_2 \,\square\,\bar{\mathsf K}_3
1-regular graph.svg|\bar{\mathsf K}_3 \,\square\,\mathsf K_2
2-regular graph.svg|\bar{\mathsf K}_2 \,\square\, \mathsf K_3
3-regular graph.svg|\mathsf K_3\,\square\,\mathsf K_2
Cube skeleton.svg|\mathsf K_2\,\square\,\mathsf K_2\,\square\,\mathsf K_2
3-3 duoprism ortho square.png|\mathsf P_3\,\square\,\mathsf P_3
Paley9-perfect.svg|\mathsf K_3\,\square\,\mathsf K_3
Pentagonal prismatic graph.svg|\mathsf C_5\,\square\,\mathsf K_2
Hexagonal prismatic graph.svg|\mathsf C_6\,\square\,\mathsf K_2
Median graph.svg|\mathsf K_2\,\square\,\mathsf K_2\,\square\,\mathsf P_3
4-3 duoprism.png|\mathsf K_2\,\square\,\mathsf K_2\,\square\,\mathsf K_3
Heptagonal prismatic graph.svg|\mathsf C_7\,\square\,\mathsf K_2
5-3 duoprism.png|\mathsf C_5 \,\square\,\mathsf K_3
Hypercubecentral.svg|\mathsf K_2\,\square\,\mathsf K_2\,\square\,\mathsf K_2\,\square\,\mathsf K_2
Ladder graph L8.svg|\mathsf P_8\,\square\,\mathsf K_2
Rook's graph.svg|\mathsf K_8\,\square\,\mathsf K_8


## 역사
그래프 데카르트 곱은 1912년에 알프레드 노스 화이트헤드와 버트런드 러셀이 《수학 원리》 2권에서 최초로 사용하였다. 이후 게르트 자비두시(, 1929〜)가 1960년에 이 연산을 재발견하였다.

## 참고 문헌

## 외부 링크
* 

분류:이항연산
분류:그래프