완전 그래프

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

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

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

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