그래프 데카르트 곱
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
그래프 데카르트 곱은 그래프의 족의 곱으로, 그래프를 범주로 간주할 때 재미있는 텐서 곱에 해당한다. 두 그래프의 데카르트 곱은 두 그래프의 꼭짓점들의 순서쌍을 꼭짓점으로 하고, 특정 조건을 만족하는 순서쌍들을 변으로 연결하여 구성된다. 그래프 데카르트 곱은 결합 법칙과 교환 법칙을 따르며, 두 그래프의 데카르트 곱의 채색수는 각 그래프의 채색수 중 최댓값과 같다. 또한, 연결 그래프는 데카르트 소 그래프들의 곱으로 유일하게 표현될 수 있으며, 대수적 그래프 이론을 통해 분석할 수 있다. 그래프 데카르트 곱은 1912년 화이트헤드와 러셀에 의해 처음 사용되었고, 자비두시에 의해 재발견되었다.
더 읽어볼만한 페이지
- 그래프 - 매케이 화살집
매케이 화살집은 유한군 G의 기약 표현을 꼭짓점으로, 텐서곱 분해를 통해 변을 정의하여 군의 표현론적 구조를 시각적으로 나타내는 도구이다. - 그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 Kn으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다. - 이항연산 - 뺄셈
뺄셈은 두 수의 관계를 나타내는 연산으로, 덧셈의 역연산이며, 피감수에서 감수를 빼는 연산으로 차를 구하고, 반교환법칙과 결합 법칙은 성립하지 않으며, 다양한 계산 방법과 함께 여러 분야에서 활용된다. - 이항연산 - 나눗셈
나눗셈은 하나의 수를 다른 수로 나누어 몫과 나머지를 구하는 기본적인 산술 연산이다.
그래프 데카르트 곱 |
---|
2. 정의
그래프의 족 의 '''그래프 데카르트 곱'''은 각 그래프들의 꼭짓점 집합들의 데카르트 곱을 꼭짓점 집합으로 가지며, 특정한 조건을 만족하는 변들로 구성된 그래프이다. 두 그래프 , 의 데카르트 곱은 으로 표기한다.
2. 1. 기본 정의
그래프의 족 의 '''그래프 데카르트 곱''' 은 다음과 같은 그래프이다.:
:
즉, 데카르트 곱 는 다음과 같은 그래프이다.
- 그 꼭짓점 은 각 성분 의 꼭짓점들의 열 , 이다.
- 두 꼭짓점 이 변으로 연결되어 있을 필요충분조건은 어떤 성분 에 대하여, 와 가 그래프 에서 변으로 연결되며, 나머지 성분들이 모두 일치하는 것이다.
두 그래프 , 의 데카르트 곱은 으로 표기한다.
2. 2. 다른 표현
그래프의 족 의 '''그래프 데카르트 곱''' 은 다음과 같은 그래프이다.:
:
즉, 데카르트 곱 는 다음과 같다.
- 꼭짓점 은 각 성분 의 꼭짓점들의 열 , 이다.
- 두 꼭짓점 이 변으로 연결되어 있을 필요충분조건은 어떤 성분 에 대하여, 와 가 그래프 에서 변으로 연결되며, 나머지 성분들이 모두 일치하는 것이다.
두 그래프 , 의 데카르트 곱은 으로 표기한다.
3. 성질
그래프 데카르트 곱은 여러 흥미로운 성질들을 가지고 있으며, 그 중 일부는 하위 섹션에서 자세히 다루어졌다.
- 결합 법칙 및 교환 법칙: 그래프 데카르트 곱은 결합 법칙과 교환 법칙을 만족한다. 즉, 그래프들의 순서를 바꾸거나 괄호를 묶는 방식을 달리해도 결과는 (그래프 동형 아래) 동일하다.
- 항등원: 한원소 그래프 는 데카르트 곱의 항등원 역할을 한다. 즉, 어떤 그래프와 의 데카르트 곱은 원래 그래프와 같다.
- 인수분해: 연결 그래프는 소인수 그래프들의 데카르트 곱으로 유일하게 인수분해될 수 있다.[1] 그러나 연결되지 않은 그래프는 이러한 인수분해가 유일하지 않을 수 있다.
- 정점 이동성: 데카르트 곱이 정점 이동 그래프가 되기 위한 필요충분조건은 각 인수가 정점 이동 그래프인 것이다.[2]
- 이분성: 데카르트 곱이 이분 그래프가 되기 위한 필요충분조건은 각 인수가 이분 그래프인 것이다.
- 단위 거리 그래프: 단위 거리 그래프의 데카르트 곱은 또 다른 단위 거리 그래프가 된다.[3]
- 효율적인 인식: 데카르트 곱 그래프는 선형 시간 안에 효율적으로 인식될 수 있다.[3]
다음 성질들은 하위 섹션에서 더 자세히 다루고 있다.
- 꼭짓점과 변의 개수 (하위 섹션 '꼭짓점과 변의 개수' 참조)
- 인접 행렬 (하위 섹션 '인접 행렬' 참조)
- 채색수 (하위 섹션 '채색수' 참조)
- 독립수 (하위 섹션 '독립수' 참조)
- 지배수 (하위 섹션 '지배수' 참조)
- 거리 (하위 섹션 '거리' 참조)
- 데카르트 곱 분해 (하위 섹션 '데카르트 곱 분해' 참조)
3. 1. 기본 성질
그래프 데카르트 곱은 (표준적 그래프 동형 아래) 결합 법칙과 교환 법칙을 따른다. 그래프 데카르트 곱의 항등원은 한원소 그래프 이다.두 그래프 , 에 대하여 다음이 성립한다.[1]
:
:
(무한 그래프의 경우 이는 기수의 연산으로 해석한다.)
연결 그래프가 데카르트 곱이면 소인수, 즉 그래프 곱으로 분해될 수 없는 그래프의 곱으로 고유하게 인수분해될 수 있다. 그러나 Imrich & Klavžar (2000)는 소수 그래프의 데카르트 곱으로 두 가지 방식으로 표현될 수 있는 연결되지 않은 그래프를 설명한다.
:
여기서 더하기 기호는 분리 집합을 나타내고 위첨자는 데카르트 곱에 대한 지수를 나타낸다.
데카르트 곱은 각 인수가 정점 이동 그래프이기 위한 필요충분 조건이다.[2]
데카르트 곱은 각 인수가 이분 그래프이기 위한 필요충분 조건이다. 더 일반적으로 데카르트 곱의 채색수는 다음 방정식을 만족한다.
:
3. 2. 꼭짓점과 변의 개수
두 그래프 , 에 대하여 다음이 성립한다.[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. 인접 행렬
두 유한 그래프 와 의 데카르트 곱의 인접 행렬은 다음과 같다.:
여기서 는 행렬의 크로네커 곱이다.
특히, 의 스펙트럼(인접 행렬의 고윳값의 중복집합)은 와 의 스펙트럼의 합이다.
:
3. 4. 채색수
유한한 채색수를 가진, 하나 이상의 꼭짓점을 갖는 두 그래프 , (유한 또는 무한)의 데카르트 곱의 채색수는 각 그래프의 채색수 가운데 최댓값이다. (두 그래프 가운데 하나가 꼭짓점을 갖지 않는다면 그 데카르트 곱의 채색수는 자명하게 0이다.):
'''증명:'''
또는 가운데 적어도 하나가 꼭짓점을 갖지 않는 경우는 자명하다. 따라서 둘 다 공그래프가 아니라고 가정하자.
편의상
:
으로 표기하자. 채색
:
:
이 주어졌을 때,
:
:
는 위의 채색을 이룬다. 따라서
:
이다. 그러나 와 은 둘 다 의 부분 그래프이다. 따라서
:
이다.
특히, 두 그래프의 데카르트 곱이 이분 그래프일 필요충분조건은 다음과 같다.
- 둘 다 이분 그래프이거나, 또는 둘 가운데 하나가 이다.
더 일반적으로 데카르트 곱의 채색수는 다음 방정식을 만족한다.
:[2]
Hedetniemi 추측은 그래프의 텐서 곱에 대한 관련 등식을 나타낸다.
3. 5. 독립수
가 보여준 것처럼 데카르트 곱의 독립수는 다음 부등식을 만족한다.:
Vizing 추측은 데카르트 곱의 지배수가 다음 부등식을 만족한다고 명시한다.
:
3. 6. 지배수
Vizing 추측은 데카르트 곱의 지배수가 다음 부등식을 만족한다고 명시한다.[1]:
3. 7. 거리
단위 거리 그래프의 데카르트 곱은 또 다른 단위 거리 그래프이다.[3]3. 8. 데카르트 곱 분해
한원소 그래프 이 아닌 두 그래프의 데카르트 곱으로 표현될 수 없는 그래프를 '''데카르트 소 그래프'''(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. 특수 그래프
는 완전 그래프, 는 무변 그래프, 는 순환 그래프, 는 경로 그래프를 나타내며, 는 임의의 그래프를 나타낸다. 작은 그래프의 데카르트 곱에 대해 다음이 성립한다.- 정육면체 그래프
- 두 변의 데카르트 곱은 네 개의 꼭짓점을 가진 사이클이다: K2□K2 = C4.
- K2와 경로 그래프의 데카르트 곱은 사다리 그래프이다.
- 두 경로 그래프의 데카르트 곱은 그리드 그래프이다.
- ''n''개의 변의 데카르트 곱은 하이퍼큐브이다.
- 따라서, 두 하이퍼큐브 그래프의 데카르트 곱은 또 다른 하이퍼큐브이다: Qi□Qj = Qi+j.
- 두 중앙값 그래프의 데카르트 곱은 또 다른 중앙값 그래프이다.
- n-각기둥의 꼭짓점과 변으로 이루어진 그래프는 데카르트 곱 그래프 K2□Cn이다.
- 룩 그래프는 두 완전 그래프의 데카르트 곱이다.
5. 대수적 그래프 이론
대수적 그래프 이론은 그래프 데카르트 곱을 분석하는 데 사용될 수 있다. 그래프 이 개의 정점을 가지고 인접 행렬 을 가지며, 그래프 가 개의 정점을 가지고 인접 행렬 를 가진다면, 두 그래프의 데카르트 곱의 인접 행렬은 인자들의 인접 행렬의 크로네커 합으로 주어진다.
5. 1. 인접 행렬 표현
두 유한 그래프 , 의 데카르트 곱의 인접 행렬은 다음과 같다.:
여기서 는 행렬의 크로네커 곱이다.
특히, 의 스펙트럼(인접 행렬의 고윳값의 중복집합)은 와 의 스펙트럼의 합이다.
:
대수적 그래프 이론은 그래프의 데카르트 곱을 분석하는 데 사용될 수 있다.
그래프 이 개의 정점과 인접 행렬 을 가지고, 그래프 가 개의 정점과 인접 행렬 를 가진다면, 두 그래프의 데카르트 곱의 인접 행렬은 다음과 같이 주어진다.
: ,
여기서 는 행렬의 크로네커 곱을 나타내고 은 항등 행렬을 나타낸다. 따라서 데카르트 곱의 인접 행렬은 인자들의 인접 행렬의 크로네커 합이다.
6. 범주론
그래프를 범주로 생각하면, 꼭짓점은 대상이 되고 변은 그래프의 경로가 된다. 이 경우 그래프 데카르트 곱은 범주의 [https://ncatlab.org/nlab/show/funny+tensor+product 재미있는 텐서 곱]에 해당한다. 그래프 데카르트 곱은 그래프와 그래프 준동형 사상의 범주를 대칭 닫힌 모노이드 범주로 만드는 두 가지 그래프 곱 가운데 하나이며, 다른 하나는 그래프의 텐서 곱이다. 데카르트 곱 와 의 내부 호환 은 에서 로의 그래프 준동형 사상을 꼭짓점으로 가지고, 그 사이의 "[https://ncatlab.org/nlab/show/unnatural+transformation 부자연스러운 변환]"을 변으로 갖는다.
6. 1. 그래프 범주
그래프를 범주로 간주하면 객체는 정점이고 사상은 그래프의 경로이며, 그래프의 데카르트 곱은 범주의 [https://ncatlab.org/nlab/show/funny+tensor+product 재미있는 텐서 곱]에 해당한다. 그래프의 데카르트 곱은 그래프와 그래프 준동형 사상의 범주를 (단순히 대칭 모노이드가 아닌) 대칭 닫힌 모노이드 범주로 만드는 두 가지 그래프 곱 중 하나이며, 다른 하나는 그래프의 텐서 곱이다. 데카르트 곱 와 의 내부 호환 은 에서 로의 그래프 준동형 사상을 정점으로 가지고, 그 사이의 "[https://ncatlab.org/nlab/show/unnatural+transformation 부자연스러운 변환]"을 변으로 갖는다.6. 2. 닫힌 모노이드 범주
그래프를 범주로 간주하면 객체는 정점이고 사상은 그래프의 경로이며, 그래프의 데카르트 곱은 범주의 [https://ncatlab.org/nlab/show/funny+tensor+product 재미있는 텐서 곱]에 해당한다. 그래프의 데카르트 곱은 그래프와 그래프 준동형 사상의 범주를 (단순히 대칭 모노이드가 아닌) 대칭 닫힌 모노이드 범주로 만드는 두 가지 그래프 곱 중 하나이며, 다른 하나는 그래프의 텐서 곱이다. 데카르트 곱 와 의 내부 호환 은 에서 로의 그래프 준동형 사상을 정점으로 가지고, 그 사이의 "[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