T-junções, T-cortes e funções conservativas

Orientador:  Paulo Feofiloff

Palavras-chave:  teoria dos grafos, algoritmos em grafos, T-junções,
problema do carteiro chinês, circuitos negativos, emparelhamentos.

A dissertação trata dos seguintes problemas em grafos não-orientados cada uma de cujas arestas tem um comprimento (positivo, negativo ou nulo):

1. Problema do circuito negativo:  Encontrar um circuito de comprimento negativo.
2. Problema da distância: Encontrar um caminho de comprimento mínimo entre dois vértices dados.
3. Problema da T-junção mínima:  Dado um conjunto T de vértices, encontrar uma T-junção (= T-join) de comprimento mínimo.
4. Problema do carteiro chinês:  Encontrar uma trilha de comprimento mínimo que passe por todas as arestas e volte ao vértice de partida.

A dissertação se restringe ao caso em que o comprimento de cada aresta vale +1 ou –1.  Esse caso é suficiente para encontrar uma T-junção com número mínimo de arestas.

Contexto

Se todas as arestas tivessem comprimento não-negativo, o célebre algoritmo de Dijkstra resolveria o problema 2.  Em geral, entretanto, o problema é NP-difícil.  (Basta observar que o problema de encontrar um caminho de comprimento máximo entre dois vértices dados é um caso particular do problema 2.)

Sebö e Lucchesi descobriram independentemente um algoritmo eficiente para o problema 1.  O par de problemas 1+2 pode ser resolvido "conjuntamente" no seguinte sentido: existe um algoritmo polinomial que recebe um grafo e um vértice r e devolve

1. um circuito de comprimento negativo ou
2. para cada vértices v, um caminho de comprimento mínimo de r a v.

(Se o grafo fosse orientado, o célebre algoritmo de Ford-Bellman resolveria o par de problemas 1+2 no sentido A+B.)

Os problemas 1 a 4 estão intimamente relacionados. Em particular, um algoritmo eficiente para o problema 1 leva facilmente a uma solução do problema 3.  Por outro lado, o problema 4 é um caso particular do problema 3.

Definições básicas

• Uma trilha em um grafo é uma seqüência  (v0, e1, v1, e2, . . . , ek, vk)  em que cada ej é uma aresta com pontas vj-1 e vj  e as arestas são distintas duas a duas.
• Um caminho é uma trilha sem vértices repetidos.
• Um circuito é uma trilha  (v0, e1, v1, e2, . . . , ek, vk)  em que vk = v0, os demais vértices são distintos dois a dois,  e  k ≥ 3.
• Para qualquer conjunto T de vértices, uma T-junção (= T-join) é qualquer conjunto de arestas que incide um número ímpar de vezes em cada vértices de T e um número par de vezes em cada um dos demais vértices.

  Exemplos: Todo circuito é uma Ø-junção (embora a recíproca não seja verdadeira).  Todo caminho de u a v é uma {u,v}-junção (embora a recíproca não seja verdadeira).

Algumas referências

• L Lovász, M.D. Plummer, Matching Theory, North-Holland, 1986.
• P. D. Seymour, "On odd cuts and plane multicommodity flows", Proceedings of the London Mathematical Society, 42, 1981, pp.178-192.
• A. Sebö, "Finding the T-join structure of graphs", Mathematical Programming, 36 1986, pp.123-134.
• P. Feofiloff, C.L. Lucchesi, Algoritmos Para Igualdades Minimax em Grafos, VI Escola de Computação, Campinas, 1988.
• A. Sebö, "Undirected distances and the postman structure of graphs", Journal of Combinatorial Theory, Series B, 49 1990, pp.10-39.
• A. Sebö, "Potentials in undirected graphs ans planar multiflows", SIAM Journal on Computing, 26, 1997, pp.582-603.
• R. Sedgewick, Algorithms in C, 3rd. ed., part 5: Graph Algorithms, Addison-Wesley, 2002.