Descrição do algoritmo

O algoritmo implementado é uma adaptação do algoritmo de Sebo feita por de Mário Leston Rey [5].

Ele usa o conceito de potencial, uma função que associa valores inteiros aos vértices de um grafo e que satifaz certas propriedades.

Vamos introduzir alguns conceitos antes de definir este potencial. Estes conceitos foram retirados da referência [5].

Seja $G = (V, E)$ um grafo não orientado, $l: E \rightarrow \{-1, 1\}$ uma função que associa comprimentos às arestas de $G$ e uma função $h: V \rightarrow \mathbb{Z}$, que associa valores inteiros aos vértices de $G$.

Vamos denotar por $E^-$ o subconjunto $\{e \in E : l(e) = -1\}$, isto é, o conjunto das arestas de comprimentos negativos de $E$.

Para toda parte $L$ de $V$, uma alça de $L$ relativa a $h$ é uma aresta $xy$ com as seguintes propriedades:

• $x, y \in L$
• $h(x) = h(y) \geq h(z)$ para todo $z \in L$.

Denotaremos por $\Delta(L)$ o conjunto das alças de $L$.

Dado $i$ no conjunto dos valores de $h$, o nível $i$ do grafo é o conjunto $V^i = \{ v \in V : h(v) \leq i \}$. Uma fatia gorda de nível $i$ é o conjunto de vértices de um componente conexo de $G[V^i]$. Uma fatia magra de nível $i$ é o conjunto de vértices de um componente conexo de $G[V^i] - \Delta(V^i)$.

Dado um subconjunto $X \subseteq V$ de vértices de $G$, um corte $\nabla(X)$ é definido como $\nabla(X) = \{ xy \in E : x \in X, y \notin X \}$, isto é, o conjunto das arestas com exatamente uma extremidade em $X$.

Definidos os conceitos de alças, fatias magras e gordas e cortes, podemos definir um potencial. Para um vértice arbitrário $r \in V$, $h$ é um $l$-potencial relativo a $r$ se

(p0)

$h(r) = 0$;

(p1)

$\vert h(v) - h(u)\vert \leq 1$ para toda aresta $uv \in E$;

(p2)

para toda fatia magra $L$ determinada por $h$, $\Delta_h(L) \cap E^- = \emptyset$;

(p3)

Para toda fatia $L$ determinada por $h$:

(a)

$\nabla(L) \cap E^- = \emptyset$ se $r \in L$;

(b)

$\vert\nabla(L) \cap E^-\vert = 1$ se $r \notin L$,

Se $G$ não tem circuitos negativos, o valor associado a cada vértice $v$ pelo potencial definido acima é o comprimento mínimo de um caminho de $r$ a $v$ em $G$.

Em sua dissertação, Rey mostra que um grafo ou admite um potencial, ou possui circuitos negativos. Logo, o certificado da inexistência de circuitos negativos será um potencial.

O algoritmo usado para procurar circuitos negativos é guiado pela definição de potencial. Informalmente, ele repetidamente verifica se uma determinada função $h: V \rightarrow \mathbb{Z}$ é um potencial e procura corrigir cada violação das propriedades (p0) a (p3), alterando $h$, até encontrar um circuito negativo ou um $h$ que seja de fato um potencial.