La teoría de Grafos.

Basándonos en el video de de Adrián Paenza, la Teoría de Grafos nos permite estudiar interrelaciones entre elementos que interactúan unos con otros.

Un ejemplo muy antiguo con respecto a ella es el del “vendedor viajero”. En este se plantea el problema de encontrar una ruta que, empezando y terminando en la misma ciudad, recorra sólo una vez las ciudades restantes y que a la vez esta ruta sea la mínima posible.

Es decir que, dado un conjunto finito de ciudades, y costos de viaje entre todos los pares de ciudades, se debe encontrar la forma más barata de visitar todas las ciudades exactamente una vez, y volver al punto de partida.

Obviamente, los costos son simétricos en el sentido de que viajar desde la ciudad X a la ciudad Y tiene el mismo costo que viajar desde la ciudad Y a la ciudad X. La condición de visitar todas las ciudades implica que el problema se reduce a decidir en qué orden las ciudades van a ser visitadas.

Para poder encontrar la solución al problema se puede utilizar la Teoría de Grafos, observando las relaciones entre las ciudades y encontrar el camino más corto y barato, respetando las condiciones dadas.

El video que se deja a continuación explica de manera clara para qué me sirve o en qué me facilita esta teoría. Necesariamente el hecho de usar estos nodos me sirve para representar diversos tipos de interacciones.

Problema del Vendedor viajero

Un ejemplo más aplicado a la vida cotidiana puede ser el siguiente:

Salgo de compras desde mi casa y quiero ir al shopping, a la ferretería y al supermercado. La idea es trazar el recorrido más corto para caminar menos y hacerlo en menor tiempo. Para lograrlo tengo que tener en cuenta los siguientes datos:

1. ·         Mi casa – 9 cuadras al Shopping
2. ·         Mi casa – 8 cuadras a la ferretería.
3. ·         Mi casa – 7 al supermercado.
4. ·         Shopping – 15 a la ferretería.
5. ·         Shopping – 10 al supermercado.
6. ·         Ferretería – 4 al supermercado

Todos estos datos se pueden representar gráficamente utilizando la teoría en cuestión.

Para encontrar el camino más corto debo probar todas las posibles rutas.

La idea de este comentario es presentar una manera más simple una teoría que encierra conocimientos matemáticos más complejos. Obviamente que también la podemos aplicar para representar las interacciones de las personas que forman parte de una red social.