T-junções, T-cortes e funções conservativas - Rey, Mario Leston (1999)
O problema da determinação de uma T-junção mínima e os desdobramentos desse problema constituem o assunto central desta dissertação. Determinar uma T-junção mínima é equivalente a decidir se um grafo com pesos mais ou menos 1 nas arestas é livre de circuitos negativos. Exploramos o problema sob esta ótica e apresentamos o Teorema de Sebö-Lucchesi que caracteriza grafos livre de circuitos negativos. Apresentamos, também, o algoritmo de Sebö que determina caminhos de peso mínimo em grafos sem circuitos negativos. Algoritmos que determinam uma T-junção mínima produzem também uma coleção 2-disjunta máxima de T-cortes. Já a determinação de uma coleção 1-disjunta máxima é um problema difícil. Discutimos o algoritmo de Korach e Pennque extrai de uma coleção 2-disjunta máxima de T-cortes uma coleção 1-disjunta 'grande'. O estudo de T-junções mínimas leva naturalmente à consideração de conjuntos máximos de arestas negativas que não induzem circuitos negativos. Apresentamos uma relação minimax, devida a Frank, entre tais conjuntos de arestas e decomposições do grafo em orelhas