그래프 데카르트 곱: 두 판 사이의 차이

내용 삭제됨 내용 추가됨

인라인

2018년 7월 2일 (월) 07:05 판

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

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

정의

그래프의 족 $(\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_{i}v_{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 \neq \varnothing \neq \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 ')\leq N

이다. 그러나 $\Gamma$ 와 $\Gamma '$ 은 둘 다 $\Gamma \,\square \,\Gamma '$ 의 부분 그래프이다. 따라서

\chi (\Gamma \,\square \,\Gamma ')\geq N

이다.

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

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

데카르트 곱 분해

한원소 그래프 ${\mathsf {K}}_{1}$ 이 아닌 두 그래프의 데카르트 곱으로 표현될 수 없는 그래프를 데카르트 소 그래프(Descartes素graph,영어: Cartesian-prime 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}^{\square 2}\sqcup {\mathsf {K}}_{2}^{\square 4})\,\square ({\mathsf {K}}_{1}\sqcup {\mathsf {K}}_{2})

예

작은 그래프의 데카르트 곱에 대하여 다음이 성립한다. 여기서 ${\mathsf {K}}_{i}$ 는 완전 그래프이며, ${\bar {\mathsf {K}}}_{i}$ 는 무변 그래프이며, ${\mathsf {C}}_{i}$ 는 순환 그래프이다. $\Gamma$ 는 임의의 그래프이다.