Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
IMPLEMENTAÇÃO DE ALGORITMOS EM GRAFOS
NO PROGRAMA DE ENGENHARIA DE PRODUÇÃO DA COPPE/UFRJ
Paulo Jorge Magalhães Teixeira
Programa de Engenharia de Produção, COPPE/UFRJ, Centro de Tecnologia, Bloco F,
Cidade Universitária, Ilha do Fundão, Rio de Janeiro, Brasil.
[email protected]
Emília do Nascimento Mato
Programa de Engenharia de Produção, COPPE/UFRJ, Centro de Tecnologia, Bloco F,
Cidade Universitária, Ilha do Fundão, Rio de Janeiro, Brasil.
[email protected]
Valdir Agustinho de Melo
Instituto de Computação, Centro Tecnológico – UFF, Rua Passo da Pátria, 156 - Bloco E - 3° andar
São Domingos, Niterói, Rio de Janeiro, Brasil.
[email protected]
Denis Silveira da Silva
Programa de Engenharia de Produção, COPPE/UFRJ, Centro de Tecnologia, Bloco F,
Cidade Universitária, Ilha do Fundão, Rio de Janeiro, Brasil.
[email protected]
Paulo Oswaldo Boaventura Netto
Programa de Engenharia de Produção, COPPE/UFRJ, Centro de Tecnologia, Bloco F,
Cidade Universitária, Ilha do Fundão, Rio de Janeiro, Brasil.
[email protected]
Resumo: A construção de modelos, matemáticos ou não, pode ser feita de diferentes modos, bem
como envolver diferentes áreas do conhecimento humano. Esta prática tem sido desenvolvida nos
últimos 200 anos mas só recentemente se percebeu a grande importância que os problemas de
matemática discreta têm assumido na caracterização e solução de problemas reais e importantes da
vida moderna e, consequentemente, os modelos matemáticos a eles associados.
Dentro deste novo contexto, uma área particularmente rica de aplicações e adequada ao
desenvolvimento de modelos matemáticos é a Teoria dos Grafos, cuja abrangência de aplicações pode
ser encontrada em diferentes áreas do conhecimento humano.
O conhecimento e entendimento de muitos conceitos da Teoria dos Grafos frequentemente passa pelo
manuseio e implementação dos diferentes algoritmos que complementam e enriquecem a teoria. No
livro “Grafos: Teoria, Modelos, Algoritmos”, 3ª Edição, Editora Edgard Blücher Ltda., São Paulo,
2003, de Paulo Oswaldo Boaventura Netto, diversos algoritmos são apresentados em sua forma
descritiva e com exemplos de aplicação.
Neste trabalho serão apresentados vários desses algoritmos, que foram implementados em linguagem
Pascal e desenvolvidos com interesse didático. O que se pretende é permitir que os usuários tomem
conhecimento dos conceitos teóricos e de aplicações envolvidos em cada uma das implementações
efetuadas nos algoritmos sugeridos, bem como a sua aplicabilidade em diferentes exemplos (alguns
propostos e outros que podem ser sugeridos pelo usuário), com a utilização de um computador pessoal
que estará disponível para uso durante o período do evento.
A implementação dos algoritmos é feita de forma bem simples e clara, sem recursos sofisticados de
linguagem e tem o apoio de um sistema que permite ao usuário desenhar grafos, igualmente
desenvolvido no Programa. Este suporte computacional, de caráter essencialmente didático, estará
disponível, em breve, no endereço eletrônico http://www.po.ufrj.br da Área de Pesquisa Operacional
do Programa de Engenharia de Produção da COPPE/UFRJ.
Palavras-chave: Teoria dos grafos, Desenho de grafos, Algoritmos.
2481