Los árboles son unas estructuras especialmente adaptadas a los problemas de optimización.
Árbol abarcador de menor peso. Vamos a considerar de nuevo el problema de la red de conducción, pero ahora añadiremos un ingrediente nuevo. El estudio previo de ingeniería nos informa de qué tramos es posible construir pero, además, disponemos de la información sobre el coste de cada uno de esos tramos. Queremos, claro, elegir una red que conecte todas las ciudades con el menor coste posible. La información de los costes se traduce en que cada arista lleva asociado un número. Lo que buscamos es un árbol abarcador del grafo, pero justo aquel (o aquellos) para el que la suma de los costes de las aristas elegidas sea mínimo.
Para modelar esta situación, necesitamos una generalización del concepto de grafo. Un grafo con pesos (o grafo ponderado) será un grafo G en el que, además, cada arista a tenga asociado lo que llamaremos su peso, p(a), un número real no negativo . La matriz de vecindades de un grafo con pesos será simétrica, con ceros en la diagonal, y sus entradas serán los pesos de las aristas (o 0 si no hay tales aristas).
No hay comentarios.:
Publicar un comentario