La teoría de grafos es extensamente utilizada como herramienta fundamental en la arquitectura de los buscadores de internet y en la construcción y estudio de redes sociales. ¿Querés saber qué postula?

La Teoría de Grafos, que empezó a estudiarse recientemente, tiene diversas aplicaciones en problemas de comunicación y optimización, y es una herramienta fundamental tanto en la arquitectura de los buscadores de Internet -por ejemplo, Google- como en la construcción y el estudio de redes sociales.

En el siguiente clip de video del programa Alterados por Pi, Adrián Paenza nos habla de algunas de estas aplicaciones:

Un grafo es un dibujo constituido por puntos -vértices- y arcos que los conectan -aristas-. Estos objetos modelan una gran cantidad de situaciones. Por ejemplo, si consideramos el conjunto de todas las personas como vértices y conectamos dos de ellas si se conocen, o tienen el mismo color de pelo, o la misma ascendencia, etc., obtendremos grafos que nos permitirán entender visualmente las relaciones que queremos observar.

Con esta guía de actividades aprenderemos algunos resultados clásicos de la teoría de grafos que nos ayudarán a resolver determinados problemas

Actividad 1: vértices y aristas

En esta actividad vamos a ver una importante relación entre los vértices y las aristas: se denomina grado de un vértice al número de aristas adyacentes a él. Si es necesaria alguna otra definición para realizar esta u otra de las actividades, se puede consultar un glosario de términos de teoría de grafos.

Consignas

1. onstruyan tres grafos que satisfagan las siguientes condiciones.
   • que tenga 7 vértices y 9 aristas y sea conexo (por definiciones, ver glosario).
   • que tenga 4 vértices y 13 aristas.
   • que tenga 6 vértices, sea completo y simple (por definiciones, ver glosario).
2. Calculen en cada uno de los ejemplos los grados de cada vértice y sumarlos.
3. Comparen los resultados de las sumas con los otros alumnos, y observar que son iguales aunque los grafos de los que provienen no los sean.
4. Comparen estas sumas con el número de aristas de cada grafo. ¿Qué conclusiones sacan?

Actividad de cierre

Generalicen lo que observaron, es decir, intenten demostrar que la suma de los grados de todos los vértices de un grafo es el doble de  la cantidad de aristas.

Actividad 2: grafos eulerianos

En esta actividad vamos a entender algunas propiedades de los grafos eulerianos. Un grafo es euleriano si admite un recorrido euleriano: un recorrido de un solo trazo que comienza y termina en un vértice del grafo, y que pasa una sola vez por cada una de sus aristas.

Consignas

1. Respondan cuáles de los grafos que aparecen dibujados arriba son eulerianos y cuáles no.
2. Hagan un recorrido euleriano de cada uno de los grafos que lo es.
3. Muestren, para cada uno de los grafos eulerianos, un vértice del que no puedan empezar un recorrido euleriano.
4. Calculá el grado de los vértices en los que no empezaron ni terminaron los recorridos eulerianos ¿Cómo son?
5. Intenten una explicación que permita entender por qué los grafos no eulerianos del comienzo en realidad no lo eran.

Actividad de cierre

Discutan la actividad y consideren de sacar la siguiente conclusión: los grafos eulerianos pueden tener a lo sumo dos vértices con grado impar en los que los recorridos eulerianos deben terminar o comenzar, aunque este hecho no garantiza que un grafo sea euleriano. Utilicen el pizarrón para dibujar los grafos.

Actividad 3: grafos y redes sociales

Esta actividad está relacionada con entender cómo funcionan los grafos como modelos de redes sociales. Tomaremos como vértices a cada uno de los alumnos de la clase y como aristas algunas propiedades que pueden tener en común entre ellos. Para empezar, cada alumno anotará en un papel con su nombre los siguientes datos:

• Mes de su cumpleaños.
• Banda o cantante favorito.
• Equipo de fútbol con el que simpatiza.
• Género (femenino o masculino)

Se procederá luego, con estos datos, a confeccionar un grafo en el pizarrón de la siguiente manera:

• Inicialicen cada vértice con algo que identifique a cada uno de los alumnos.
• Usen un color de tiza para cada propiedad de las anteriores. Por ejemplo dibujen una arista blanca ente dos de los vértices si cumplen años el mismo mes, una amarilla si son simpatizantes del mismo equipo, una verde si admiran al mismo cantante y una roja si son ambos del mismo sexo.
• Sigan así hasta completar todas las coincidencias para terminar el grafo.

Actividad de cierre

Observen el grafo para identificar afinidades y coincidencias entre todos los alumnos del curso. ¿Se corresponden de cierta manera algunas de estas aristas y/o el número de coincidencias con la intimidad que tienen entre sí los alumnos del curso?

Encuentro Descargas

• Capítulo 6: Grafos, un modelo para conectarse

Autor: Sebastián Freyre