그래프 데카르트 곱

그래프 데카르트 곱의 예. 5개의 꼭짓점 및 5개의 변을 갖는 그래프와 4개의 꼭짓점 및 3개의 변을 갖는 그래프의 데카르트 곱은 5×4=20개의 꼭짓점을 가지며, 5×3+4×5=35개의 변을 가진다.

그래프 데카르트 곱의 예. 5개의 꼭짓점 및 6개의 변을 갖는 그래프와 2개의 꼭짓점 및 1개의 변을 갖는 그래프의 데카르트 곱은 5×2=10개의 꼭짓점을 가지며, 5×1+2×6=17개의 변을 가진다.

그래프 이론에서 그래프 데카르트 곱(graph Descartes곱, 틀:Llang)은 두 그래프를 합치는 이항 연산이다. 이렇게 얻은 그래프의 꼭짓점의 수는 원래 두 그래프의 꼭짓점의 수들의 곱과 같다.

정의

그래프의 족 $({\mathrm{\Gamma }}_i{)}_{i\in I}$의 그래프 데카르트 곱

$\mathrm{\Gamma }=\prod \coprod _{i\in I}{\mathrm{\Gamma }}_i$

은 다음과 같은 그래프이다.

$𝖵(\mathrm{\Gamma })=\prod _{i\in I}𝖵({\mathrm{\Gamma }}_i)$

$uv\in 𝖤(\mathrm{\Gamma })⟺\mathrm{\exists }i\in I:(u_i{v}_i\in 𝖤({\mathrm{\Gamma }}_i)\wedge \mathrm{\forall }j\in I\setminus \{i\}:u_i=v_j)$

즉, 데카르트 곱 $\mathrm{\Gamma }$는 다음과 같은 그래프이다.

• 그 꼭짓점 $v\in 𝖵(\mathrm{\Gamma })$은 각 성분 ${\mathrm{\Gamma }}_i$의 꼭짓점들의 열 $(v_i{)}_{i\in I}$, $v_i\in 𝖵({\mathrm{\Gamma }}_i)$이다.
• 두 꼭짓점 $u,v\in 𝖵(\mathrm{\Gamma })$이 변으로 연결되어 있을 필요 충분 조건은 어떤 성분 $i\in I$에 대하여, $u_i$와 $v_i$가 그래프 ${\mathrm{\Gamma }}_i$에서 변으로 연결되며, 나머지 성분들이 모두 일치하는 것이다.

두 그래프 $\mathrm{\Gamma }$, ${\mathrm{\Gamma }}^{\prime }$의 데카르트 곱은 $\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime }$으로 표기한다.

성질

그래프 데카르트 곱은 (표준적 그래프 동형 아래) 결합 법칙과 교환 법칙을 따른다. 그래프 데카르트 곱의 항등원은 한원소 그래프 ${𝖪}_1$이다.

두 그래프 $\mathrm{\Gamma }$, ${\mathrm{\Gamma }}^{\prime }$에 대하여 다음이 성립한다.

$\left|𝖵\left(\prod \coprod _{i\in I}{\mathrm{\Gamma }}_i\right)\right|=\prod _{i\in I}|𝖵({\mathrm{\Gamma }}_i)|$

$\left|𝖤\left(\prod \coprod _{i\in I}{\mathrm{\Gamma }}_i\right)\right|=\sum _{i\in I}|𝖤({\mathrm{\Gamma }}_i)|\prod _{j\in I\setminus \{i\}}|𝖵({\mathrm{\Gamma }}_j)|$

(무한 그래프의 경우 이는 기수의 연산으로 해석한다.)

인접 행렬

두 유한 그래프 $\mathrm{\Gamma }$, ${\mathrm{\Gamma }}^{\prime }$의 데카르트 곱의 인접 행렬은 다음과 같다.

${𝖠}_{\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime }}={𝖠}_{\mathrm{\Gamma }}\otimes 1_{𝖵({\mathrm{\Gamma }}^{\prime })}+1_{𝖵(\mathrm{\Gamma })}\otimes {𝖠}_{{\mathrm{\Gamma }}^{\prime }}$

여기서 $\otimes$는 행렬의 크로네커 곱이다.

특히, $\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime }$의 스펙트럼(인접 행렬의 고윳값의 중복집합)은 $\mathrm{\Gamma }$와 ${\mathrm{\Gamma }}^{\prime }$의 스펙트럼의 합이다.

$\mathrm{Spec}(\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime })=\mathrm{Spec}(\mathrm{\Gamma })+\mathrm{Spec}({\mathrm{\Gamma }}^{\prime })=\{\lambda +{\lambda }^{\prime }:\lambda \in \mathrm{Spec}\mathrm{\Gamma },{\lambda }^{\prime }\in \mathrm{Spec}{\mathrm{\Gamma }}^{\prime }\}$

채색수

유한한 채색수를 가진, 하나 이상의 꼭짓점을 갖는 두 (유한 또는 무한) 그래프 $\mathrm{\Gamma }$, ${\mathrm{\Gamma }}^{\prime }$의 데카르트 곱의 채색수는 각 그래프의 채색수 가운데 최댓값이다. (두 그래프 가운데 하나가 꼭짓점을 갖지 않는다면 그 데카르트 곱의 채색수는 자명하게 0이다.)

