|
|
|
|
|
 |
|
|
|
Teorema de Turán
En la teoría de grafos , el teorema de Turán es un resultado en el número de aristas en un K r 1 - libre gráfico . Un n - vértice gráfico que no contiene ( r + 1)-vértice camarilla puede ser formado por la partición del conjunto de vértices en r partes de tamaño igual o casi igual, y que conecta dos vértices de una ventaja cada vez que pertenecen a dos diferentes partes. Llamamos a la gráfica resultante del Turán gráfico T ( n , r ). El teorema de Turán estados que el gráfico de Turán tiene el mayor número de aristas entre todos los K r un sin n -vértices gráficos. Gráficos Turán se describió por primera vez y estudiado por los húngaros matemático Pablo Turán en 1941, aunque un caso especial del teorema se indicó anteriormente por Mantel en 1907. Declaración formal Formalmente, el teorema de Turán puede formularse como sigue. Vamos a G ser cualquier subgrafo de K n tal que G es K r una libre. A continuación, el número de aristas en G es mayor Una formulación equivalente es la siguiente: Entre los n gráficos simples, sin vértice ( r + 1)-camarillas, T ( n , r ) tiene el número máximo de aristas. Prueba Vamos a G ser un n -grafo simple vértice sin ( r + 1)-camarilla y con el máximo número de aristas. Resumen: La prueba consta de dos afirmaciones sobre la G , los cuales se explican, antes de probar. La primera afirmación es que G debe ser un completo r-partito gráfico (aunque es declarado técnicamente más abajo). En otras palabras, podemos dividir el conjunto de vértices en r subconjuntos tal que si dos vértices están en diferentes conjuntos, S i y S j , entonces tienen una arista entre ellos, pero si están en el mismo, entonces no tienen arista entre ellos. La segunda afirmación es que el tamaño de estos conjuntos S i se diferencian entre sí por más de 1. Por ejemplo, si queremos que el gráfico de 23 vértices con la mayoría de los bordes que no contiene un triángulo, entonces la partición de los vértices en conjuntos S 1 y S 2 , con | S 1 | = 12 y | S 2 | = 11 . Añadimos todas las aristas entre los dos conjuntos, por lo que el gráfico tendrá 11 * 12 = 132 bordes. Esto coincide con el teorema que dice que G tendrá en la mayoría de los bordes. Reivindicación 1: Gráfico G no contiene tres vértices u , v , w tal que G contiene borde u v , pero no contiene ni bordes u w ni v w . (Esta afirmación es equivalente a la relación x ~ y si y sólo si x no está conectada a ser y una relación de equivalencia. ~ Siempre es reflexiva y simétrica, pero sólo en casos especiales es transitivo. ~ No es transitiva, precisamente cuando tenemos u , v y w con u ~ w y w ~ v sin u ~ v ). Supongamos que la afirmación es falsa. Construir una nueva n -vértices sencillo gráfico G ' que no contiene ( r + 1)-camarilla, pero tiene más aristas de G , de la siguiente manera: Caso 1: d ( w ) < d ( u ) o d ( w ) < d ( v ). Supongamos que d ( w ) < d ( u ) . Eliminar vértice w , y crear una copia de vértice u (con todos los vecinos mismos u ); llamamos u ' . Cualquier camarilla en el nuevo gráfico contiene más de un vértice entre { u , u '} . Por lo que este nuevo gráfico no contiene ( r + 1) camarilla. Sin embargo, contiene más aristas: | E ( G ) | = | E ( G ) | - d ( w ) + d ( u )> | E ( G ) |. Caso 2: y Eliminar vértices u y v y crear dos nuevas copias del vértice w . Una vez más, el nuevo gráfico no contiene ( r + 1)-camarilla. Sin embargo, contiene más aristas: . Esto demuestra la reivindicación 1. La afirmación demuestra que es posible partición de los vértices de G en clases de equivalencia en función de su nonneighbors, es decir, dos vértices están en la misma clase de equivalencia si están adyacentes. Esto implica que G es un grafo completo multipartita (donde las partes son las clases de equivalencia). Reivindicación 2: El número de aristas en un completo k -partito gráfico se maximiza cuando el tamaño de las partes es diferente al menos por una. Si G es un completo k -partito gráfico con las partes A y B y | A |> | B | + 1 , entonces podemos aumentar el número de aristas en G moviendo un vértice de la parte A de la Parte B. Al mover un vértice de la parte A de la Parte B , el gráfico pierde | B | bordes, pero las ganancias | A | - 1 aristas. Por lo tanto, las ganancias por lo menos borde. Esto demuestra dos reclamación. Esta prueba muestra que el gráfico de Turan tiene el número máximo de aristas. Además, la prueba muestra que el gráfico de Turan es el único gráfico que tiene el número máximo de aristas. Teorema de Mantel Como un caso especial del teorema de Turán, para r = 2, se obtiene el teorema de Mantel : El número máximo de aristas en un n -vértice del triángulo sin gráfica es En otras palabras, hay que eliminar casi la mitad de los bordes de K n para obtener una gráfica sin triángulos. Una forma reforzada de teorema de Mantel que cualquier gráfica con al menos n 2 / 4 bordes debe ser el gráfico bipartito completo K n / 2, n / 2 o bien debe ser pancyclic : no sólo contiene un triángulo, sino que también debe contienen ciclos de todas las longitudes posibles otros hasta el número de vértices en la gráfica ( Bondy 1971 ). Otro refuerzo de teorema de Mantel que los bordes de los gráficos puede ser cubierto en la mayoría de las camarillas , es decir, el número de intersección es mayor ( Erdős, Goodman y Posa 1966 ).
 |
|
|
| |
|
|
|
|
|
|
|
|
|
|
