Gráfico completo

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 arista única . Un digrafo 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). ^{[ 1 ]}

La teoría de grafos se suele fechar con el trabajo de Leonhard Euler de 1736 sobre los Siete Puentes de Königsberg . Sin embargo, los dibujos de grafos completos, con sus vértices situados en los puntos de un polígono regular , ya habían aparecido en el siglo XIII, en la obra de Ramon Llull . ^{[ 2 ]} A este tipo de dibujo se le conoce a veces como rosa mística . ^{[ 3 ]}

El grafo completo de n vértices se denota por K _n . Algunas fuentes afirman que la letra K en esta notación corresponde a la palabra alemana komplett , ^{[ 4 ]} pero el nombre alemán para un grafo 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 un grafo regular de grado n − 1. Todos los grafos completos son sus propias camarillas máximas . Son máximamente conexos ya que el único corte de vértice que desconecta el grafo es el conjunto completo de vértices. El grafo complemento de un grafo completo es un grafo vacío .

Si a cada una de las aristas de un grafo completo se le da una orientación , el grafo dirigido resultante se llama torneo .

K _n puede descomponerse en n árboles T _i tales que T _i tiene i vértices. ^{[ 6 ]} La conjetura de Ringel pregunta si el grafo completo K _{2 n +1} puede descomponerse 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

${\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 grafo de n vértices. ^{[ 11 ]} El número de emparejamientos perfectos del grafo completo K _n (con n par) viene dado por el doble factorial ( n − 1)!! . ^{[ 12 ]}

Se conocen los números de cruce hasta K _{27 , mientras que} K ₂₈ requiere 7233 o 7234 cruces. El proyecto Rectilinear Crossing Number recopila valores adicionales. ^{[ 13 ]} Los números de cruce rectilíneos 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, ... (secuencia A014540 en el OEIS ) .

Un grafo completo con n nodos es el grafo de aristas de un simplex _de ( n -1) dimensiones . Geométricamente, _K3 forma el conjunto de aristas de un _triángulo , K4 un tetraedro , etc. El poliedro de Császár , un poliedro no convexo con la topología de un toro , tiene como esqueleto el grafo completo K7 . ^{[ 15 ]} Todo politopo vecino en cuatro o más dimensiones también tiene un esqueleto completo.

K ₁ a K ₄ son todos grafos planares . Sin embargo, todo dibujo planar de un grafo completo con cinco o más vértices debe contener un cruce, y el grafo completo no planar K ₅ juega un papel clave en las caracterizaciones de los grafos planares: por el teorema de Kuratowski , un grafo es planar si y solo si no contiene ni K ₅ ni el grafo bipartito completo K _3,3 como una subdivisión, y por el teorema de Wagner el mismo resultado se cumple para los menores de grafos en lugar de subdivisiones. Como parte de la familia de Petersen , K ₆ juega un papel similar como uno de los menores prohibidos para la incrustación sin enlaces . ^{[ 16 ]} En otras palabras, y como Conway y Gordon ^{[ 17 ]} demostraron, toda incrustación de K ₆ en el espacio tridimensional está intrínsecamente enlazada, con al menos un par de triángulos enlazados. 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 .

Gráficos completos sobre${\displaystyle n}$vértices, para${\displaystyle n}$Los valores entre 1 y 12 se muestran a continuación junto con el número de aristas:

• Red totalmente conectada , en redes informáticas
• Grafo bipartito completo (o biclique ), un grafo bipartito especial donde cada vértice de un lado de la bipartición está conectado a cada vértice del otro lado.
• El simplex , que es idéntico a un grafo completo de${\displaystyle n+1}$vértices, donde${\displaystyle n}$es la dimensión del simplex.

• Weisstein, Eric W. "Grafo completo" . MathWorld .