위키백과 ― 우리 모두의 백과사전.
그래프 이론에서 완전 그래프(complete graph)는 서로 다른 두개의 꼭지점이 반드시 하나의 변으로 연결된 그래프이다.
n개의 꼭지점을 가지는 완전 그래프는 Kn이라고 나타낸다. Kn은
개의 변을 가지는데, 이것은 n개의 꼭지점 중에서 시작점과 끝점에 해당하는 2개를 선택하는 경우의 수
에서 확인할 수 있다. Kn은 n-1의 차수를 가지는 정규 그래프이다. 모든 완전 그래프는 그 자체로 clique이다.
다음 그래프는 각각 꼭지점을 1개 ~ 8개 가지는 완전 그래프의 그림이다.