완전 그래프

완전 그래프(Complete graph)는 그래프 이론에서 그래프의 한 종류로, 그래프 내의 모든 정점이 서로 직접적으로 연결되어 있는 그래프를 말한다. 즉, 그래프 내의 임의의 두 정점을 선택했을 때, 그 두 정점을 연결하는 변(edge)이 항상 존재하는 그래프를 완전 그래프라고 정의한다.

• 기본 개념: n개의 정점을 가진 완전 그래프는 n( n - 1) / 2 개의 변을 가진다. 이는 모든 정점이 다른 모든 정점과 연결되어 있기 때문이다.

• 표기법: n개의 정점을 가진 완전 그래프는 통상적으로 *K_n*으로 표기한다. 예를 들어, *K₅*는 5개의 정점을 가지고 있으며, 각 정점이 다른 모든 정점과 연결된 완전 그래프를 의미한다.

• 특징:

  • 각 정점의 차수(degree, 연결된 변의 수)는 n - 1 이다.
  • 완전 그래프는 정규 그래프(regular graph)의 한 종류이다. (모든 정점의 차수가 동일)
  • 완전 그래프는 연결 그래프(connected graph)이다. (임의의 두 정점 사이에 경로가 존재)
  • 완전 그래프는 클리크(clique) 문제에서 중요한 역할을 한다. (최대 크기의 완전 부분 그래프를 찾는 문제)

• 응용 분야: 완전 그래프는 네트워크 설계, 클러스터링, 소셜 네트워크 분석 등 다양한 분야에서 활용될 수 있다. 예를 들어, 통신 네트워크에서 모든 장치가 서로 직접 통신할 수 있도록 설계하는 경우 완전 그래프의 개념이 적용될 수 있다.

• 예시:

  • K₁: 정점 1개만 있는 그래프 (자명한 경우)
  • K₂: 정점 2개와 변 1개로 이루어진 그래프
  • K₃: 정점 3개와 변 3개로 이루어진 그래프 (삼각형)
  • K₄: 정점 4개와 변 6개로 이루어진 그래프