Aplicaciones ("en la vida cotidiana") de la teoría de grafos

Question

EDITAR otra idea que me dio alguien fue considerar flujos en una red que no sólo dependieran del nodo al principio y al final de un vértice sino también sobre el propio vértice, como un flujo máximo para el vértice...

Actualmente estoy trabajando en un proyecto relacionado con la ciencia computacional y las matemáticas y estoy buscando aplicaciones concretas de la teoría de grafos.

Más concretamente quiero centrarme en la noción de defectos en un grafo, por ejemplo para empezar pensé en trabajar en cómo homogeneizar el valor de los nodos de un grafo para evitar grandes desfases entre dos de ellos - el ejemplo que tenía en mente era el de una red de distribución de energía ( cómo la gran diferencia de valores entre nodos fomenta los atajos...)

En primer lugar me interesan bastante los ejemplos que puedan conducir fácilmente a modelos sencillos, ya que probablemente acabaré teniendo que codificar en Python un poco :)

De ahí que mi pregunta sea: ¿conocen algún original ejemplos de aplicaciones de la teoría de grafos, que serían relativamente fáciles de crear y estudiar un modelo? Por original, quiero decir -¡si es posible! Sería realmente un plus- no los demasiado "obvios", usados y por tanto eruditos, como las redes de transporte, el movimiento de multitudes, la distribución de energía en una red eléctrica...

Muchas gracias por la atención y -espero- por la futura ayuda/apoyo. Si tienes algún consejo, no dudes en compartirlo :)

(+ edición: he rebajado el tono demasiado personalista de este post para que pueda reunir a todos los grafoteóricos)

Answer 1

Cualquier situación en la que se tenga un conjunto de tareas, algunas de las cuales deben completarse antes que otras (por ejemplo, debe cursar Francés I antes de cursar Francés II) puede modelarse como un grafo acíclico dirigido (el grafo debe ser acíclico porque no tiene sentido que haya dependencias mutuas). A continuación, se puede utilizar clasificación topológica para determinar un orden apropiado para completar estas tareas. Esto es trivial para las cosas sencillas, y lo hacemos en nuestra cabeza todo el tiempo (tengo que coger las llaves para arrancar mi coche, luego entrar en el coche para ir a la tienda de comestibles, y luego comprar comida para poder comer), pero puedes imaginar situaciones en las que las tareas se cuentan por miles o más. Si dirigieras una empresa de transporte y, por ejemplo, muchos camiones que salen tuvieran que esperar a que lleguen otros para poder transferir los paquetes de uno a otro.

Answer 2

Las redes aparecen cada vez con más frecuencia en la economía. Yo me inclinaría por la teoría de los juegos algorítmicos y las redes económicas. La formación de redes estratégicas, los juegos de enrutamiento, las subastas sobre gráficos y las redes sociales son todos ellos relevantes. Los juegos de enrutamiento utilizan muchos argumentos de funciones potenciales, por lo que alguien familiarizado con Electricidad y Magnetismo se sentiría cómodo. El autor de Networks, Crowds, and Markets también tiene un preprint que puede descargarse de su sitio web: http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book.pdf

La investigación operativa se ocupa mucho de la teoría de grafos. Muchos problemas de la teoría de grafos pueden formularse como programas lineales y enteros. Es una buena manera de estudiar las restricciones y entender el problema, así como de resolverlo utilizando relajaciones de LP de algún tipo (plano de corte, branch and bound, etc.).

La teoría de los gráficos también aparece mucho en Química. En particular, la teoría de grafos espectrales se utiliza mucho en química. No soy químico ni me siento lo suficientemente cómodo con la literatura como para decirte mucho más.

La coloración también es útil para el almacenamiento. Dos vértices son adyacentes si no pueden almacenarse juntos. Entonces se encuentra la coloración mínima del gráfico para determinar el número de unidades de almacenamiento diferentes que se necesitarán.