완전 그래프

위키백과 ― 우리 모두의 백과사전.

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

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

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