Complete Graph(완전 그래프)는 서로 다른 두개의 vertex가 반드시 하나의 edge로 연결된 그래프를 뜻한다.

예를 들어 vertex의 수가 8개인 complete graph는 다음과 같다.



n개의 vertex를 가지는 complete graph는 으로 나타낸다.

은 개의 edge를 가지는데,

이는 n개의 꼭지점 중 2개를 선택하는 조합문제에 해당한다.






vertex가 k개인 complete graph는 자연스럽게 k-1을 차수로 하는 regular graph가 된다.

  regular graph(정규 그래프)는 각 vertex가 동일한 수의 이웃을 가지는 그래프이다.

  즉, 각 vertex의 차수가 모두 같다는 것이다.



또 모든 complete graph는 그 자체로 clique이다.

  clique(클릭)이란 모든 두 꼭지점이 변으로 연결되어 있는 집합을 말한다.





참고자료

1. Complete Graph - 위키피디아





Posted by 하남각목