En la teoría de gráficas extremas, estudias la función extrema [matemáticas] \ text {ex} (n, H) [/ matemáticas] que se define como el número máximo de aristas en una gráfica de nodos [matemáticas] n [/ matemáticas] que NO contiene un subgrafo isomorfo a [math] H [/ math].
Deje que [math] K_r [/ math] sea el gráfico completo en los nodos [math] r [/ math]. El teorema de Turan establece que el número máximo de aristas en un gráfico de nodo [matemático] n [/ matemático] que es [matemático] K_ {r + 1} [/ matemático] libre es
[matemáticas] \ text {ex} (n, K_ {r + 1}) \ aprox (1 – \ frac {1} {r}) \ binom {n} {2} [/ matemáticas]
- ¿Cómo puedo obtener una clase de matemáticas completa para tontos en la web?
- Matemática Aplicada: ¿Por qué la transformación de Laplace convierte la convolución en multiplicación?
- ¿Cuáles son algunas secuencias sin fórmulas generales conocidas?
- ¿Me pueden ayudar a resolver [matemáticas] e ^ x = 1-x [/ matemáticas]?
- ¿Qué es exactamente Z en Z-Transform? ¿Qué es el dominio Z?
que es el orden del gráfico de Turan [math] T_r (n) [/ math], un gráfico completo [math] r [/ math] -partite en [math] n [/ math] nodos distribuidos de la manera más uniforme posible.
El teorema de Erdos-Stone extiende el teorema de Turan a [matemáticas] H = K_ {r} (t) [/ matemáticas], el gráfico completo [matemáticas] r [/ matemáticas] con nodos [matemáticas] t [/ matemáticas] en cada clase. Observe que [math] K_ {r} (t) = T_ {r} (rt) [/ math]. Es el teorema fundamental de la teoría gráfica extrema.
El teorema de Erdos-Stone establece que el número máximo de aristas en un gráfico de nodo [matemático] n [/ matemático], para suficientemente grande [matemático] n [/ matemático], es decir [matemático] K_ {r + 1} (t ) [/ math] gratis es
[matemáticas] \ text {ex} (n, K_ {r + 1} (t)) \ aprox (1 – \ frac {1} {r} + \ epsilon) \ binom {n} {2} [/ matemáticas] .
De manera equivalente, puede decir que para [math] n [/ math] suficientemente grande (en función de [math] r [/ math] y [math] \ epsilon [/ math]) un gráfico [math] G [/ math ] con [math] n [/ math] nodos y al menos [math] e (G)> (1 – \ frac {1} {r} + \ epsilon) \ binom {n} {2} [/ math] bordes debe contener [math] K_ {r + 1} (t) [/ math] como un subgrafo.
