El grafo Turán T ( n , r ) es un grafo multipartito completo formado al dividir un conjunto de n vértices en r subconjuntos, con tamaños lo más iguales posible, y conectando dos vértices por un borde si y solo si pertenecen a diferentes subconjuntos. El gráfico tendrá subconjuntos de tamaño , y subconjuntos de tamaño . Es decir, es un grafo de partita r completo
Gráfico de Turán | |
---|---|
Lleva el nombre de | Pál Turán |
Vértices | norte |
Bordes | ~ |
Radio | |
Diámetro | |
Circunferencia | |
Número cromático | r |
Notación | T ( n , r ) |
Tabla de gráficos y parámetros |
Cada vértice tiene un grado o . El número de aristas es
Es una gráfica regular si n es divisible por r .
Teorema de Turán
Los gráficos de Turán llevan el nombre de Pál Turán , quien los usó para probar el teorema de Turán , un resultado importante en la teoría de grafos extremos .
Por el principio de casillero, cada conjunto de vértices r + 1 en el gráfico de Turán incluye dos vértices en el mismo subconjunto de partición; por lo tanto, el gráfico de Turán no contiene un clique de tamaño r + 1. Según el teorema de Turán, el gráfico de Turán tiene el máximo número posible de aristas entre todos los gráficos libres de clique ( r + 1) con n vértices. Keevash y Sudakov (2003) muestran que el gráfico de Turán es también el único gráfico libre de clicas ( r + 1) de orden n en el que cada subconjunto de α n vértices abarca al menosaristas, si α está lo suficientemente cerca de 1. El teorema de Erdős-Stone amplía el teorema de Turán al delimitar el número de aristas en un gráfico que no tiene un gráfico de Turán fijo como subgrafo. A través de este teorema, se pueden probar límites similares en la teoría de grafos extremos para cualquier subgrafo excluido, dependiendo del número cromático del subgrafo.
Casos especiales
Varias elecciones del parámetro r en un gráfico de Turán conducen a gráficos notables que se han estudiado de forma independiente.
El gráfico de Turán T (2 n , n ) se puede formar eliminando una coincidencia perfecta de un gráfico completo K 2 n . Como mostró Roberts (1969) , este gráfico tiene una boxicidad exactamente n ; a veces se lo conoce como el gráfico de Roberts . Este gráfico es también el 1- esqueleto de un n -dimensional politopo de cruce ; por ejemplo, el gráfico T (6,3) = K 2,2,2 es el gráfico octaédrico , el gráfico del octaedro regular . Si n parejas van a una fiesta y cada uno le da la mano a cada uno excepto a su pareja, entonces este gráfico describe el conjunto de apretones de manos que se llevan a cabo; por esta razón también se le llama gráfico de cóctel .
El gráfico de Turán T ( n , 2) es un gráfico bipartito completo y, cuando n es par, un gráfico de Moore . Cuando r es un divisor de n , el gráfico de Turán es simétrico y fuertemente regular , aunque algunos autores consideran que los gráficos de Turán son un caso trivial de regularidad fuerte y, por lo tanto, los excluyen de la definición de un gráfico fuertemente regular.
El gráfico de Turán tiene 3 a 2 b camarillas máximas , donde 3 a + 2 b = n y b ≤ 2; cada camarilla máxima se forma eligiendo un vértice de cada subconjunto de partición. Este es el mayor número de camarillas máximas posibles entre todos los gráficos de n -vértices independientemente del número de aristas en el gráfico (Moon y Moser 1965); estas gráficas a veces se denominan gráficas Moon-Moser .
Otras propiedades
Cada gráfica de Turán es una cografía ; es decir, se puede formar a partir de vértices individuales mediante una secuencia de operaciones de unión y complemento disjuntas . Específicamente, dicha secuencia puede comenzar formando cada uno de los conjuntos independientes del gráfico de Turán como una unión disjunta de vértices aislados. Entonces, el gráfico general es el complemento de la unión disjunta de los complementos de estos conjuntos independientes.
Chao y Novacky (1982) muestran que los gráficos de Turán son cromáticamente únicos : ningún otro gráfico tiene los mismos polinomios cromáticos . Nikiforov (2005) utiliza gráficos de Turán para proporcionar un límite inferior para la suma de los k th autovalores de un gráfico y su complemento.
Falls, Powell y Snoeyink desarrollan un algoritmo eficiente para encontrar agrupaciones de grupos de genes ortólogos en los datos del genoma, mediante la representación de los datos como un gráfico y la búsqueda de grandes subgrafos de Turán.
Los gráficos de Turán también tienen algunas propiedades interesantes relacionadas con la teoría de grafos geométricos . Pór y Wood (2005) dan un límite inferior de Ω (( rn ) 3/4 ) en el volumen de cualquier incrustación de cuadrícula tridimensional del gráfico de Turán. Witsenhausen (1974) conjetura que la suma máxima de distancias al cuadrado, entre n puntos con diámetro unitario en R d , se obtiene para una configuración formada al incrustar un gráfico de Turán en los vértices de un símplex regular.
Un gráfico de n- vértice G es un subgráfico de un gráfico de Turán T ( n , r ) si y solo si G admite una coloración equitativa con r colores. La partición del gráfico de Turán en conjuntos independientes corresponde a la partición de G en clases de color. En particular, el gráfico de Turán es el único gráfico n- vértice máximo con una coloración equitativa de color r .
Referencias
- Chao, CY; Novacky, GA (1982). "En gráficos saturados al máximo". Matemáticas discretas . 41 (2): 139-143. doi : 10.1016 / 0012-365X (82) 90200-X .
- Falls, Craig; Powell, Bradford; Snoeyink, Jack. "Cálculo de COG de alta rigurosidad mediante gráficas tipo Turán" (PDF) . Cite journal requiere
|journal=
( ayuda ) - Keevash, Peter; Sudakov, Benny (2003). "Densidad local en gráficos con subgrafos prohibidos" (PDF) . Combinatoria, Probabilidad y Computación . 12 (2): 139-153. doi : 10.1017 / S0963548302005539 .
- Luna, JW; Moser, L. (1965). "Sobre camarillas en gráficos". Revista de Matemáticas de Israel . 3 : 23-28. doi : 10.1007 / BF02760024 . S2CID 9855414 .
- Nikiforov, Vladimir (2005). "Problemas de valores propios del tipo Nordhaus-Gaddum". arXiv : matemáticas.CO / 0506260 .
- Pór, Atila; Madera, David R. (2005). "No hay tres en línea en 3D". Proc. En t. Symp. Dibujo gráfico (GD 2004) . Notas de la conferencia en Ciencias de la Computación no. 3383, Springer-Verlag. págs. 395–402. doi : 10.1007 / b105810 . hdl : 11693/27422 .
- Roberts, FS (1969). Tutte, WT (ed.). "Sobre la boxicidad y cubicidad de un gráfico". Progreso reciente en combinatoria : 301–310.
- Turán, P. (1941). "Egy gráfelméleti szélsőértékfeladatról (Sobre un problema extremo en teoría de grafos)". Matematikai és Fizikai Lapok . 48 : 436–452.
- Witsenhausen, HS (1974). "Sobre el máximo de la suma de distancias al cuadrado bajo una restricción de diámetro". American Mathematical Monthly . 81 (10): 1100–1101. doi : 10.2307 / 2319046 . JSTOR 2319046 .
enlaces externos
- Weisstein, Eric W. "Gráfico de cóctel" . MathWorld .
- Weisstein, Eric W. "Gráfico octaédrico" . MathWorld .
- Weisstein, Eric W. "Turán Graph" . MathWorld .