Loading AI tools
위키백과, 무료 백과사전
그래프 이론에서 완전 그래프(完全graph, 영어: complete graph)는 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프이다.
(단순) 그래프의 범주 위에, 그래프를 그 꼭짓점 집합으로 대응시키는 망각 함자 가 존재한다. 이 함자는 오른쪽 수반 함자를 갖는다.
이 경우, 집합 에 대하여, 를 위의 완전 그래프라고 한다.
구체적으로, 집합 위의 완전 그래프 는 다음과 같다.
즉, 완전 그래프는 주어진 꼭짓점들에 대하여 가능한 모든 변들을 갖는 그래프이다.
서로 크기가 같은 두 집합의 완전 그래프는 서로 동형이다. 집합의 크기가 기수 인 집합의 완전 그래프를 라고 한다.
유한 완전 그래프 은 개의 변을 가지며, 모든 꼭짓점은 차수 을 갖는 정규 그래프이다. 모든 완전 그래프는 그 자체로 클릭을 이룬다.
꼭짓점을 1개 ~ 8개 가지는 완전 그래프는 다음과 같다.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.