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(클릭)이란 모든 두 꼭지점이 변으로 연결되어 있는 집합을 말한다.
참고자료
'Mathematics' 카테고리의 다른 글
Complete Graph(완전 그래프)란 무엇인가 (0) | 2013.05.04 |
---|---|
술어논리 - '모든 사람은 때때로 어떤 사람을 좋아한다'와 그 부정 (0) | 2013.04.26 |
술어논리 - '모든 사람은 어떤 사람을 좋아한다'와 그 부정 (0) | 2013.04.26 |
칸토어의 집합론 - 자연수 vs 실수 (0) | 2013.04.26 |
칸토어의 집합론 - 자연수 vs 유리수 (0) | 2013.04.26 |
칸토어의 집합론 - 자연수 vs 정수 (1) | 2013.04.26 |
댓글을 달아 주세요