완전 그래프

틀:위키데이터 속성 추적 그래프 이론에서 완전 그래프(完全graph, 틀:Llang)는 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프이다.

정의

(단순) 그래프의 범주 $\mathrm{Graph}$ 위에, 그래프를 그 꼭짓점 집합으로 대응시키는 망각 함자 $V:\mathrm{Graph}\to \mathrm{Set}$가 존재한다. 이 함자는 오른쪽 수반 함자를 갖는다.

$K:\mathrm{Set}\to \mathrm{Graph}$

$V⊣K$

이 경우, 집합 $S$에 대하여, $K(S)$를 $S$ 위의 완전 그래프라고 한다.

구체적으로, 집합 $S$ 위의 완전 그래프 $K(S)$는 다음과 같다.

• $V(K(S))=S$
• $uv\in E(K(S))⟺u\ne v$

즉, 완전 그래프는 주어진 꼭짓점들에 대하여 가능한 모든 변들을 갖는 그래프이다.

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

성질

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

완전 그래프 $K(S)$의 여 그래프는 무변 그래프 $\overline{K}(S)$이다.

예

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

• 
  $K_1$
• 
  $K_2$
• 
  $K_3$
• 
  $K_4$
• 
  $K_5$
• 
  $K_6$
• 
  $K_7$
• 
  $K_8$

외부 링크

• 틀:매스월드

같이 보기

• 램지의 정리