그래프 데카르트 곱

섬네일|right|그래프 데카르트 곱의 예. 5개의 꼭짓점 및 6개의 변을 갖는 그래프와 2개의 꼭짓점 및 1개의 변을 갖는 그래프의 데카르트 곱은 5×2=10개의 꼭짓점을 가지며, 5×1+2×6=17개의 변을 가진다.
그래프 이론에서 그래프 데카르트 곱(graph Descartes곱, )은 두 그래프를 합치는 이항 연산이다. 이렇게 얻은 그래프의 꼭짓점의 수는 원래 두 그래프의 꼭짓점의 수들의 곱과 같다.

 정의 
그래프의 족 의 그래프 데카르트 곱

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

즉, 데카르트 곱 는 다음과 같은 그래프이다.
 그 꼭짓점 은 각 성분 의 꼭짓점들의 열 , 이다.
 두 꼭짓점 이 변으로 연결되어 있을 필요 충분 조건은 어떤 성분 에 대하여, 와 가 그래프 에서 변으로 연결되며, 나머지 성분들이 모두 일치하는 것이다.

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

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

두 그래프 , 에 대하여 다음이 성립한다.

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

 인접 행렬 
두 유한 그래프 , 의 데카르트 곱의 인접 행렬은 다음과 같다.

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

특히, 의 스펙트럼(인접 행렬의 고윳값의 중복집합)은 와 의 스펙트럼의 합이다.

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

증명:
 또는  가운데 적어도 하나가 꼭짓점을 갖지 않는 경우는 자명하다. 따라서 둘 다 공그래프가 아니라고 가정하자.

편의상

으로 표기하자. 채색

이 주어졌을 때,

는  위의 채색을 이룬다. 따라서

이다. 그러나 와 은 둘 다 의 부분 그래프이다. 따라서

이다.

특히, 두 그래프의 데카르트 곱이 이분 그래프일 필요 충분 조건은 다음과 같다.
 둘 다 이분 그래프이거나, 또는 둘 가운데 하나가 이다.

 데카르트 곱 분해 
한원소 그래프 이 아닌 두 그래프의 데카르트 곱으로 표현될 수 없는 그래프를 데카르트 소 그래프(Descartes素graph,)라고 하자.

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

 예 
작은 그래프의 데카르트 곱에 대하여 다음이 성립한다. 여기서 는 완전 그래프이며, 는 무변 그래프이며, 는 순환 그래프이며, 는 경로 그래프이다. 는 임의의 그래프이다.

 정육면체 그래프

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

 참고 문헌 

 외부 링크 


분류:이항연산
분류:그래프