$\chi (\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime })=\{\begin{array}{cc}\underset{i\in I}{\max }\{\chi (\mathrm{\Gamma }),\chi ({\mathrm{\Gamma }}^{\prime })\}& (\mathrm{\Gamma }\ne \varnothing \ne {\mathrm{\Gamma }}^{\prime })\\ 0& (\varnothing \in \{\mathrm{\Gamma },{\mathrm{\Gamma }}^{\prime }\})\end{array}$

증명:

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

편의상

$N=\max \{\chi (\mathrm{\Gamma }),\chi ({\mathrm{\Gamma }}^{\prime })\}$

으로 표기하자. 채색

$c:𝖵(\mathrm{\Gamma })\to \mathbb{Z}/(N)$

$c^{\prime }:𝖵({\mathrm{\Gamma }}^{\prime })\to \mathbb{Z}/(N)$

이 주어졌을 때,

$C:𝖵(\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime })\to \mathbb{Z}/(N)$

$C:(v,v^{\prime })\mapsto c(v)+c^{\prime }(v^{\prime })$

는 $\mathrm{\Gamma }◻\mathrm{\Gamma }$ 위의 채색을 이룬다. 따라서

$\chi (\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime })\le N$

이다. 그러나 $\mathrm{\Gamma }$와 ${\mathrm{\Gamma }}^{\prime }$은 둘 다 $\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime }$의 부분 그래프이다. 따라서

$\chi (\mathrm{\Gamma }◻{\mathrm{\Gamma }}^{\prime })\ge N$

이다.

특히, 두 그래프의 데카르트 곱이 이분 그래프일 필요 충분 조건은 다음과 같다.

• 둘 다 이분 그래프이거나, 또는 둘 가운데 하나가 $\varnothing$이다.

데카르트 곱 분해

한원소 그래프 ${𝖪}_1$이 아닌 두 그래프의 데카르트 곱으로 표현될 수 없는 그래프를 데카르트 소 그래프(Descartes素graph,틀:Llang)라고 하자.

모든 연결 유한 그래프는 소 그래프들의 데카르트 곱으로 표현될 수 있으며, 이러한 표현은 (순서를 무시하면) 유일하다. 그러나 연결 그래프가 아닌 그래프의 경우 이러한 표현은 일반적으로 유일하지 않다. 예를 들어, 다음이 성립한다.

$({𝖪}_1\bigsqcup {𝖪}_2\bigsqcup {𝖪}_2^{◻2})◻({𝖪}_1\bigsqcup {𝖪}_2^{◻3})=({𝖪}_1\bigsqcup {𝖪}_2^{◻2}\bigsqcup {𝖪}_2^{◻4})◻({𝖪}_1\bigsqcup {𝖪}_2)$

예

작은 그래프의 데카르트 곱에 대하여 다음이 성립한다. 여기서 ${𝖪}_i$는 완전 그래프이며, ${\overline{𝖪}}_i$는 무변 그래프이며, ${𝖢}_i$는 순환 그래프이며, ${𝖯}_i$는 경로 그래프이다. $\mathrm{\Gamma }$는 임의의 그래프이다.

${𝖪}_1◻\mathrm{\Gamma }=\mathrm{\Gamma }$

${𝖪}_2◻{𝖪}_2={𝖢}_4$

${𝖪}_2◻{𝖢}_4=$ 정육면체 그래프

${\overline{𝖪}}_i◻{\overline{𝖪}}_j={\overline{𝖪}}_{ij}$

${\overline{𝖪}}_i◻\mathrm{\Gamma }={\mathrm{\Gamma }}^{\bigsqcup i}$

• 
  ${𝖪}_2◻{𝖪}_2$
• 
  ${\overline{𝖪}}_2◻{\overline{𝖪}}_3$
• 
  ${\overline{𝖪}}_3◻{𝖪}_2$
• 
  ${\overline{𝖪}}_2◻{𝖪}_3$
• 
  ${𝖪}_3◻{𝖪}_2$
• 
  ${𝖪}_2◻{𝖪}_2◻{𝖪}_2$
• 
  ${𝖯}_3◻{𝖯}_3$
• 
  ${𝖪}_3◻{𝖪}_3$
• 
  ${𝖢}_5◻{𝖪}_2$
• 
  ${𝖢}_6◻{𝖪}_2$
• 
  ${𝖪}_2◻{𝖪}_2◻{𝖯}_3$
• 
  ${𝖪}_2◻{𝖪}_2◻{𝖪}_3$
• 
  ${𝖢}_7◻{𝖪}_2$
• 
  ${𝖢}_5◻{𝖪}_3$
• 
  ${𝖪}_2◻{𝖪}_2◻{𝖪}_2◻{𝖪}_2$
• 
  ${𝖯}_8◻{𝖪}_2$
• 
  ${𝖪}_8◻{𝖪}_8$

역사

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

외부 링크

• 틀:매스월드