Otimizacao em Redes e Nao Linear - Folha de Exercicios 2

Departamento de Matemática da Universidade de Aveiro Optimização em Redes e Não Linear Ano Lectivo 20052006 2º semestre Folha 2 Optimização em Redes 1 Árvore de Suporte 1 Suponha que uma dada companhia aérea tem 200 voos semanais os quais estabelecem ligações entre 35 cidades em alguns casos indirectamente isto é com várias escalas e que durante um período de crise resolveu manter em funcionamento o menor número de voos que possibilitasse a ligação entre as 35 cidadesse necessário com eventual mudança de avião em certos pontos do percurso Considerando que um voo liga duas cidades quantos voos ficaram em funcionamento 2 Considere o grafo GVE a Construa uma árvore de suporte ou abrangente de G b Supondo que a distribuição dos pesos das arestas do grafo G é a seguinte e110e22e33e45e53e63e77e82e95 encontre a árvore abrangente ou de suporte mínima 3 Seja GVE o grafo a Indique duas árvores de suporte ou abrangentes distintas neste grafo b Supondo que os custos de cada aresta são c122c133c144c151c233c246c25c261c34c353c453c462c574 encontre a árvore abrangente mínima usando o algoritmo de Kruskal e o algoritmo de Prim 4 Como modificaria ambos os algoritmos de construção da árvore abrangente mínima de modo a poder construir a árvore abrangente máxima Aplique os algoritmos modificados ao grafo do exercício anterior