Grafo completo

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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í misma 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, aparecieron ya 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 denota por 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 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. La conjetura de Ringel pregunta si el grafo completo K _{2 n +1} se puede descomponer en copias de cualquier árbol con n aristas. Se sabe que esto es cierto para n suficientemente grande.

El número de todos los caminos distintos entre un par específico de vértices en K _{n +2} está dado por ${displaystyle w_{n+2}=n!e_{n}=lpiso en!rpiso,}$

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éfono1, 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 n vértices. ¡¡ El número de emparejamientos perfectos del gráfico completo K _n (con n par) viene dado por el factorial doble (n – 1)!!.

Se conocen los números de cruce hasta K ₂₇, y K ₂₈ 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 son0, 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,... (secuencia A014540 en el OEIS).

Geometría y topología

Un gráfico completo con n nodos representa las aristas de un (n – 1) -simplex. Geométricamente K ₃ forma el conjunto de aristas de un triángulo, K ₄ 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 ₇ como su esqueleto. Cada politopo vecino en cuatro o más dimensiones también tiene un esqueleto completo.

K ₁ a K ₄ 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 ₅ 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 ni K ₅ ni el grafo bipartito completo K _3,3 como una subdivisión, y según el teorema de Wagner, el mismo resultado se cumple para grafos menores en lugar de subdivisiones. Como parte de la familia Petersen, K ₆ juega 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 ₆ en el 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 ₇ contiene un ciclo hamiltoniano que está incrustado en el espacio como un nudo no trivial.