Gráfica completa

Gráfico en el que cada dos vértices son 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 arista única . 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). ^[1]

La teoría de grafos se suele fechar como algo que comenzó con el trabajo de Leonhard Euler de 1736 sobre Los siete puentes de Königsberg . Sin embargo, dibujos de grafos completos, con sus vértices colocados 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 a veces se lo denomina rosa mística . ^[3]

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 , ^[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 un grafo regular de grado n – 1 . Todos los grafos completos son sus propios cliques maximalistas . Están máximamente conectados ya que el único corte de vértice que desconecta el grafo es el conjunto completo de vértices. El grafo complementario de un grafo completo es un grafo vacío .

Si a cada uno de los bordes de un gráfico completo se le 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. ^[6] La conjetura de Ringel pregunta si el grafo 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} está 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 se da 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 la OEIS ).

Estos números dan el mayor valor posible del índice de Hosoya para un gráfico de n vértices. ^[11] El número de emparejamientos perfectos del gráfico completo K _n (con n par) está dado por el factorial doble ( n – 1)!! . ^[12]

Se conocen los números de cruce hasta K _{27 , y} K ₂₈ requiere 7233 o 7234 cruces. El proyecto Rectilinear Crossing Number recopila más valores. ^[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 la OEIS ).

Geometría y topología

Modelo poliédrico interactivo de Csaszar con vértices que representan nodos. En la imagen SVG, mueva el ratón para rotarla. ^[14]

Un grafo completo con n nodos representa las aristas de un ( n – 1) - símplex . 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 . ^[15] Cada politopo vecino en cuatro o más dimensiones también tiene un esqueleto completo.

K ₁ a K ₄ son todos grafos planares . Sin embargo, cada 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 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 subdivisión, y por el teorema de Wagner el mismo resultado es válido para los menores de grafos en lugar de las subdivisiones. Como parte de la familia Petersen , K ₆ juega un papel similar como uno de los menores prohibidos para la incrustación sin enlaces . ^[16] En otras palabras, y como demostraron Conway y Gordon ^[17] , cada 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 .

Ejemplos

A continuación se muestran gráficos completos de vértices entre 1 y 12, junto con el número de aristas: ${\displaystyle n}$ ${\displaystyle n}$

Véase también

• Red completamente conectada , en redes informáticas
• Gráfico bipartito completo (o biclicuo ), un gráfico bipartito especial donde cada vértice de un lado de la bipartición está conectado a cada vértice del otro lado.
• El símplex , que es idéntico a un gráfico completo de vértices, donde es la dimensión del símplex. ${\displaystyle n+1}$ ${\displaystyle n}$

Referencias

1. Bang-Jensen, Jørgen; Gutin, Gregory (2018), "Terminología básica, notación y resultados", en Bang-Jensen, Jørgen; Gutin, Gregory (eds.), Clases de grafos dirigidos , Springer Monographs in Mathematics, Springer International Publishing, págs. 1–34, doi :10.1007/978-3-319-71840-8_1; ver pág. 17
2. Knuth, Donald E. (2013), "Dos mil años de combinatoria", en Wilson, Robin; Watkins, John J. (eds.), Combinatoria: antigua y moderna , Oxford University Press, págs. 7–37, ISBN 978-0191630620.
3. Mystic Rose, nrich.maths.org , consultado el 23 de enero de 2012.
4. Gries, David ; Schneider, Fred B. (1993), Un enfoque lógico para las matemáticas discretas, Springer-Verlag, pág. 436, ISBN 0387941150.
5. Pirnot, Thomas L. (2000), Matemáticas por todos lados, Addison Wesley, pág. 154, ISBN 9780201308150.
6. Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (5 de agosto de 2019). "Empaquetamientos óptimos de árboles de grado acotados" (PDF) . Journal of the European Mathematical Society . 21 (12): 3573–3647. doi :10.4171/JEMS/909. ISSN  1435-9855. S2CID  119315954. Archivado (PDF) desde el original el 9 de marzo de 2020 . Consultado el 9 de marzo de 2020 .
7. Ringel, G. (1963). Teoría de grafos y sus aplicaciones . Actas del Simposio Smolenice.
8. Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2021). "Una prueba de la conjetura de Ringel". Análisis geométrico y funcional . 31 (3): 663–720. arXiv : 2001.02665 . doi : 10.1007/s00039-021-00576-2 .
9. Hartnett, Kevin. "La prueba del arco iris muestra que los gráficos tienen partes uniformes". Revista Quanta . Archivado desde el original el 20 de febrero de 2020. Consultado el 20 de febrero de 2020 .
10. Hassani, M. "Ciclos en gráficos y desajustes". Math. Gaz. 88, 123–126, 2004.
11. Tichy, Robert F.; Wagner, Stephan (2005), "Problemas extremos para índices topológicos en química combinatoria" (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, CiteSeerX 10.1.1.379.8693 , doi :10.1089/cmb.2005.12.1004, PMID  16201918, archivado (PDF) desde el original el 2017-09-21 , consultado el 2012-03-29 .
12. Callan, David (2009), Un estudio combinatorio de identidades para el factorial doble , arXiv : 0906.1317 , Bibcode :2009arXiv0906.1317C.
13. Oswin Aichholzer. "Proyecto de número de cruce rectilíneo". Archivado desde el original el 30 de abril de 2007.
14. Ákos Császár, un poliedro sin diagonales. Archivado el 18 de septiembre de 2017 en Wayback Machine , Instituto Bolyai, Universidad de Szeged, 1949
15. Gardner, Martin (1988), Viajes en el tiempo y otros desconciertos matemáticos, WH Freeman and Company, pág. 140, Bibcode :1988ttom.book.....G, ISBN 0-7167-1924-X
16. Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993), "Incorporaciones sin enlaces de gráficos en el espacio tridimensional", Boletín de la Sociedad Matemática Americana , 28 (1): 84–89, arXiv : math/9301216 , doi :10.1090/S0273-0979-1993-00335-5, MR  1164063, S2CID  1110662.
17. Conway, JH ; Cameron Gordon (1983). "Nudos y vínculos en gráficos espaciales". Revista de teoría de grafos . 7 (4): 445–453. doi :10.1002/jgt.3190070410.

Enlaces externos

• Weisstein, Eric W. "Gráfico completo". MundoMatemático .