완전 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

그래프 이론에서 완전 그래프(完全graph, 영어: complete graph)는 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프이다.

정의[편집]

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

K\colon\operatorname{Set}\to\operatorname{Graph}
V\dashv K

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

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

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

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

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

성질[편집]

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

완전 그래프 K(S)여 그래프무변 그래프 \bar K(S)이다.

[편집]

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

바깥 고리[편집]