맨위로가기

그래프 데카르트 곱

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

1. 개요

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

더 읽어볼만한 페이지

  • 그래프 - 매케이 화살집
    매케이 화살집은 유한군 G의 기약 표현을 꼭짓점으로, 텐서곱 분해를 통해 변을 정의하여 군의 표현론적 구조를 시각적으로 나타내는 도구이다.
  • 그래프 - 완전 그래프
    완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 Kn으로 표기되며 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_iv_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_iv_i그래프 \Gamma_i에서 변으로 연결되며, 나머지 성분들이 모두 일치하는 것이다.


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

3. 성질

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


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


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

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

3. 1. 기본 성질

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

그래프 \Gamma, \Gamma'에 대하여 다음이 성립한다.[1]

:\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),

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

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

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

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

3. 2. 꼭짓점과 변의 개수

그래프 \Gamma, \Gamma'에 대하여 다음이 성립한다.[1]

꼭짓점의 개수\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) \}.[2]

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 추측은 데카르트 곱의 지배수가 다음 부등식을 만족한다고 명시한다.[1]

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

3. 7. 거리

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

3. 8. 데카르트 곱 분해

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

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

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

4. 예시


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

4. 1. 기본 그래프

Ki영어완전 그래프이며, 는 무변 그래프이며, Ci영어순환 그래프이며, Pi영어경로 그래프이다. Γ영어는 임의의 그래프이다.

  • K1 □ Γ = Γ영어
  • K2 □ K2 = C4영어
  • K2 □ C4 = 영어 정육면체 그래프
  • j = ij}}






  • 두 변의 데카르트 곱은 네 개의 꼭짓점을 가진 사이클이다: K2□K2 = C4영어.
  • K2영어경로 그래프의 데카르트 곱은 사다리 그래프이다.
  • 두 경로 그래프의 데카르트 곱은 그리드 그래프이다.
  • ''n''개의 변의 데카르트 곱은 하이퍼큐브이다:
  • (K2)□n = Qn.영어
  • 두 하이퍼큐브 그래프의 데카르트 곱은 또 다른 하이퍼큐브이다: Qi□Qj = Qi+j영어.
  • 두 중앙값 그래프의 데카르트 곱은 또 다른 중앙값 그래프이다.
  • n-각기둥의 꼭짓점과 변으로 이루어진 그래프는 데카르트 곱 그래프 K2□Cn영어이다.
  • 룩 그래프는 두 완전 그래프의 데카르트 곱이다.

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}

  • 두 변의 데카르트 곱은 네 개의 꼭짓점을 가진 사이클이다: K2□K2 = C4.
  • K2경로 그래프의 데카르트 곱은 사다리 그래프이다.
  • 두 경로 그래프의 데카르트 곱은 그리드 그래프이다.
  • ''n''개의 변의 데카르트 곱은 하이퍼큐브이다.
  • (K_2)^{\square n} = Q_n.
  • 따라서, 두 하이퍼큐브 그래프의 데카르트 곱은 또 다른 하이퍼큐브이다: Qi□Qj = Qi+j.
  • 두 중앙값 그래프의 데카르트 곱은 또 다른 중앙값 그래프이다.
  • n-각기둥의 꼭짓점과 변으로 이루어진 그래프는 데카르트 곱 그래프 K2□Cn이다.
  • 룩 그래프는 두 완전 그래프의 데카르트 곱이다.

5. 대수적 그래프 이론

대수적 그래프 이론은 그래프 데카르트 곱을 분석하는 데 사용될 수 있다. 그래프 G_1n_1개의 정점을 가지고 n_1\times n_1 인접 행렬 \mathbf A_1을 가지며, 그래프 G_2n_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_1n_1개의 정점과 n_1\times n_1 인접 행렬 \mathbf A_1을 가지고, 그래프 G_2n_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_nn\times n 항등 행렬을 나타낸다. 따라서 데카르트 곱의 인접 행렬은 인자들의 인접 행렬의 크로네커 합이다.

6. 범주론

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

6. 1. 그래프 범주

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

6. 2. 닫힌 모노이드 범주

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

7. 역사

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

참조

[1] 학술 1960
[2] 학술 2000
[3] 학술 2007
[4] 서적 Principia Mathematica. Volume 2 1912
[5] 저널 Graph multiplication 1960



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com