Grafos: Introduccion

Los grafos permiten modelar infinidad de sistemas del mundo real en los que diferentes elementos de un conjunto est´an relacionados entre sı: ciudades conectadas por carre- teras, proyectos divididos en tareas que dependen unas de otras, relaciones familiares en diagramas genealogicos, aeropuertos conectados por vuelos directos, etc. En muchos de estos sistemas surge la necesidad de resolver ciertos problemas que, en esencia, son instancias de problemas prototıpicos que podemos formular en el terreno abstracto de los grafos. Tiene inter´es, por tanto, encontrar algoritmos eficientes para la resoluci´on de estos problemas. Un par de ejemplos ayudar´a a entender el planteamiento: Consid´erese el problema de encontrar la ruta por carretera que nos permita ir de una ciudad a otra con un menor consumo de combustible, o el de calcular la ruta que debe seguir un repartidor de pizzas para llegar cuanto antes al domicilio del cliente. Ambos son casos particulares de un mismo problema prototıpico sobre grafos, el que conocemos como ((problema del camino mas corto)).

Dada la relaci´on ((ser amigo)) en un grupo de personas o dada la relacion ((es un pıxel vecino y del mismo color)) en una imagen, el ((problema del calculo de las componentes conexas)) de un grafo da solucion a los respectivos problemas concretos de hallar los grupos de amigos o las zonas de una imagen que presentan el mismo color. Resolver uno de los problemas prototıpicos resuelve infinidad de problemas concretos. Ante un problema concreto, la metodologıa de trabajo propuesta consiste en modelar el sistema real mediante un grafo y formular nuestro problema en termi- nos de equivalencia con un problema prototıpico sobre grafos,

encontrar un m´etodo resolutivo para el problema prototıpico sobre grafos (en muchos casos, disponible en la literatura),

aplicar el metodo al grafo e interpretar la solucion del problema prototıpico en terminos del problema original. Este cap´ıtulo y los dos siguientes se dedican a presentar algunos conceptos relacio- nados con grafos, cuestiones relativas a su implementacion y algunos de los algoritmos resolutivos para ciertos problemas fundamentales: el recorrido de los vertices de un grafo con diferentes criterios,

el ordenamiento topologico de los vertices de un grafo,

el calculo de las componentes conexas de un grafo,

el calculo de la clausura transitiva de un grafo,

Apuntes de Algorıtmica 151

7.1 Grafos dirigidos 2003/12/09-12:57

el calculo del arbol de recubrimiento mınimo de un grafo ponderado, la obtenci´on del camino mas corto entre dos vertices de un grafo ponderado, el calculo del camino mas corto entre un vertice y cualquier otro, esto es, del arbol de caminos mas cortos, el calculo de la

...