Orientador: Claudio L. Lucchesi

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

Resumo: Esta dissertação tem como objetivo apresentar igualdades minimax em grafos que envolvem cortes orientados; cortes ímpares e suas coberturas.
A primeira metade da dissertação trata das igualdades que relacionam famílias disjuntas máximas de cortes com as coberturas mínimas dos cortes do...

Resumo: Esta dissertação tem como objetivo apresentar igualdades minimax em grafos que envolvem cortes orientados; cortes ímpares e suas coberturas.
A primeira metade da dissertação trata das igualdades que relacionam famílias disjuntas máximas de cortes com as coberturas mínimas dos cortes do grafo. Na segunda parte, os papéis destes problemas são inveI:tidos, isto é, as igualdades relacionam cortes mínimos com famílias disjuntas máximas de coberturas dos cortes.
Mostramos ao longo do trabalho que em muitos casos é possível estabelecer analogias entre resultados para cortes orientados e para cortes ímpares. Estas analogias apresentam-se de duas maneiras: através de enunciados semelhantes e através de demonstrações semelhantes.
Entre os teoremas apresentados na primeria parte do trabalho, destacam-se os Teoremas de ~ucchesi- Younger e de Edmonds-Giles para cortes orientados e os de Lovász e de Seymour para cortes ímpares. Também são apresentados teoremas que tratam de circuitos orientados e ímpares em grafos planares, mostrando que a analogia também se estende para outros tipos de problemas.
Na segunda parte estabelecemos relações entre a igualdade minimax dual ao Teorema de Lovász com a generalização de uma famosa conjectura de Fulkerson. . Provamos um caso particular desta igualdade. Apresentamos também um resultado para um caso particular da igualdade dual ao Teorema de Lucchesi- Younger que foi provado por Schrijver e independentemente por Feofiloff e Younger.

Abstract: The goal of this dissertation is to unify some results of Graph Theory related to directed
cuts, odd cuts and their coverings.
In the first half of this work we show equalities that relate maximum disjoint families of cuts with the minimum coverings of the cuts of the graph. In the second...

Abstract: The goal of this dissertation is to unify some results of Graph Theory related to directed
cuts, odd cuts and their coverings.
In the first half of this work we show equalities that relate maximum disjoint families of cuts with the minimum coverings of the cuts of the graph. In the second half, we present the duals of those equalities, i. e., they relate minimum cuts with disjoint families of coverings.
Qur main purpose. is to provi de examples that show analogies between results on directed cuts and odd cuts. The analogies are of two types: in the statements of the results and in their proofs.
Among the results presented in the first half, the most important are Lucchesi- Younger and
Edmonds-Giles' theorems on directed cuts and Lovász and Seymour's theorems for odd cuts.
In the last part of this work we extend a result by Seymour that relates the dual of Lovász's theorem with a generalizatión of a famous conjecture due to Fulkerson. We prove a particular case of that equality. We also show an equality for a particular case of the dual of LucchesiYounger's theorem which had been proved by Schrijver and independent1y by Fe,ofiloff and Younger.