Queridos Estudiantes:
Me complace enormemente acompañarles en uno de los temas centrales en computación: la Teoría de Grafos.
Este apasionante tema nos ocupará la segunda mitad del curso. Sus aplicaciones son inmensas, y van desde problemas de redes y telecomunicaciones
hasta transporte, circuitos eléctricos, biología, epidemiología, problemas de asignación de recursos y organización de proyectos, optimización, entre muchos otros.
Les aliento a que vayan más allá de los puntos tratados en clase. En particular, la historia de la Teoría cromática de Grafos es una valiosa evidencia de
la conexión entre Matemática y Computación. El Teorema de Kirchhoff (o de Matrices y Árboles) es una piedra angular en la Teoría Algebraica de Grafos,
y además permitió a Kirchhoff trascender en el tiempo, brindando la resolución de circuitos eléctricos (este gran científico ha dejado tanto más de legado a la ciencia). El problema del vendedor ambulante o "Traveling Salesman Problem" nos deja en ridículo a la humanidad, pues pese a su sencillez de planteo aún no conocemos una manera eficiente para resolverlo. La conjetura de Hoffman y Singleton es un intento de caracterizar a todos los grafos regulares de diámetro 2.
Los autores mostraron que la regularidad puede ser de 2, 3, 7 y 57. Sin embargo, la evidencia del grafo de regularidad 57 es un problema abierto...
En este mundo de Teoría de Grafos hay muchos problemas que esperan una respuesta.
Quizás ya tienen potencial para resolverlos, y es momento de conocer los problemas.
Les invito entonces a que busquen información tomando en cuenta las siguientes palabras clave: "Moore Graph", "Traveling Salesman Problem",
"Four Color Conjecture", "Hoffman Singleton Conjecture", "Matrix-Tree Theorem", "Ford-Fulkerson Algorithm".
Cordiales saludos,
Pablo.