La calculadora del teorema de Turán da el número máximo de aristas que puede tener un grafo de n vértices sin clique de un tamaño dado, la estructura del grafo de Turán extremal, su densidad y el número de aristas que fuerza la clique.
Cómo se hace el cálculo
- Introduce el número de vértices n.
- Introduce el tamaño de clique que evitar, r + 1, de al menos 3.
- Lee el número máximo de aristas, las partes y la densidad.
Ejemplo
Un grafo de 20 vértices sin clique de 4 puede tener como máximo 133 aristas, es decir, el 70,00 % de las 190 aristas del grafo completo. El grafo de Turán tiene 3 partes: 2 de ellas tienen un vértice más que las más pequeñas, de 6. Con 134 aristas, una clique es inevitable.
Por qué es útil
La calculadora ayuda a estudiantes y profesores de matemática discreta, a informáticos y a analistas de redes que estudian problemas extremales de grafos, comprueban ejercicios sobre los teoremas de Mantel y de Turán, o estiman la densidad de una red antes de que deba contener un grupo unido. Es un recurso habitual en las asignaturas de teoría de grafos de los grados de Matemáticas e Informática.
Conviene saber
El tamaño de clique que evitar es r + 1, de modo que un grafo sin triángulos tiene r = 2 y aquí se introduce un valor de 3. La fórmula exige vértices repartidos en partes lo más iguales posible. El máximo solo lo alcanza el grafo de Turán, así que cualquier otro grafo con tantas aristas y sin clique es imposible. El resultado es el mayor número de aristas y no el número típico. Los grafos reales, incluso densos, suelen quedar muy por debajo de esta cota. Cuando el número de vértices no es múltiplo de r, las partes se diferencian en un vértice, y la calculadora trata ese caso con el resto de la división.
Herramientas relacionadas
La calculadora de números de Catalan cuenta otras estructuras combinatorias, la de combinaciones cuenta subconjuntos, la del binomio da los coeficientes y la de números poligonales enumera recuentos figurados vecinos.