skip to main content
Idioma:
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

Caminhos mais longos em grafos

De Rezende, Susanna Figueiredo

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2014-05-30

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Caminhos mais longos em grafos
  • Autor: De Rezende, Susanna Figueiredo
  • Orientador: Wakabayashi, Yoshiko
  • Assuntos: 2-Árvores; Intersecção; Grafos Exoplanares; Caminhos Mais Longos; Algoritmos De Aproximação; Approximation Algorithms; 2-Trees; Intersection; Longest Paths; Outerplanar Graphs
  • Notas: Dissertação (Mestrado)
  • Descrição: 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.
  • DOI: 10.11606/D.45.2014.tde-10092014-045127
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2014-05-30
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  4 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.