'edge'에 해당되는 글 1건

  1. 2013.05.04 Complete Graph(완전 그래프)란 무엇인가

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 하남각목