그래프 데카르트 곱

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

그래프 데카르트 곱은 그래프의 족의 곱으로, 그래프를 범주로 간주할 때 재미있는 텐서 곱에 해당한다. 두 그래프의 데카르트 곱은 두 그래프의 꼭짓점들의 순서쌍을 꼭짓점으로 하고, 특정 조건을 만족하는 순서쌍들을 변으로 연결하여 구성된다. 그래프 데카르트 곱은 결합 법칙과 교환 법칙을 따르며, 두 그래프의 데카르트 곱의 채색수는 각 그래프의 채색수 중 최댓값과 같다. 또한, 연결 그래프는 데카르트 소 그래프들의 곱으로 유일하게 표현될 수 있으며, 대수적 그래프 이론을 통해 분석할 수 있다. 그래프 데카르트 곱은 1912년 화이트헤드와 러셀에 의해 처음 사용되었고, 자비두시에 의해 재발견되었다.

그래프 데카르트 곱

📚 더 읽어볼만한 페이지

그래프 - 매케이 화살집
매케이 화살집은 유한군 G의 기약 표현을 꼭짓점으로, 텐서곱 분해를 통해 변을 정의하여 군의 표현론적 구조를 시각적으로 나타내는 도구이다.
그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K<sub>n</sub>으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.
이항연산 - 뺄셈
뺄셈은 두 수의 관계를 나타내는 연산으로, 덧셈의 역연산이며, 피감수에서 감수를 빼는 연산으로 차를 구하고, 반교환법칙과 결합 법칙은 성립하지 않으며, 다양한 계산 방법과 함께 여러 분야에서 활용된다.
이항연산 - 나눗셈
나눗셈은 하나의 수를 다른 수로 나누어 몫과 나머지를 구하는 기본적인 산술 연산이다.

2. 정의

그래프의 족 $(\Gamma_i)_{i\in I}$ 의 그래프 데카르트 곱은 각 그래프들의 꼭짓점 집합들의 데카르트 곱을 꼭짓점 집합으로 가지며, 특정한 조건을 만족하는 변들로 구성된 그래프이다. 두 그래프 $\Gamma$ , $\Gamma'$ 의 데카르트 곱은 $\Gamma\,\square\, \Gamma'$ 으로 표기한다.

2.1. 기본 정의

