Algoritmo de Malgrange

PR

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ

Ministério da Educação
Universidade Tecnológica Federal do Paraná
Pró-Reitoria de Pesquisa e Pós-Graduação

Relatório Final de Atividades

Algoritmo de Malgrange vinculado ao projeto
Teoria dos Grafos

Cristiano Gonçalves de Araujo
Voluntário
Engenharia Ambiental
Data de ingresso no programa: 06/2013
Prof(ª). Msc. Fausto Pinheiro Silva

Área do Conhecimento:
1.03.03.01-4 Linguagens de Programação

CAMPUS Medianeira, 2014

CRISTIANO GONÇALVES DE ARAUJO
FAUSTO PINHEIRO SILVA

ALGORITMO DE MALGRANGE

Relatório Pesquisa do Programa de
Iniciação Científica ou Programa de
Iniciação Tecnológica da Universidade
Tecnológica Federal do Paraná.

MEDIANEIRA, 2014

SUMÁRIO

INTRODUÇÃO

4

MATERIAIS E MÉTODOS

4

RESULTADOS E DISCUSSÕES

8

CONCLUSÕES

10

REFERÊNCIAS

10

INTRODUÇÃO
Uma das grandes necessidades atualmente é determinar algoritmos eficientes para encontrar rotas em grafos orientados. O algoritmo de Malgrange determina as componentes f-conexas de um grafo orientado. Conseqüentemente, se dois vértices a, b pertencem a uma mesma componente f-conexa então existem um caminho de a para b e um caminho de b para a.
A modelagem de um problema de minimizar e determinar rotas de entrega se torna mais fácil em um grafo f-conexo ou a região de entrega é uma componente f-conexa. Se um grafo que modela este problema não for f-conexo, haverá rua onde o entregador quando entrar nela não poderá sair. A determinação das componentes f-conexas de um grafo orientado é uma etapa muito importante no estudo de muitos modelos de grafos, visto que ela permite que se façam estudos locais mais detalhados. Para facilitar o determinação da componentes f-conexas vamos implementar o algoritmo de Malgrange.

Fundamentação Teórica
Como representar um grafo
Existem muitas formas de se organizar os dados sobre de grafo, de modo que eles possam ser introduzidos em um