Tese

Caminhos mais longos em grafos (2014)

• Authors:
  • De Rezende, Susanna Figueiredo
  • Wakabayashi, Yoshiko (Orientador)
• Autor USP: REZENDE, SUSANNA FIGUEIREDO DE - IME
• Unidade: IME
• Sigla do Departamento: MAC
• Subjects: TEORIA DOS GRAFOS; OTIMIZAÇÃO COMBINATÓRIA
• Agências de fomento:
  • Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
• Language: Português
• Abstract: 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.
• Imprenta:
  • Publisher place: São Paulo
  • Date published: 2014
• Data da defesa: 30.05.2014


---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  DE REZENDE, Susanna Figueiredo. Caminhos mais longos em grafos. 2014. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2014. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092014-045127. Acesso em: 28 dez. 2025.

• APA

  De Rezende, S. F. (2014). Caminhos mais longos em grafos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092014-045127

• NLM

  De Rezende SF. Caminhos mais longos em grafos [Internet]. 2014 ;[citado 2025 dez. 28 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092014-045127

• Vancouver

  De Rezende SF. Caminhos mais longos em grafos [Internet]. 2014 ;[citado 2025 dez. 28 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-10092014-045127

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• Intersecting longest paths