Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276026
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Cortes orientados e cortes impares em grafos
Author: Cohen, Jaime
Advisor: Lucchesi, Cláudio Leonardo, 1945-
Abstract: 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 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.
Subject: Teoria dos grafos
Análise combinatória
Language: Português
Editor: [s.n.]
Date Issue: 1995
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Cohen_Jaime_M.pdf1.93 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.