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 …exibir mais conteúdo…

Em uma abordagem com algoritmos, às vezes se usa a vizinhança fechada, denotada por N[ x ], que inclui o vértice no qual ela se baseia. Não há, é claro, maior dificuldade em se passar de uma noção à outra, basta notar que N[x] = N(x) {x}.
Fecho transitivo
Em um grafo, se existe a ligação (v,w), diremos que w é atingível a partir de v.
Então poderemos pensar em usar outra ligação para ir adiante: esta relação de atingibilidade é transitiva, pois se houver uma ligação ( w,x ) poderemos chegar a x e este será também atingível de v.
Mais ainda, poderemos procurar todos os vértices atingíveis em um grafo G não orientado a partir de v dado: este conjunto é chamado fecho transitivo de v em G. Ele é designado por R( v ).
Se estivermos em um grafo orientado, haverá dois desses fechos:
 o fecho transitivo direto, que procura ( iterativamente ) sucessores de vértices e é o conjunto de todos os vértices atingíveis a partir de v. Estes vértices são chamados os descendentes de v.
 o fecho transitivo inverso, que procura ( iterativamente ) antecessores de vértices e é o conjunto de todos os vértices a partir dos quais v é atingível.
Estes vértices são chamados os ascendentes de v.
Para um vértice v, designaremos esses fechos, por
( v ) e
( v ), respectivamente. É importante observar que um fecho transitivo sempre inclui o seu vértice origem, por coerência: ele é, naturalmente, atingível de si mesmo.
A figura a seguir mostra exemplos destes dois últimos