Aplicaciones de la teoria de grafos

...

Un grafo ponderado es un grafo en el que se han asignado a cada arista un número, llamado coste o peso. El peso de cada arista puede indicar la distancia, el tiempo empleado en recorrerla, coste económico, etc. La solución a nuestro problema viene dada por el llamado algoritmo de Krustal. Por tanto dicho algoritmo es un método para encontrar un árbol generador de peso mínimo en un grafo conexo ponderado de n- vértices.

Veamos cuales son los pasos de este algoritmo. 1º Ordenamos las aristas en orden creciente de peso. 2º Elegimos una arista a1 de peso mínimo. 3º Formamos una sucesión de aristas a2,....,an-1 eligiendo en cada iteración la de menor peso posible (no elegida anteriormente) de forma que no forme un circuito con las seleccionadas previamente. 4º Terminamos cuando tengamos n-1 aristas así elegidas. El árbol generador requerido es el grafo A de aristas a1,.....,an-1 y los vértices de G Pongamos el ejemplo de la construcción de una red ferroviaria. Supongo que tengo 4 ciudades A,B,C,D y las distancias entre ellas son: Utilizando el algoritmo de Krustal para encontrar el árbol que utiliza la menor cantidad de vía obtenemos: Una importante aplicación de los grafos, y que nada tiene que ver con lo visto hasta ahora es su utilización como modelos estructurales de la ciencia. En particular, es muy frecuente su utilidad en la química. Y es que es difícil encontrar algo en la ciencia que se asemeje tanto a un grafo como la fórmula estructural de un compuesto químico. Los vértices representan a los átomos de la molécula y los lados a los enlaces químicos que conectan ciertas parejas de átomos.

Conclusión

La programación de actividades es un caso típico de aplicación de la teoría de grafos, aunque presenta ciertas peculiaridades, tales como que los arcos, que representan las actividades, están limitados por sus vértices extremos, acontecimientos, pero tienen un tiempo propio de inicio, además de su duración. Así, un cambio en una actividad afectará a otras dependiendo no sólo de sus relaciones topológicas (conexiones entre vértices), sino de sus tiempos de comienzo. Se presenta un conjunto de herramientas matemáticas para la planificación y programación de proyectos mediante grafos, que hacen uso de un esquema compacto y eficiente para almacenar y manejar la información, que se organiza en listas de adyacencia, almacenadas en matrices unidimensionales sin punteros. Todas ellas se basan en la generación y búsqueda en profundidad de un árbol (Depth-firstsearch), cuyo esquema genérico se ha descrito detalladamente, así como las condiciones específicas de cada uno de los procesos concretos