O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.

Made available in DSpace on 2014-07-29T16:24:21Z (GMT). No. of bitstreams: 1 ANGEL jose.pdf: 1885350 bytes, checksum: 8203e3220392d36d98c1cc30c0439590 (MD5) Previous issue date: 2005-08-30 / The araticunzeiro (Annona crassiflora Mart.) is a tropical fruit tree species from the Cerrado (Brazilian Savannah) with high economic potential. The strong degradation of the Cerrado, allied to the predatory extractivism that threatens the species, points out to the necessity of development of research to support future conservation programs. With the aim to furnish information about the genetic status of this species and to guide future conservation strategies, 82 individuals from 11 natural populations were submitted to genetic analysis. The coalescent based analysis of the polymorphism present in the trn-L cpDNA allowed the detection of high levels of genetic diversity in the species. In spite of the high level of genetic similarity among different populations the results produced suggested that, , there is an incipient, but statistically significant, increasing differentiation process taking place due to current status of geographical isolation and genetic drift. The genetic differentiation coefficient estimated was equal to 7.3%. The spatial genetic divergence analyses suggested that the genetic distances are not associated to geographical distances between populations, evidencing the absence of current gene flow between adjacent populations. The coalescent based approach allowed the identification of different evolutionary scenes to the investigated populations. Among sampled populations cases from well conserved status to dangerous low levels of genetic diversity were detected. Results obtained by the use of coalescent models to infer the divergence time between populations suggested that natural populations of A. crassiflora were, until recently, part of a great regional continuum. These findings suggest that the low levels of genetic diversity among different populations must be due to the small time since isolation. / O araticunzeiro (Annona crassiflora Mart.) é uma espécie de árvore frutífera nativa do bioma Cerrado com elevado potencial de utilização econômica. A forte degradação desse bioma, aliada ao extrativismo predatório a que a espécie vem sendo submetida, justifica a necessidade de desenvolvimento de pesquisas que subsidiem a sua conservação. Objetivando obter informações que indiquem o status genético dessa espécie e orientem futuras estratégias de conservação, 82 indivíduos provenientes de 11 populações naturais foram analisados geneticamente. A análise do polimorfismo presente em seqüências da região trn-L do genoma cloroplastidial e posterior aplicação dos modelos associados à teoria da coalescência permitiram a detecção de elevados níveis de diversidade genética para a espécie. Os resultados obtidos indicam que, embora as populações amostradas tenham demonstrando elevada similaridade genética entre si, há uma incipiente, mas significativa, diferenciação genética entre elas, que tende a aumentar progressivamente devido ao efeito do isolamento geográfico e à força da deriva. O coeficiente de diferenciação genética entre as populações analisadas foi de 7,3%. A análise de divergência entre as populações amostradas não evidenciou a existência de associação significativa dos padrões de diferenciação genética com a distância geográfica entre elas. As informações obtidas pela análise baseada no modelo de coalescência permitiram a identificação de diferentes cenários evolutivos para as populações estudadas. Dentre as populações amostradas, foram identificadas desde populações em bom estado de conservação até populações com baixíssimos níveis de diversidade genética. Os resultados obtidos pela utilização do modelo coalescente para se inferir o tempo de divergência entre as populações sugeriram que as populações se A. crassiflora até há muito pouco tempo se constituíam em um grande contínuo populacional, sendo a baixa diversidade encontrada entre as populações atribuída ao pequeno tempo de divergência entre elas.