Trabalho prog

INSTITUTO MILITAR DE ENGENHARIA PÓS-GRADUAÇÃO EM ENGENHARIA DE TRANSPORTES

Algoritmos para Resolução de Problemas em Redes

Prof.ª Vânia Barcellos G. Campos

Índice
1- Definição e Conceitos Básicos sobre Grafos 1.1 Conceitos Básicos 1.2 Características Estruturais 2- Conceituação de Redes 3- Minimização de Redes 3.1 Algoritmo de Kruskal 3.2 Algoritmo de Prim 4- Algoritmos de Caminho Mínimo 4.1 Algoritmo de Dijkstra 4.2 Algoritmo de Ford, Bellman e Moore 4.3 Caminho mais Confiável 4.4 Algoritmo de Floyd 4.5 Algoritmo de Dantzig 4.6Algoritmo de K-caminhos mínimos 4.7Desempenho dos Algoritmos 5- Algoritmos de Fluxo Máximo 5.1 Conceitos Básicos 5.2 Algoritmo de Aumento de Fluxo 5.3 Algoritmo de Ford /Fulkerson 5.4 Algoritmo de Dinic 5.5 Algoritmo DMKM 5.6 Modificações na Estrutura da Rede 5.7 Análise dos Algoritmos 6- Algoritmos de Custo Mínimo 6.1 Algoritmo Busacker e Gowen 6.2 Análise dos Algoritmos de custo Mínimo 7 - Roteirização Bibliografia Lista de Exercícios

pag 1 1 2 2 4 4 6 6 7 9 11 12 13 13 14 15 15 17 19 20 21 22 23 24 24 26 27 28 29

1

1- Definição e Conceitos Básicos sobre Grafos
Um grafo G = (X,A) é uma estrutura composta por um conjunto X de elementos chamados vértices ou nós e um conjunto A de pares de vértices, chamados arcos ou arestas. A representação gráfica de um grafo é feita por pontos (vértices) e linhas (arestas) unindo estes pontos. Quanto as características de seus arcos, um grafo pode ser : a) Orientado e não orientado São orientados quando seus arcos possuem uma orientação definida , ou seja , um nó do arco é definido como origem do mesmo e o outro como destino. E, não orientado, quando não existe esta noção de direção. b) Valorado e não valorado Um grafo é valorado, quando existem valores atribuídos a cada um dos seus arcos. Exemplo disto ocorre quando se está representando uma rede viária e se atribui a cada arco os valores correspondentes às distância entre interseções ( vértices). c) Planar e não-planar Um grafo