Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.