Tareas invo




Investigación a las Operaciones

Apuntes

01/12/2011





ARBOL DE PESO MÍNIMO

Un árbol es una gráfica convexa y sin ciclos y un árbol generador en una gráfica convexa es unárbol que incluye a todos los vértices de la gráfica.
G T1




T2 T3




Otro concepto del árbol de peso mínimo nos dice que cada arista tiene asignado un peso proporcional entre ellos,lo cual es un número representativo de algún objeto o distancia y se usa para asignar un peso total al árbol incluyendo la suma de todos los pesos de los aristas de dicho árbol.
Ejemplo:
Unacompañía de cable desea trazar cable a una nueva colonia, si se limita a trazar el cable por ciertos caminos, entonces se generara una gráfica que represente los puntos conectados por dichos caminos.Algunos de estos caminos serán más caros que otros por ser más largos, dichos caminos serán representados por las aristas de mayor peso.
ALGORITMO DE DIJKSTRA
Este algoritmo también es conocido como elalgoritmo de caminos mínimos y es utilizado para la determinación del camino más corto dado un vértice origen al resto de vértices en una gráfica con pesos en cada arista.
La idea de este algoritmoconsiste en ir explotando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, una vez obtenido el camino más corto desde el vértice origen, al resto devértices que componen las gráfica, el algoritmo se detiene.
El algoritmo no funciona en gráficas con aristas con costos negativos.
ALGORITMO KRUSKAL
Elegir una arista ei de tal forma que w(ei)sea lo más pequeño posible, una vez elegidos las aristas e1, e2, …., ei, hay que elegir el arista ei+1 de E-{e1, e2, …., ei} de tal manera que:
a) G[`{e1, e2, …., ei}] sea a cíclica
b) ω[ei+1] seatan pequeño como sea posible
Ejemplo:
Se desea construir una red ferroviaria que comunique a cierto número de pueblos. Sea Cij el costo de construir la vía directa entre los pueblos i y j....