그래프의 족 $(\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'$ 으로 표기한다.

2.2. 다른 표현

그래프의 족 $(\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'$ 으로 표기한다.

3. 성질

그래프 데카르트 곱은 여러 흥미로운 성질들을 가지고 있으며, 그 중 일부는 하위 섹션에서 자세히 다루어졌다.

* 결합 법칙 및 교환 법칙: 그래프 데카르트 곱은 결합 법칙과 교환 법칙을 만족한다. 즉, 그래프들의 순서를 바꾸거나 괄호를 묶는 방식을 달리해도 결과는 (그래프 동형 아래) 동일하다.
* 항등원: 한원소 그래프 $\mathsf K_1$ 는 데카르트 곱의 항등원 역할을 한다. 즉, 어떤 그래프와 $\mathsf K_1$ 의 데카르트 곱은 원래 그래프와 같다.
* 인수분해: 연결 그래프는 소인수 그래프들의 데카르트 곱으로 유일하게 인수분해될 수 있다. 그러나 연결되지 않은 그래프는 이러한 인수분해가 유일하지 않을 수 있다.
* 정점 이동성: 데카르트 곱이 정점 이동 그래프가 되기 위한 필요충분조건은 각 인수가 정점 이동 그래프인 것이다.
* 이분성: 데카르트 곱이 이분 그래프가 되기 위한 필요충분조건은 각 인수가 이분 그래프인 것이다.
* 단위 거리 그래프: 단위 거리 그래프의 데카르트 곱은 또 다른 단위 거리 그래프가 된다.
* 효율적인 인식: 데카르트 곱 그래프는 선형 시간 안에 효율적으로 인식될 수 있다.

다음 성질들은 하위 섹션에서 더 자세히 다루고 있다.

* 꼭짓점과 변의 개수 (하위 섹션 '꼭짓점과 변의 개수' 참조)
* 인접 행렬 (하위 섹션 '인접 행렬' 참조)
* 채색수 (하위 섹션 '채색수' 참조)
* 독립수 (하위 섹션 '독립수' 참조)
* 지배수 (하위 섹션 '지배수' 참조)
* 거리 (하위 섹션 '거리' 참조)
* 데카르트 곱 분해 (하위 섹션 '데카르트 곱 분해' 참조)

3.1. 기본 성질

그래프 데카르트 곱은 (표준적 그래프 동형 아래) 결합 법칙과 교환 법칙을 따른다. 그래프 데카르트 곱의 항등원은 한원소 그래프 $\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)|$

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

연결 그래프가 데카르트 곱이면 소인수, 즉 그래프 곱으로 분해될 수 없는 그래프의 곱으로 고유하게 인수분해될 수 있다. 그러나 Imrich & Klavžar (2000)는 소수 그래프의 데카르트 곱으로 두 가지 방식으로 표현될 수 있는 연결되지 않은 그래프를 설명한다.

: $(K_1 + K_2 + K_2^2) \mathbin{\square} (K_1 + K_2^3) = (K_1 + K_2^2 + K_2^4) \mathbin{\square} (K_1 + K_2),$

여기서 더하기 기호는 분리 집합을 나타내고 위첨자는 데카르트 곱에 대한 지수를 나타낸다.

데카르트 곱은 각 인수가 정점 이동 그래프이기 위한 필요충분 조건이다.

데카르트 곱은 각 인수가 이분 그래프이기 위한 필요충분 조건이다. 더 일반적으로 데카르트 곱의 채색수는 다음 방정식을 만족한다.

: $\chi (G \mathbin{\square} H) = \max \{ \chi (G), \chi (H) \}.$

3.2. 꼭짓점과 변의 개수

두 그래프 $\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\| =

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

3.3. 인접 행렬

두 유한 그래프

\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'\}

3.4. 채색수

유한한 채색수를 가진, 하나 이상의 꼭짓점을 갖는 두 그래프 $\Gamma$ , $\Gamma'$ (유한 또는 무한)의 데카르트 곱의 채색수는 각 그래프의 채색수 가운데 최댓값이다. (두 그래프 가운데 하나가 꼭짓점을 갖지 않는다면 그 데카르트 곱의 채색수는 자명하게 0이다.)
: $\chi(\Gamma\,\square\,\Gamma') =\begin{cases}\max\{\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$ 이다.

더 일반적으로 데카르트 곱의 채색수는 다음 방정식을 만족한다.
: $\chi (G \mathbin{\square} H) = \max \{ \chi (G), \chi (H) \}.$
Hedetniemi 추측은 그래프의 텐서 곱에 대한 관련 등식을 나타낸다.

3.5. 독립수

가 보여준 것처럼 데카르트 곱의 독립수는 다음 부등식을 만족한다.

: $\alpha (G) \alpha (H) + \min \{ |V(G)| -\alpha (G), |V(H)| - \alpha (H) \} \le \alpha (G \mathbin{\square} H) \le \min \{ \alpha (G) |V(H)|, \alpha (H) |V(G)| \}.$

Vizing 추측은 데카르트 곱의 지배수가 다음 부등식을 만족한다고 명시한다.

: $\gamma (G \mathbin{\square} H) \ge \gamma (G) \gamma (H).$

3.6. 지배수

Vizing 추측은 데카르트 곱의 지배수가 다음 부등식을 만족한다고 명시한다.

: $\gamma (G \mathbin{\square} H) \ge \gamma (G) \gamma (H).$

3.7. 거리

단위 거리 그래프의 데카르트 곱은 또 다른 단위 거리 그래프이다.

3.8. 데카르트 곱 분해

한원소 그래프 $\mathsf K_1$ 이 아닌 두 그래프의 데카르트 곱으로 표현될 수 없는 그래프를 데카르트 소 그래프(Cartesian-prime graph^영어)라고 한다.

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

연결 그래프는 소인수, 즉 그래프 곱으로 분해될 수 없는 그래프의 곱으로 고유하게 인수분해될 수 있다.

4. 예시

* 두 변의 데카르트 곱은 네 개의 꼭짓점을 가진 사이클이다.
* K₂와 경로 그래프의 데카르트 곱은 사다리 그래프이다.
* 두 경로 그래프의 데카르트 곱은 그리드 그래프이다.
* n개 변의 데카르트 곱은 하이퍼큐브이다.
* 두 하이퍼큐브 그래프의 데카르트 곱은 또 다른 하이퍼큐브이다.
* 두 중앙값 그래프의 데카르트 곱은 또 다른 중앙값 그래프이다.
* n-각기둥의 꼭짓점과 변으로 이루어진 그래프는 K₂와 C_n의 데카르트 곱 그래프이다.
* 룩 그래프는 두 완전 그래프의 데카르트 곱이다.

4.1. 기본 그래프

K_i^영어는 완전 그래프이며, {{overline^영어는 무변 그래프이며, C_i^영어는 순환 그래프이며, P_i^영어는 경로 그래프이다. Γ^영어는 임의의 그래프이다.

* K₁ □ Γ = Γ^영어
* K₂ □ K₂ = C₄^영어
* K₂ □ C₄ = ^영어 정육면체 그래프
* {{overline^영어
* {{overline^영어

--
--
--
--
--
--
--

--
--
--
--
--
--

K2 □ K2 □ K2 □ K2}} — K₂ □ K₂ □ K₂ □ K₂}}

--
--

* 두 변의 데카르트 곱은 네 개의 꼭짓점을 가진 사이클이다: K₂□K₂ = C₄^영어.
* K₂^영어와 경로 그래프의 데카르트 곱은 사다리 그래프이다.
* 두 경로 그래프의 데카르트 곱은 그리드 그래프이다.
* n개의 변의 데카르트 곱은 하이퍼큐브이다:
* (K₂)^□n = Q_n.^영어
* 두 하이퍼큐브 그래프의 데카르트 곱은 또 다른 하이퍼큐브이다: Q_i□Q_j = Q_i+j^영어.
* 두 중앙값 그래프의 데카르트 곱은 또 다른 중앙값 그래프이다.
* n-각기둥의 꼭짓점과 변으로 이루어진 그래프는 데카르트 곱 그래프 K₂□C_n^영어이다.
* 룩 그래프는 두 완전 그래프의 데카르트 곱이다.

4.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}$

--
--
--
--
--
--
--

--
--
--
--
--
--

$\mathsf K_2\,\square\,\mathsf K_2\,\square\,\mathsf K_2\,\square\,\mathsf K_2$

--
--

* 두 변의 데카르트 곱은 네 개의 꼭짓점을 가진 사이클이다: K₂□K₂ = C₄.
* K₂와 경로 그래프의 데카르트 곱은 사다리 그래프이다.
* 두 경로 그래프의 데카르트 곱은 그리드 그래프이다.
* n개의 변의 데카르트 곱은 하이퍼큐브이다.
*

(K_2)^{\square n} = Q_n.

* 따라서, 두 하이퍼큐브 그래프의 데카르트 곱은 또 다른 하이퍼큐브이다: Q_i□Q_j = Q_i+j.
* 두 중앙값 그래프의 데카르트 곱은 또 다른 중앙값 그래프이다.
* n-각기둥의 꼭짓점과 변으로 이루어진 그래프는 데카르트 곱 그래프 K₂□C_n이다.
* 룩 그래프는 두 완전 그래프의 데카르트 곱이다.

5. 대수적 그래프 이론

대수적 그래프 이론은 그래프 데카르트 곱을 분석하는 데 사용될 수 있다. 그래프 $G_1$ 이 $n_1$ 개의 정점을 가지고 $n_1\times n_1$ 인접 행렬 $\mathbf A_1$ 을 가지며, 그래프 $G_2$ 가 $n_2$ 개의 정점을 가지고 $n_2\times n_2$ 인접 행렬 $\mathbf A_2$ 를 가진다면, 두 그래프의 데카르트 곱의 인접 행렬은 인자들의 인접 행렬의 크로네커 합으로 주어진다.

5.1. 인접 행렬 표현

두 유한 그래프 $\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'\}$
대수적 그래프 이론은 그래프의 데카르트 곱을 분석하는 데 사용될 수 있다.
그래프 $G_1$ 이 $n_1$ 개의 정점과 $n_1\times n_1$ 인접 행렬 $\mathbf A_1$ 을 가지고, 그래프 $G_2$ 가 $n_2$ 개의 정점과 $n_2\times n_2$ 인접 행렬 $\mathbf A_2$ 를 가진다면, 두 그래프의 데카르트 곱의 인접 행렬은 다음과 같이 주어진다.
: $\mathbf A_{1\mathbin{\square} 2} = \mathbf A_1 \otimes \mathbf I_{n_2} + \mathbf I_{n_1} \otimes \mathbf A_2$ ,
여기서 $\otimes$ 는 행렬의 크로네커 곱을 나타내고 $\mathbf I_n$ 은 $n\times n$ 항등 행렬을 나타낸다. 따라서 데카르트 곱의 인접 행렬은 인자들의 인접 행렬의 크로네커 합이다.

6. 범주론

그래프를 범주로 생각하면, 꼭짓점은 대상이 되고 변은 그래프의 경로가 된다. 이 경우 그래프 데카르트 곱은 범주의 [https://ncatlab.org/nlab/show/funny+tensor+product 재미있는 텐서 곱]에 해당한다. 그래프 데카르트 곱은 그래프와 그래프 준동형 사상의 범주를 대칭 닫힌 모노이드 범주로 만드는 두 가지 그래프 곱 가운데 하나이며, 다른 하나는 그래프의 텐서 곱이다. 데카르트 곱 $G$ 와 $H$ 의 내부 호환 $[G, H]$ 은 $G$ 에서 $H$ 로의 그래프 준동형 사상을 꼭짓점으로 가지고, 그 사이의 "[https://ncatlab.org/nlab/show/unnatural+transformation 부자연스러운 변환]"을 변으로 갖는다.

6.1. 그래프 범주

그래프를 범주로 간주하면 객체는 정점이고 사상은 그래프의 경로이며, 그래프의 데카르트 곱은 범주의 [https://ncatlab.org/nlab/show/funny+tensor+product 재미있는 텐서 곱]에 해당한다. 그래프의 데카르트 곱은 그래프와 그래프 준동형 사상의 범주를 (단순히 대칭 모노이드가 아닌) 대칭 닫힌 모노이드 범주로 만드는 두 가지 그래프 곱 중 하나이며, 다른 하나는 그래프의 텐서 곱이다. 데카르트 곱 $G$ 와 $H$ 의 내부 호환 $[G, H]$ 은 $G$ 에서 $H$ 로의 그래프 준동형 사상을 정점으로 가지고, 그 사이의 "[https://ncatlab.org/nlab/show/unnatural+transformation 부자연스러운 변환]"을 변으로 갖는다.

6.2. 닫힌 모노이드 범주

7. 역사

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