완전 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''완전 그래프'''(完全graph, {{llang|en|complete graph}})는 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프이다.

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

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

서로 [[집합의 크기|크기]]가 같은 두 집합의 완전 그래프는 서로 [[동형]]이다. [[집합의 크기]]가 [[기수 (수학)|기수]] <math>\kappa</math>인 집합의 완전 그래프를 <math>K_\kappa</math>라고 한다.

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

완전 그래프 <math>K(S)</math>의 [[여 그래프]]는 [[무변 그래프]] <math>\bar K(S)</math>이다.

== 예 ==
[[꼭짓점]]을 1개 ~ 8개 가지는 완전 그래프는 다음과 같다.
<gallery>
파일:Complete graph K1.svg|<math>K_1</math>
파일:Complete graph K2.svg|<math>K_2</math>
파일:Complete graph K3.svg|<math>K_3</math>
파일:Complete graph K4.svg|<math>K_4</math>
파일:Complete graph K5.svg|<math>K_5</math>
파일:Complete graph K6.svg|<math>K_6</math>
파일:Complete graph K7.svg|<math>K_7</math>
파일:Complete graph K8.svg|<math>K_8</math>
</gallery>

== 외부 링크 ==
* {{매스월드|id=CompleteGraph|title=Complete graph}}

== 같이 보기 ==
* [[램지의 정리]]

{{전거 통제}}
{{토막글|조합론}}

[[분류:그래프]]
[[분류:정규 그래프]]