2. O problema do fluxo máximo. |
a) Definición e representación gráfica. Problema dual: conxunto de corte de capacidade mínima.
b) Algoritmo de Ford-Fulkerson.
c) Aplicacións. |
4. O problema da árbore de mínimo custo. |
a) Descrición do problema. Algoritmos para calcular a árbore de mínimo custo: Prim, Kruskal, Boruvka.
b) Regras para dividir o custo da árbore de mínimo custo entre os nodos. Regras baseadas nos algoritmos de Prim e Kruskal. Regras baseadas en xogos cooperativos con utilidade transferible. |