En el campo matemático de la teoría de grafos , un gráfico completo es un gráfico simple no dirigido en el que cada par de vértices distintos está conectado por una arista única . Un dígrafo completo es un gráfico dirigido en el que cada par de vértices distintos está conectado por un par de aristas únicas (una en cada dirección). [1]
La teoría de grafos en sí suele datarse en su inicio con el trabajo de Leonhard Euler de 1736 sobre los Siete Puentes de Königsberg . Sin embargo, los dibujos de gráficas completas, con sus vértices colocados sobre los puntos de un polígono regular , ya habían aparecido en el siglo XIII, en obra de Ramon Llull . [2] Este dibujo a veces se denomina rosa mística . [3]
El gráfico completo en n vértices se denota por K n . Algunas fuentes afirman que la letra K en esta notación representa la palabra alemana komplett , [4] pero el nombre alemán para un gráfico completo, vollständiger Graph , no contiene la letra K , y otras fuentes afirman que la notación honra las contribuciones de Kazimierz Kuratowski a la teoría de grafos. [5]
K n tiene n ( n – 1)/2 aristas (un número triangular ) y es una gráfica regular de grado n – 1 . Todos los gráficos completos son sus propias camarillas máximas . Están conectados al máximo ya que el único corte de vértice que desconecta el gráfico es el conjunto completo de vértices. La gráfica complementaria de una gráfica completa es una gráfica vacía .
Si a cada uno de los bordes de un gráfico completo se le da una orientación , el gráfico dirigido resultante se llama torneo .
K n se puede descomponer en n árboles T i tales que T i tiene i vértices. [6] La conjetura de Ringel pregunta si el gráfico completo K 2 n +1 se puede descomponer en copias de cualquier árbol con n aristas. [7] Se sabe que esto es cierto para n suficientemente grande . [8] [9]
El número de todos los caminos distintos entre un par específico de vértices en K n +2 viene dado [10] por
donde e se refiere a la constante de Euler , y
El número de coincidencias de las gráficas completas viene dado por los números de teléfono.
Estos números dan el valor más grande posible del índice de Hosoya para un gráfico de n vértices. [11] ¡ ¡El número de coincidencias perfectas del gráfico completo K n (con n par) viene dado por el factorial doble ( n – 1)!! . [12]
Se conocen los números de cruce hasta K 27 , y K 28 requiere cruces 7233 o 7234. El proyecto Rectilinear Crossing Number recopila más valores. [13] Los números de cruce rectilíneos para K n son
Un gráfico completo con n nodos representa las aristas de un ( n – 1) - simplex . Geométricamente K 3 forma el conjunto de aristas de un triángulo , K 4 un tetraedro , etc. El poliedro de Császár , un poliedro no convexo con topología de toro , tiene como esqueleto el grafo completo K 7 . [15] Cada politopo vecino en cuatro o más dimensiones también tiene un esqueleto completo.
K 1 a K 4 son todos gráficos planos . Sin embargo, cada dibujo plano de un gráfico completo con cinco o más vértices debe contener un cruce, y el gráfico completo no plano K 5 juega un papel clave en las caracterizaciones de los gráficos planos: según el teorema de Kuratowski , un gráfico es plano si y sólo si no contiene ni K 5 ni el gráfico bipartito completo K 3,3 como una subdivisión, y según el teorema de Wagner el mismo resultado es válido para gráficos menores en lugar de subdivisiones. Como parte de la familia Petersen , K 6 desempeña el mismo papel que uno de los menores prohibidos para la incrustación sin vínculos . [16] En otras palabras, y como demostraron Conway y Gordon [17] , cada incrustación de K 6 en un espacio tridimensional está intrínsecamente vinculada, con al menos un par de triángulos vinculados. Conway y Gordon también demostraron que cualquier incrustación tridimensional de K 7 contiene un ciclo hamiltoniano que está incrustado en el espacio como un nudo no trivial .
A continuación se muestran gráficos completos de vértices, entre 1 y 12, junto con el número de aristas:
