완전 그래프

그래프 이론에서 완전 그래프(complete graph)는 서로 다른 두개의 정점이 반드시 하나의 간선으로 연결된 그래프이다.

n개의 정점을 가지는 완전 그래프는 $K_n$으로 나타낸다. $K_n$은 $\frac{n(n-1)}{2}$개의 변을 가지는데, 이것은 n개의 정점 중에서 시작점과 끝점에 해당하는 2개를 선택하는 경우의 수 ${n \choose 2}$에서 확인할 수 있다. $K_n$은 n-1의 차수를 가지는 정규 그래프이다. 모든 완전 그래프는 그 자체로 클릭(clique)이다.

다음 그래프는 각각 꼭지점을 1개 ~ 8개 가지는 완전 그래프의 그림이다.

• 

  $K_1$

• 

  $K_2$

• 

  $K_3$

• 

  $K_4$

• 

  $K_5$

• 

  $K_6$

• 

  $K_7$

• 

  $K_8$