Universidade de São Paulo
Instituto de Matemática e Estatística

Projeto



Implementação de um algoritmo para encontrar circuitos negativos em grafos não-orientados



Maurício Rapchan Andretta

$\parbox{.55\textwidth}{{\sl Dissertação realizada sob a orientação d... ... requisitos para a obtenção do grau de Bacharel em Ciência da Computação.} \/ }$

São Paulo, dezembro de 2.003.

Resumo

O problema abordado nesta dissertação é determinar se um dado grafo com arestas de comprimento $1$ ou $-1$ possui circuitos negativos.

Para grafos orientados, o problema possui uma solução bem conhecida e muito simples, baseada no algoritmo de Bellman-Ford.

Para grafos não-orientados também há uma solução conhecida, que usa o algoritmo do emparelhamento máximo de Edmonds.

Um algoritmo mais direto para esse mesmo problema foi desenvolvido por András Sebo [6] e, independentemente, por Cláudio L. Lucchesi [1]. Ele usa o conceito de potenciais, funções que associam valores aos vértices do grafo e que satisfazem certas propriedades. Sebo definiu propriedades para um potencial de modo que um grafo não-orientado admite um tal potencial se e somente se não possui circuitos negativos.

Neste trabalho veremos uma implementação do algoritmo de Sebo adaptado por Mário Leston Rey [5]. Abstract

The problem considered in this dissertation is to determine if a given graph with edges that have lengths equals to $1$ or $-1$ has negative circuits.

For directed graphs, the problem has a well known and simple solution, based on the Bellman-Ford algorithm.

For undirected graphs there is a well known solution, that uses the Edmonds maximum matching algorithm.

Another, more direct, algorithm for the same problem was designed by András Sebo [6] and, independently, by Cláudio L. Lucchesi [1]. It uses the concept of a potential -- a function that associates values to vertices of the graph and has certain properties. Sebo defines the concept of potential in such way that an undirected graph admits a potential if and only if it has no negative circuits.

In this paper we will describe an implementation of Sebo's algorithm as adapted by Mário Leston Rey [5].