2. El problema del flujo máximo. |
a) Definición y representación gráfica. Problema dual: conjunto de corte de capacidad mínima.
b) Algoritmo de Ford-Fulkerson.
c) Aplicaciones. |
4. El problema del árbol de mínimo coste. |
a) Descripción del problema. Algoritmos para calcular el árbol de mínimo coste: Prim, Kruskal, Boruvka.
b) Reglas para dividir el coste del árbol de mínimo coste entre los nodos. Reglas basadas en los algoritmos de Prim y Kruskal. Reglas basadas en juegos cooperativos con utilidad transferible. |