Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Граф, в котором любые две вершины смежны.
Graph in which every two vertices are adjacent
В математической области теории графов, полный граф — это простой неориентированный граф, в котором каждая пара различных вершин соединена единственным ребром. Полный ориентированный граф — это ориентированный граф, в котором каждая пара различных вершин соединена парой уникальных рёбер (по одному в каждом направлении). Сама теория графов обычно относят к началу работ Леонарда Эйлера 1736 года о семи мостах Кёнигсберга. Однако изображения полных графов, с вершинами, расположенными на точках правильного многоугольника, уже появлялись в XIII веке в работах Рамона Луллия. Такой рисунок иногда называют мистической розой.
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). 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. Such a drawing is sometimes referred to as a mystic rose.
Геометрия и топология
Полный граф с n узлами представляет рёбра (n – 1)-симплекса. Геометрически он формирует набор рёбер треугольника, тетраэдра и т. д. Полиэдр Цсасара, невыпуклый полиэдр с топологией тора, имеет полный граф в качестве своего скелета. Каждый соседний политоп в четырёх или более измерениях также имеет полный скелет. Графы K₅ и K₃,₃ являются плоскими графами. Однако, любое плоское изображение полного графа с пятью или более вершинами должно содержать пересечение, и непланарный полный граф K₅ играет ключевую роль в характеристике планарных графов: по теореме Куратовского, граф является планарным тогда и только тогда, когда он не содержит ни K₅, ни полный двудольный граф K₃,₃ в качестве подграфа, полученного делением рёбер, а по теореме Вагнера тот же результат справедлив для миноров графа вместо деления рёбер. Как часть семейства Петерсена, K₅ играет аналогичную роль одного из запрещённых миноров для вложения без связей. Другими словами, как доказали Конвей и Гордон, любое вложение K₅ в трёхмерное пространство внутренне связано, с по крайней мере одной парой связанных треугольников. Конвей и Гордон также показали, что любое трёхмерное вложение K₅ содержит гамильтонов цикл, который вложен в пространство как нетривиальный узел.
A complete graph with n nodes represents the edges of an (n – 1) simplex. Geometrically forms the edge set of a triangle, a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph as its skeleton. Every neighborly polytope in four or more dimensions also has a complete skeleton. through 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 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 nor the complete bipartite graph 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, plays a similar role as one of the forbidden minors for linkless embedding. In other words, and as Conway and Gordon proved, every embedding of 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 contains a Hamiltonian cycle that is embedded in space as a nontrivial knot.