완전 그래프

1. 개요

완전 그래프는 주어진 꼭짓점들 사이에 가능한 모든 변을 갖는 단순 그래프이다. 집합 S에 대한 완전 그래프 K(S)는 S를 꼭짓점으로 가지고, 서로 다른 모든 두 꼭짓점 사이에 변을 갖는다. 크기가 같은 두 집합의 완전 그래프는 동형이며, 크기가 κ인 집합의 완전 그래프는 K_κ로 표기한다.

n개의 꼭짓점을 가진 유한 완전 그래프 K_n은 n(n-1)/2개의 변을 가지며, 모든 꼭짓점의 차수는 n-1이다. 모든 완전 그래프는 그 자체로 클리크를 이루며, 여 그래프는 무변 그래프이다. 완전 그래프의 각 변에 방향을 부여하면 토너먼트가 된다. 완전 그래프는 기하학적 및 위상수학적 성질을 가지며, K₁부터 K₄까지는 평면 그래프이지만, 다섯 개 이상의 꼭짓점을 가진 완전 그래프는 비평면 그래프이다.

2. 정의

(단순) 그래프의 범주 $\backslash operatorname\{Graph\}$ 위에, 그래프를 그 꼭짓점 집합으로 대응시키는 망각 함자 $V\backslash colon\backslash operatorname\{Graph\}\backslash to\backslash operatorname\{Set\}$가 존재한다. 이 함자는 오른쪽 수반 함자를 갖는다.
:$K\backslash colon\backslash operatorname\{Set\}\backslash to\backslash operatorname\{Graph\}$
:$V\backslash dashv\; K$
이 경우, 집합 $S$에 대하여, $K(S)$를 $S$ 위의 완전 그래프라고 한다.

구체적으로, 집합 $S$ 위의 완전 그래프 $K(S)$는 다음과 같다.
* $V(K(S))=S$
* $uv\backslash in\; E(K(S))\backslash iff\; u\backslash ne\; v$
즉, 완전 그래프는 주어진 꼭짓점들에 대하여 가능한 모든 변들을 갖는 그래프이다.

서로 크기가 같은 두 집합의 완전 그래프는 서로 동형이다. 집합의 크기가 기수 $\backslash kappa$인 집합의 완전 그래프를 $K\_\backslash kappa$라고 한다.

3. 성질

유한 완전 그래프 $K\_n$은 $n(n-1)/2$개의 변을 가지며, 모든 꼭짓점은 차수 $n-1$을 갖는 정규 그래프이다. 모든 완전 그래프는 그 자체로 클릭을 이룬다.

완전 그래프 $K(S)$의 여 그래프는 무변 그래프 $\backslash bar\; K(S)$이다.

완전 그래프의 각 변에 방향을 부여하면, 결과 유향 그래프는 토너먼트라고 한다.

$K\_n$은 $T\_i$가 $i$개의 정점을 갖도록 $n$개의 트리 $T\_i$로 분해될 수 있다. 링겔의 추측은 완전 그래프 $K\_\{2n+1\}$이 $n$개의 변을 가진 임의의 트리의 복사본으로 분해될 수 있는지 묻는다. 이것은 충분히 큰 $n$에 대해 참인 것으로 알려져 있다.

완전 그래프의 매칭 수는 전화 번호로 주어지며, $n$-정점 그래프에 대한 호소야 지수의 가장 큰 가능한 값을 제공한다. 완전 그래프 $K\_n$ ($n$이 짝수)의 완전 매칭 수는 이중 계승 $(n-1)!!$로 주어진다.

교차수는 $K\_\{27\}$까지 알려져 있으며, $K\_\{28\}$은 7233 또는 7234개의 교차점을 필요로 한다. 추가 값은 Rectilinear Crossing Number 프로젝트에서 수집된다.

3.1. 기하학적 및 위상수학적 성질

n^영어개의 노드를 가진 완전 그래프는 (n-1)-단순체의 모서리를 나타낸다. 기하학적으로 K₃는 삼각형의 모서리 집합을, K₄는 사면체 등을 형성한다. 토러스의 위상을 가진 비볼록 다면체인 차사르 다면체는 완전 그래프 K₇을 골격으로 갖는다. 4차원 이상의 모든 이웃 다면체 역시 완전 골격을 가지고 있다.

K₁부터 K₄까지는 모두 평면 그래프이다. 그러나 다섯 개 이상의 꼭짓점을 가진 완전 그래프의 모든 평면 그림은 교차점을 포함해야 하며, 비평면 완전 그래프 K₅는 평면 그래프의 특성에서 중요한 역할을 한다. 쿠라토프스키 정리에 따르면, 그래프는 K₅나 완전 이분 그래프 K_3,3을 세분으로 포함하지 않는 경우에만 평면 그래프이며, 바그너의 정리에 따르면 세분 대신 그래프 마이너에 대해서도 동일한 결과가 적용된다. 피터슨 패밀리의 일부로서, K₆는 링크 없는 임베딩에 대한 금지된 마이너 중 하나로 유사한 역할을 한다. 즉, 콘웨이와 고든이 증명했듯이, K₆을 3차원 공간에 임베딩하면 최소한 한 쌍의 연결된 삼각형을 가진 본질적으로 꼬여 있다. 콘웨이와 고든은 또한 K₇의 모든 3차원 임베딩이 공간에 비자명 매듭으로 임베딩된 해밀턴 사이클을 포함한다는 것을 보여주었다.

4. 예시

꼭짓점을 1개 ~ 8개 가지는 완전 그래프는 다음과 같다.

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

1에서 12까지의 정점 n에 대한 완전 그래프는 가장자리 수와 함께 아래에 표시된다.