Gráfico completo

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

Gráfico completo
K 7 , una gráfica completa con 7 vértices
Vértices	norte
Bordes	${\displaystyle \textstyle {\frac {n(n-1)}{2}}}$
Radio	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}$
Diámetro	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}$
Circunferencia	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}$
Automorfismos	n ! ( S n )
Número cromático	norte
Índice cromático	n si n es impar n - 1 si n es par
Espectro	${\displaystyle \left\{{\begin{array}{lll}\emptyset &n=0\\\left\{0^{1}\right\}&n=1\\\left\{(n-1)^{1},-1^{n-1}\right\}&{\text{otherwise}}\end{array}}\right.}$
Propiedades	( n - 1) -regular Gráfico simétrico Vértice-transitivo Transitivo al borde Muy regular Integral
Notación	K n
Tabla de gráficos y parámetros

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 gráfico dirigido en el que cada par de vértices distintos está conectado por un par de bordes únicos (uno en cada dirección).

Por lo general, la teoría de grafos en sí comienza 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 colocados en los puntos de un polígono regular , aparecieron ya en el siglo XIII, en la obra de Ramon Llull . ^{[1] A} este dibujo se le llama a veces una rosa mística . ^[2]

Propiedades

El gráfico completo de vértices se denota por . Algunas fuentes afirman que la letra en esta notación representa la palabra alemana komplett , ^[3] pero el nombre alemán para un gráfico completo, vollständiger Graph , no contiene la letra , y otras fuentes afirman que la notación honra las contribuciones de Kazimierz Kuratowski a la teoría de grafos. ^[4]${\displaystyle n}$${\displaystyle K_{n}}$${\displaystyle K}$${\displaystyle K}$

${\displaystyle K_{n}}$tiene aristas (un número triangular ) y es una gráfica regular de grados . 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 de complemento de un gráfico completo es un gráfico vacío .${\displaystyle n(n-1)/2}$ ${\displaystyle n-1}$

Si cada uno de los bordes de un gráfico completo tiene una orientación , el gráfico dirigido resultante se denomina torneo .

${\displaystyle K_{n}}$se puede descomponer en árboles de modo que tenga vértices. ^[5] La conjetura de Ringel pregunta si el gráfico completo se puede descomponer en copias de cualquier árbol con bordes. ^[6] Se sabe que esto es cierto para lo suficientemente grande . ^{[7] [8]}${\displaystyle n}$${\displaystyle T_{i}}$${\displaystyle T_{i}}$${\displaystyle i}$${\displaystyle K_{2n+1}}$${\displaystyle n}$${\displaystyle n}$

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 la OEIS ).

Estos números dan el mayor valor posible del índice de Hosoya para un gráfico de vértice. ^[9] El número de emparejamientos perfectos del gráfico completo (con pares) viene dado por el factorial doble . ^[10]${\displaystyle n}$${\displaystyle K_{n}}$${\displaystyle n}$ ${\displaystyle (n-1)!!}$

Los números de cruces hasta son conocidos, y se requieren cruces 7233 o 7234. El proyecto Rectilinear Crossing Number recopila más valores. ^{[11] Los} números de cruce rectilíneo para son ${\displaystyle K_{27}}$${\displaystyle K_{28}}$${\displaystyle K_{n}}$

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 poliedro interactivo de Csaszar con vértices que representan nodos. En la imagen SVG , mueva el mouse para rotarla. ^[12]

Un gráfico completo con nodos representa los bordes de un - 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 gráfico completo K ₇ como su esqueleto . Cada politopo vecino en cuatro o más dimensiones también tiene un esqueleto completo.${\displaystyle n}$${\displaystyle (n-1)}$

K ₁ a K ₄ son todas gráficas planas . Sin embargo, todo dibujo plano de un grafo completo con cinco o más vértices debe contener un cruce, y el grafo completo no plano K ₅ juega un papel clave en las caracterizaciones de grafos planos: según el teorema de Kuratowski , un grafo es plano si y solo si no contiene ni K ₅ ni el gráfico bipartito completo K _3,3 como subdivisión, y según el teorema de Wagner, el mismo resultado es válido para los gráficos menores 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 . ^[13] En otras palabras, y como demostraron Conway y Gordon ^[14] , cada incrustación de K ₆ 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 ₇ contiene un ciclo hamiltoniano que está incrustado en el espacio como un nudo no trivial .

Ejemplos

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

K 1 : 0	Reyes 2 : 1	Reyes 3 : 3	Reyes 4 : 6
K 5 : 10	K 6 : 15	K 7 : 21	K 8 : 28
Reyes 9 : 36	K 10 : 45	K 11 : 55	K 12 : 66

Ver también

• Red completamente conectada , en red informática
• Gráfico bipartito completo (o biclique ), 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

Referencias

1. Knuth, Donald E. (2013), "Dos mil años de combinatoria" , en Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern , Oxford University Press, págs. 7-37, ISBN 978-0191630620.
2. Mystic Rose , nrich.maths.org , consultado el 23 de enero de 2012.
3. Gries, David ; Schneider, Fred B. (1993), A Logical Approach to Discrete Math , Springer-Verlag, pág. 436, ISBN 0387941150.
4. Pirnot, Thomas L. (2000), Matemáticas por todas partes , Addison Wesley, p. 154 , ISBN 9780201308150.
5. Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (5 de agosto de 2019). "Empaquetaduras óptimas de árboles de grados acotados" (PDF) . Revista de la Sociedad Matemática Europea . 21 (12): 3573–3647. doi : 10.4171 / JEMS / 909 . ISSN 1435-9855 . S2CID 119315954 .   
6. Ringel, G. (1963). Teoría de Gráficos y sus Aplicaciones . Actas del Simposio Smolenice.
7. Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (8 de enero de 2020). "Una prueba de la conjetura de Ringel". arXiv : 2001.02665 [ math.CO ].
8. Hartnett, Kevin. "Rainbow Proof muestra que los gráficos tienen partes uniformes" . Revista Quanta . Consultado el 20 de febrero de 2020 .
9. 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   .
10. Callan, David (2009), Una encuesta combinatoria de identidades para el factorial doble , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.
11. Oswin Aichholzer. "Proyecto Rectilinear Crossing Number" . Archivado desde el original el 30 de abril de 2007.
12. Ákos Császár, Un poliedro sin diagonales. Archivado el 18 de septiembre de 2017 en la Wayback Machine , Instituto Bolyai, Universidad de Szeged, 1949
13. Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993), "Inserciones sin enlaces de gráficos en 3 espacios", Boletín de la Sociedad Americana de Matemáticas , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , MR 1.164.063 , S2CID 1110662  .
14. Conway, JH ; Cameron Gordon (1983). "Nudos y vínculos en gráficos espaciales". J. Graph Th . 7 (4): 445–453. doi : 10.1002 / jgt.3190070410 .

Enlaces externos

Wikimedia Commons tiene medios relacionados con Gráficos completos .

Busque el gráfico completo en Wiktionary, el diccionario gratuito.

• Weisstein, Eric W. "Gráfico completo" . MathWorld .