완전 그래프

3. 성질

유한 완전 그래프 $K\_n$은 $n(n-1)/2$개의 변을 가지며, 모든 꼭짓점은 차수 $n-1$을 갖는 정규 그래프이다. 모든 완전 그래프는 그 자체로 클릭을 이룬다.^[4]

완전 그래프 $K(S)$의 여 그래프는 무변 그래프 $\backslash bar\; K(S)$이다.

완전 그래프의 각 변에 방향을 부여하면, 결과 유향 그래프는 토너먼트라고 한다.

$K\_n$은 $T\_i$가 $i$개의 정점을 갖도록 $n$개의 트리 $T\_i$로 분해될 수 있다.^[6] 링겔의 추측은 완전 그래프 $K\_\{2n+1\}$이 $n$개의 변을 가진 임의의 트리의 복사본으로 분해될 수 있는지 묻는다.^[7] 이것은 충분히 큰 $n$에 대해 참인 것으로 알려져 있다.^[8][9]

완전 그래프의 매칭 수는 전화 번호로 주어지며, $n$-정점 그래프에 대한 호소야 지수의 가장 큰 가능한 값을 제공한다.^[11] 완전 그래프 $K\_n$ ($n$이 짝수)의 완전 매칭 수는 이중 계승 $(n-1)!!$로 주어진다.^[12]

교차수는 $K\_\{27\}$까지 알려져 있으며, $K\_\{28\}$은 7233 또는 7234개의 교차점을 필요로 한다. 추가 값은 Rectilinear Crossing Number 프로젝트에서 수집된다.^[13]

3. 1. 기하학적 및 위상수학적 성질

4. 예시

꼭짓점을 1개 ~ 8개 가지는 완전 그래프는 다음과 같다.

1에서 12까지의 정점 n에 대한 완전 그래프는 가장자리 수와 함께 아래에 표시된다.

참조

_[1] 서적 Classes of Directed Graphs https://books.google[...] Springer International Publishing
_[2] 서적 Combinatorics: Ancient and Modern Oxford University Press
_[3] 웹인용 Mystic Rose https://nrich.maths.[...] nrich.maths.org 2012-01-23
_[4] 서적 A Logical Approach to Discrete Math https://books.google[...] Springer-Verlag
_[5] 서적 Mathematics All Around https://archive.org/[...] Addison Wesley
_[6] 간행물 Optimal packings of bounded degree trees http://pure-oai.bham[...] 2020-03-09
_[7] conference Theory of Graphs and its Applications 1963
_[8] 간행물 A proof of Ringel's Conjecture 2021
_[9] 웹사이트 Rainbow Proof Shows Graphs Have Uniform Parts https://www.quantama[...] 2020-02-20
_[10] 간행물 Cycles in graphs and derangements.
_[11] 간행물 Extremal problems for topological indices in combinatorial chemistry http://www.math.tugr[...] 2012-03-29
_[12] 간행물 A combinatorial survey of identities for the double factorial
_[13] 웹사이트 Rectilinear Crossing Number project http://www.ist.tugra[...]
_[14] Webarchive A Polyhedron Without Diagonals. http://www.diale.org[...] 2017-09-18
_[15] 서적 Time Travel and Other Mathematical Bewilderments https://archive.org/[...] W. H. Freeman and Company
_[16] 간행물 Linkless embeddings of graphs in 3-space
_[17] 간행물 Knots and Links in Spatial Graphs
_[18] 서적 A Logical Approach to Discrete Math Springer