Gráfico completo

ImprimirCitar

Gráfico en el que cada dos vértices están adyacentes

En el campo matemático de la teoría de grafos, un grafo completo es un grafo simple no dirigido en el que cada par de vértices distintos está conectado por una única arista. Un dígrafo completo es un grafo dirigido en el que cada par de vértices distintos está conectado por un par de aristas únicas (una en cada dirección).

La teoría de grafos en sí suele fecharse a partir del trabajo de 1736 de Leonhard Euler sobre los siete puentes de Königsberg. Sin embargo, los dibujos de grafos completos, con sus vértices colocados sobre los puntos de un polígono regular, ya habían aparecido en el siglo XIII, en la obra de Ramon Llull. Este dibujo a veces se denomina rosa mística.

Propiedades

El gráfico completo en $n$ vértices se indica mediante $K n$ . Algunas fuentes afirman que la letra $K$ en esta notación representa la palabra alemana komplett, 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 Teoría de grafos.

$K n$ tiene $n (n - 1)/2$ aristas (un número triangular), y es un gráfico 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. El gráfico complementario de un gráfico completo es un gráfico vacío.

Si a los bordes de un gráfico completo se les asigna una orientación, el gráfico dirigido resultante se denomina torneo.

$K n$ se puede descomponer en $n$ árboles $T i$ tales que $T i$ tiene $i$ vértices. La conjetura de Ringel pregunta si el gráfico completo $K 2 n +1$ puede descomponerse en copias de cualquier árbol con bordes $n$ . Se sabe que esto es cierto para $n$ suficientemente grandes.

El número de todos los caminos distintos entre un par específico de vértices en $K n +2$ viene dado por

{displaystyle w_{n+2}=n!e_{n}=lfloor en!rfloor}

donde $e$ se refiere a la constante de Euler, y

{displaystyle e_{n}=sum _{k=0}^{n}{frac {1}{k!}}.}

El número de coincidencias de los gráficos completos viene dado por los números de teléfono

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736,... (secuencia) A000085 en el OEIS).

Estos números dan el mayor valor posible del índice de Hosoya para un gráfico de vértice $n$ . El número de coincidencias perfectas del gráfico completo $K n$ (con $n$ even) viene dado por el factorial doble $(n - 1)!!$ .

Se conocen los números de cruce hasta $K 27$ , con $K 28$ que requiere 7233 o 7234 cruces. El proyecto Número de cruce rectilíneo recopila valores adicionales. Los números de cruce rectilíneo para $K n$ son

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,... A014540 en el OEIS).

Geometría y topología

Modelo de poliedro Csaszar interactivo con vértices que representan nodos. En la imagen SVG, mueva el ratón para girarlo.

Un gráfico completo con $n$ nodos representa los bordes de un $(n - 1)$ -símplex. 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 la topología de un toro, tiene el grafo completo $K 7$ como su esqueleto. Cada politopo vecino en cuatro o más dimensiones también tiene un esqueleto completo.

$K 1$ hasta $K 4$ son todas gráficas planas. 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 solo si no contiene $K 5$ ni el grafo bipartito completo $K 3,3$ como subdivisión, y por el teorema de Wagner, el mismo resultado se cumple para gráficos menores en lugar de subdivisiones. Como parte de la familia Petersen, $K 6$ desempeña un papel similar como uno de los menores prohibidos para incrustaciones sin enlaces. En otras palabras, y como demostraron Conway y Gordon, cada incrustación de $K 6$ en el espacio tridimensional está intrínsecamente vinculada, con al menos un par de triángulos unidos. 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.