Teorema de Turán (Grafos)

Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 563
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Teorema de Turán (Grafos)

Mensaje sin leer por Nacho »

Para poder entender el teorema de Turán tenemos que primero conocer el concepto de grafo:
Grafo: Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Cliqué: es el grafo completo, es decir, un grafo en donde se unieron todos los vertices entre sí. Sea [math] la cantidad de vértices, se representa como [math].

Ahora que sabemos esto, el teorema de Turán dice:

Sea [math] un grafo de [math] vértices tal que no contiene un subconjunto de [math] vértices todos unidos entre si. Entonces, el máximo número de aristas de [math] es [math].

Un problema que sale con esto es el problema 1 del selectivo de ibero de 2004:

1. En un torneo de ajedrez en el que participan [math] jugadores al cabo de la primera semana se observa que ningún jugador ha enfrentado más de una vez al mismo oponente y que es imposible formar un grupo de [math] jugadores de modo tal que cada integrante haya enfrentado a los otros [math]. Determinar el máximo número de partidos que se pueden haber jugado hasta el momento en que se hicieron las observaciones.

Solución:

Si consideramos al grafo en el cual se representan a los vértices como los jugadores y los aristas como los partidos jugados, vemos que está contenido en [math]. Además por el enunciado, no puede haber un cliqué de [math]. Por lo tanto, el máximo número de aristas del grafo (es decir el máximo número de partidos jugados) es [math].
EDIT: ahora hay un dibujo del grafo.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
"Though my eyes could see I still was a blind man"
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Turán

Mensaje sin leer por Ivan »

Poné algún dibujo con el ejemplo de como queda el grafo :D
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 563
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Re: Turán

Mensaje sin leer por Nacho »

Dejo otro problema que sale:

Sean [math] siete puntos de una circunferencia. Se unen algunos de ellos entre sí mediante segmentos. ¿Cuál es el número mínimo de segmentos que deben trazarse si se desea qeu cada vez que se tomen [math] puntos de los [math] haya por lo menos [math] unidos por un segmento?
"Though my eyes could see I still was a blind man"
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Turán

Mensaje sin leer por Ivan »

Lo dejo enunciado de forma mas simple sin decir grafo :p

Turán: Dado un grupo de [math] personas sea [math] el número de pares de personas que se conocen entre sí.
Si no hay [math] personas tales que se conocen entre todos entonces
[math]

El ejemplo cuando hay igualdad (si el número no es entero miramos la parte entera) es formando [math] grupos de personas, lo mas parejos posibles. Dos personas se conocen si y solo si están en grupos distintos.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Responder