Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/9599
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorLee, Orlando-
dc.contributor.authorFreitas, Lucas Ismaily Bezerra-
dc.date.accessioned2014-10-30T18:28:27Z-
dc.date.available2014-10-30T18:28:27Z-
dc.date.issued2014-
dc.identifier.citationFREITAS, L. I. B. A conjectura de Tuza sobre triângulos em grafos. 2014. 83 f. Dissertação (Mestrado Ciência da Computação) - Instituto de Computação, Universidade Estadual de Campinas, Campinas, 2014.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/9599-
dc.description.abstractIn this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza’s conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K5 minor.pt_BR
dc.language.isopt_BRpt_BR
dc.subjectTeoria dos Grafospt_BR
dc.subjectEmpacotamento e cobertura combinatóriapt_BR
dc.subjectConjectura de Tuzapt_BR
dc.titleA conjectura de Tuza sobre triângulos em grafospt_BR
dc.typeDissertaçãopt_BR
dc.description.abstract-ptbrNeste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação¸ nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contraexemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K5.pt_BR
dc.title.enThe conjecture of Tuza about triangles in graphspt_BR
Aparece nas coleções:CQUIXADA - Dissertações defendidas em outras instituições

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2014_dis_libfreitas.pdf1,79 MBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.