Saltar al contenido
Omnikalc

Calculadora del teorema de Turán

Introduce el número de vértices y el tamaño de clique que evitar para obtener el número máximo de aristas del grafo de Turán, el tamaño de sus partes, la densidad de aristas y el número de aristas que fuerza una clique.

Actualizado el
Tus datos

Valor fuera de rango

Valor fuera de rango

Resultados

Número máximo de aristas sin la clique

133

Aristas que fuerzan una clique

134

Aristas del grafo completo
190
Parte de todas las aristas posibles
70,00 %
Número de partes (r)
3
Partes del mayor tamaño
2
Tamaño de las partes más pequeñas
6

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.

Preguntas frecuentes

¿Qué dice el teorema de Turán?

El teorema de Turán da el número máximo de aristas de un grafo de n vértices que no contiene ningún subgrafo completo de r + 1 vértices. El grafo extremal es el grafo r-partito completo cuyas partes son lo más iguales posible, llamado grafo de Turán. Para r = 2, sin triángulos, la respuesta es el teorema de Mantel: como máximo n² / 4 aristas.

¿Cuál es la fórmula?

Si n = q × r + s con 0 ≤ s < r, el grafo de Turán tiene s partes de tamaño q + 1 y r − s partes de tamaño q. Su número de aristas es (1 − 1/r) × n² / 2 − s × (r − s) / (2r). Si r divide a n, se reduce a (1 − 1/r) × n² / 2.

¿Qué dice sobre forzar una clique?

Todo grafo con más aristas que el número de Turán debe contener una clique de r + 1 vértices. Para 20 vértices, un grafo de 133 aristas o más debe contener una clique de 4. Es el punto de partida de la teoría extremal de grafos, que pregunta cuántas aristas fuerzan una estructura dada.

¿Dónde se usa?

Aparece en combinatoria extremal, diseño de redes, teoría de códigos y análisis de grafos densos. Una red social con más conexiones que la cota de Turán debe contener un grupo de amistades unidas de un tamaño dado, lo que permite demostrar la existencia de cliques sin encontrarlas.

¿Te ha resultado útil esta calculadora?

¡Gracias por tu opinión!

Resultados orientativos con fines informativos. No sustituyen el consejo de un profesional.