Английская Википедия:Complete graph
Шаблон:Short description Шаблон:Infobox graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction).[1]
Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull.[2] Such a drawing is sometimes referred to as a mystic rose.[3]
Properties
The complete graph on Шаблон:Mvar vertices is denoted by Шаблон:Mvar. Some sources claim that the letter Шаблон:Mvar in this notation stands for the German word Шаблон:Lang,[4] but the German name for a complete graph, Шаблон:Lang, does not contain the letter Шаблон:Mvar, and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory.[5]
Шаблон:Mvar has Шаблон:Math edges (a triangular number), and is a regular graph of degree Шаблон:Math. All complete graphs are their own maximal cliques. They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices. The complement graph of a complete graph is an empty graph.
If the edges of a complete graph are each given an orientation, the resulting directed graph is called a tournament.
Шаблон:Mvar can be decomposed into Шаблон:Mvar trees Шаблон:Mvar such that Шаблон:Mvar has Шаблон:Mvar vertices.[6] Ringel's conjecture asks if the complete graph Шаблон:Math can be decomposed into copies of any tree with Шаблон:Mvar edges.[7] This is known to be true for sufficiently large Шаблон:Mvar.[8][9]
The number of all distinct paths between a specific pair of vertices in Шаблон:Math is given[10] by
- <math> w_{n+2} = n! e_n = \lfloor en!\rfloor,</math>
where Шаблон:Mvar refers to Euler's constant, and
- <math>e_n = \sum_{k=0}^n\frac{1}{k!}.</math>
The number of matchings of the complete graphs are given by the telephone numbers
- 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... Шаблон:OEIS.
These numbers give the largest possible value of the Hosoya index for an Шаблон:Mvar-vertex graph.[11] The number of perfect matchings of the complete graph Шаблон:Mvar (with Шаблон:Mvar even) is given by the double factorial Шаблон:Math.[12]
The crossing numbers up to Шаблон:Math are known, with Шаблон:Math requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.[13] Rectilinear Crossing numbers for Шаблон:Mvar are
- 0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... Шаблон:OEIS.
Geometry and topology
A complete graph with Шаблон:Mvar nodes represents the edges of an Шаблон:Math-simplex. Geometrically Шаблон:Math forms the edge set of a triangle, Шаблон:Math a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph Шаблон:Math as its skeleton.[15] Every neighborly polytope in four or more dimensions also has a complete skeleton.
Шаблон:Math through Шаблон:Math are all planar graphs. However, every planar drawing of a complete graph with five or more vertices must contain a crossing, and the nonplanar complete graph Шаблон:Math plays a key role in the characterizations of planar graphs: by Kuratowski's theorem, a graph is planar if and only if it contains neither Шаблон:Math nor the complete bipartite graph Шаблон:Math as a subdivision, and by Wagner's theorem the same result holds for graph minors in place of subdivisions. As part of the Petersen family, Шаблон:Math plays a similar role as one of the forbidden minors for linkless embedding.[16] In other words, and as Conway and Gordon[17] proved, every embedding of Шаблон:Math into three-dimensional space is intrinsically linked, with at least one pair of linked triangles. Conway and Gordon also showed that any three-dimensional embedding of Шаблон:Math contains a Hamiltonian cycle that is embedded in space as a nontrivial knot.
Examples
Complete graphs on <math>n</math> vertices, for <math>n</math> between 1 and 12, are shown below along with the numbers of edges:
See also
- Fully connected network, in computer networking
- Complete bipartite graph (or biclique), a special bipartite graph where every vertex on one side of the bipartition is connected to every vertex on the other side
References
External links
Шаблон:Commons Шаблон:Wiktionary
- ↑ Шаблон:Citation; see p. 17
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite conference
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite web
- ↑ Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Cite web
- ↑ Ákos Császár, A Polyhedron Without Diagonals. Шаблон:Webarchive, Bolyai Institute, University of Szeged, 1949
- ↑ Шаблон:Citation
- ↑ Шаблон:Citation.
- ↑ Шаблон:Cite journal
