Diferencia entre revisiones de «Grafo de Turán»
Contenido eliminado Contenido añadido
m Correcciones ortográficas con Replacer (herramienta en línea de revisión de errores) |
m Correcciones ortográficas con Replacer (herramienta en línea de revisión de errores) |
||
Línea 13:
|notación = <math>T(n,r)</math>
}}
El '''grafo de Turán''' <math>T(n,r)</math> es un [[Grafo multipartito|grafo multipartito completo]] formado por el posicionamiento de un conjunto de <math>n</math> vértices dentro de <math>r</math> subconjuntos, con tamaños lo más iguales posibles, y conectando dos vértices por una esquina sí y
:<math>K_{\lceil n/r\rceil, \lceil n/r\rceil, \ldots, \lfloor n/r\rfloor, \lfloor n/r\rfloor}.</math>
Cada vértice tiene grados o de <math>n-\lceil n/r\rceil</math> o de <math>n-\lfloor n/r\rfloor</math>. El número de esquinas es
Línea 45:
Los grafos de Turán también tienen propiedades interesantes relacionadas con la teoría de grafos geométricos. Pór y Wood en 2005 dieron un límite menor de <math>\Omega ((rn)^{3/4})</math> en el volumen de cualquier rejilla tridimensional del grafo de Turán.<ref>{{cita conferencia|nombre=Attila|apellido=Pór|nombre2=David R.|apellido2=Wood|año=2005|título=No-three-in-line-in-3D|títulolibro=Proc. Int. Symp. Graph Drawing (GD 2004)|editorial=[[Springer Science+Business Media|Springer]]|publicación=[[Lecture Notes in Computer Science]]|volumen=3383|páginas=395–402|doi=10.1007/b105810}}</ref> Witsenhausen en 1974 conjetura que la suma máxima de distancias al cuadrado, entre <math>n</math> puntos con diámetro unitario en <math>R^d</math> es alcanzado por una configuración formada al incrustar un grafo de Turán en los vértices de un [[símplex]] regular.<ref>{{cita publicación|apellidos=Witsenhausen|nombre=H. S.|título=On the maximum of the sum of squared distances under a diameter constraint|año=1974|publicación=[[American Mathematical Monthly]]|páginas=1100–1101|volumen=81|doi=10.2307/2319046|número=10|editorial=[[American Mathematical Society]]|issn=0002-9890|jstor=2319046|idioma=inglés}}</ref>
Un grafo <math>G</math> de <math>n</math>-vértices es el [[Anexo:Glosario de teoría de grafos#Subgrafo|subgrafo]] de un grafo de Turán <math>T(n,r)</math> sí y
== Referencias ==
| |||