Empacotamento de árvores em grafos completos (2014)
- Authors:
- Autor USP: DIAZ, RENZO GONZALO GÓMEZ - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2014.tde-03022015-115100
- Assunto: TEORIA DOS GRAFOS
- Agências de fomento:
- Language: Português
- Abstract: Nesta dissertacao estudamos problemas de empacotamento de arvores em grafos, com enfase no caso de grafos completos. Denotamos por Ti uma arvore de ordem i. Dizemos que existe um empacotamento de arvores T1, . . . , Tn num grafo G se e possivel encontrar em G subgrafos H1, . . . , Hn, dois a dois disjuntos nas arestas, tais que Hi e isomorfo a Ti. Em 1976, A. Gyarfas e J. Lehel levantaram a seguinte questao, que conjecturaram ter uma resposta positiva: e possivel empaco- tar qualquer sequencia de arvores T1, . . . , Tn no Kn? Esta dissertacao tem como tema principal os estudos realizados por diversos pesquisadores na busca de uma resposta para esta pergunta, que permanece ainda em aberto. Tendo em vista a dificuldade para tratar esta questao, surge natural- mente a pergunta sobre a existencia de classes de arvores para as quais a resposta e afirmativa. Nessa linha, existem diversos resultados positivos, como por exemplo quando queremos empacotar estrelas e caminhos, ou estrelas e biestrelas. Por outro lado, em vez de restringir a classe das arvores, faz sentido restringir o tamanho da sequencia e reformular a pergunta. Por exemplo, dado s < n, e possivel empacotar qualquer sequencia de arvores T1, . . . , Ts no Kn? Em 1983, Bollobas mostrou ? que a resposta e afirmativa se s <= n / sqrt(2). Na primeira parte deste trabalho focamos nosso estudo em questoes desse tipo. Na segunda parte desta dissertacao investigamos algumas conjecturas que foram motivadas pela pergunta levantada por Gyarfas & Lehel. Por exemplo, Hobbs, Bourgeois e Kasiraj formularam a seguinte questao: para n par, e possivel empacotar qualquer sequencia de arvores T1, . . . , Tn no grafo bipartido Kn/2,n-1? Para essa pergunta apresentamos alguns resultados conhecidos analogos aos obtidos para a conjectura de Gyarfas & Lehel. Mais recentemente, Gerbner, Keszegh e Palmer estudaram a seguinte generalizacao da conjectura original: e possivel empacotar qualquer sequencia de arvores T1, . . . , Tk n
- Imprenta:
- Data da defesa: 28.08.2014
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
GÓMEZ DIAZ, Renzo Gonzalo. Empacotamento de árvores em grafos completos. 2014. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2014. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-03022015-115100. Acesso em: 15 abr. 2026. -
APA
Gómez Diaz, R. G. (2014). Empacotamento de árvores em grafos completos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-03022015-115100 -
NLM
Gómez Diaz RG. Empacotamento de árvores em grafos completos [Internet]. 2014 ;[citado 2026 abr. 15 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-03022015-115100 -
Vancouver
Gómez Diaz RG. Empacotamento de árvores em grafos completos [Internet]. 2014 ;[citado 2026 abr. 15 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-03022015-115100
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
