Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275634
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Partições de digrafos em caminhos
Title Alternative: Path partitions in digraphs
Author: Pereira, Luiz Fernando de Faria, 1986-
Advisor: Lee, Orlando, 1969-
Abstract: Resumo: Uma partição em caminhos de um grafo dirigido é uma partição do conjunto de vértices deste grafo em caminhos dirigidos. Dada uma métrica sobre partições em caminhos chamada k-norma, o problema de interesse é estabelecer para um dado grafo quais das suas partições em caminhos tem a menor k-norma dentre todas as suas possíveis partições em caminhos. Chamamos estas partições de k-ótimas. Na década de 1980, Claude Berge conjecturou que para toda partição k-ótima, existe um conjunto de k conjuntos independentes disjuntos que, em certo sentido, interceptam o maior número possível de caminhos desta partição. A validade ou a falsidade desta proposição ainda não foi demonstrada, e ela é conhecida como a conjectura de Berge sobre partições em caminhos. Nesta dissertação, fizemos um estudo geral sobre a conjectura de Berge, sua história recente, e o trabalho matemático que foi desenvolvido sobre ela. Exibimos demonstrações para diversos casos particulares da conjectura que já foram resolvidos, como para grafos bipartidos, hamiltonianos, acíclicos, partições compostas somente de caminhos curtos, partições compostas somente de caminhos longos, e para valores fixos de k. Uma parte significativa do trabalho foi dedicada à reescrita da demonstração recente do caso particular onde k = 2, feita por Eli Berger e Irith Hartman, e uma análise do método usado

Abstract: A path partition of a directed graph is a partition of its vertex set into directed paths. Given a metric over path partitions called the k-norm, the problem we are interested in is to determine for a given graph which of its path partitions have the smallest k-norm among all possible path partitions. These partitions are called k-optimal. In the 1980's, Claude Berge conjectured that for every k-optimal path partition, there exists a set of k disjoint independent sets which intercepts the maximum number of paths in this partition. The validity of this proposition has not yet been demonstrated, and it is known as Berge's conjecture on path partitions. In this work, we consider Berge's conjecture, its recent history, and the related mathematical work that has been accomplished. We show proofs for many particular cases of the conjecture, including for acyclic graphs, bipartite graphs, hamiltonian graphs, partitions which include only short paths, partitions which include only long paths, and for fixed values of k. A significant part of this work was dedicated to the rewriting of a recent proof for the particular case where k = 2 by Eli Berger and Irith Hartman, and an analysis of their method
Subject: Teoria dos grafos
Berge, Conjectura de
Language: Português
Editor: [s.n.]
Date Issue: 2013
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Pereira_LuizFernandodeFaria_M.pdf841.92 kBAdobe PDFView/Open


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