Grafos(livro)

Disponível somente no TrabalhosFeitos
  • Páginas : 125 (31076 palavras )
  • Download(s) : 0
  • Publicado : 1 de maio de 2012
Ler documento completo
Amostra do texto
1

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL ESCOLA DE ENGENHARIA PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA DE PRODUÇÃO

UM MODELO DE RESOLUÇÃO PARA O PROBLEMA DE ROTEIRIZAÇÃO EM ARCOS COM RESTRIÇÃO DE CAPACIDADE

Rafael Roco de Araújo

Porto Alegre, 2003

2

Rafael Roco de Araújo

UM MODELO DE RESOLUÇÃO PARA O PROBLEMA DE ROTEIRIZAÇÃO EM ARCOS COM RESTRIÇÃO DE CAPACIDADEDissertação submetida ao Programa de PósGraduação em Engenharia de Produção da Universidade Federal do Rio Grande do Sul como requisito parcial à obtenção do título de MESTRE EM ENGENHARIA EM ENGENHARIA DE PRODUÇÃO na área de concentração de Sistemas de Transportes e Logística.

Orientador: Prof.Luiz Afonso dos Santos Senna, Ph. D

Porto Alegre, 2003

3

Esta dissertação foi julgada adequada paraa obtenção do título de Mestre em Engenharia de Produção e aprovada em sua forma final pelo Orientador e pela Banca Examinadora designada pelo Programa de Pós-Graduação em Engenharia de Produção.

Prof. Luiz Afonso dos Santos Senna, Ph. D Universidade Federal do Rio Grande do Sul

Prof. José Luiz Duarte Ribeiro, Ph.D Coordenador PPGEP / UFRGS

Banca Examinadora:

Ana Maria Volkmer deAzambuja, Dr.
Prof. Depto. Matemática / FURG

Emílio Merino Dominguez, Dr.
Prof. PPGEP/UFRGS

Fernando Dutra Michel, M. Eng.
Prof. PPGEP/UFRGS

João Luiz Becker, Ph. D
Prof. PPGA/UFRGS

4

A meus pais, Arno e Vitória, e a memória de meu tio Rafael Rocco.

5

AGRADECIMENTOS Vários são aqueles que colaboraram de algum modo, seja de forma direta ou indireta, para o desenvolvimentodeste trabalho. Gostaria de registrar o meu sincero agradecimento ao Prof. Fernando Michel pelo permanente acompanhamento, pelo apoio e pela amizade, assim como ao meu orientador o Prof. Luiz Afonso dos Santos Senna. Agradeço também aos colegas Guilherme Schneider e Daniela Facchini pela valiosa participação que tiveram no desenvolvimento deste trabalho como bolsistas de iniciação científica. A todasas pessoas que atuam no Lastran, sejam elas professores, doutorandos, mestrandos, bolsistas e funcionários, agradeço pela amizade e constante incentivo. Agradeço ao suporte financeiro da FEENG durante este período e também ao PPGEP por toda a estrutura de apoio que nos foi disponibilizada. Aos meus familiares, em especial a meu pai, o agradecimento por todo apoio e encorajamento, decisivoprincipalmente para a superação dos momentos mais difíceis. Por fim, rendo graças a Deus, por todos os caminhos que pelas suas sábias mãos foram abertos neste importante período de minha vida, assim como pela sua constante benção e proteção.

6

LISTA DE FIGURAS Figura 1 Pontes de Königsberg e o multigrafo correspondente .................................................. 27 Figura 2 Representação deum multigrafo .................................................................................. 32 Figura 3 Grafo não orientado com ciclo de Euler associado ...................................................... 35 Figura 4 Grafo não euleriano valorado ....................................................................................... 39 Figura 5 Grafo completo formado a partir dos elementosde Vo e E’ ......................................... 39 Figura 6 Grafo aumentado .......................................................................................................... 40 Figura 7 Grafo fortemente conexo .............................................................................................. 41 Figura 8 Grafo orientado valorado.............................................................................................. 42 Figura 9 Grafo bipartido .............................................................................................................. 43 Figura 10 Grafo orientado aumentado ......................................................................................... 44 Figura 11 Grafo não orientado valorado com arestas requeridas formando uma...
tracking img