Detalhes bibliográficos
| Ano de defesa: |
2011 |
| Autor(a) principal: |
Parente, Roberto Freitas |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22032012-150640/
|
Resumo: |
Seja H\' uma orientação do grafo H. Alon e Yuster [The number of orientations having no fixed tounament, Combinatória, 26 (2006), no. 1, 1-6] propuseram o problema de determinar ou estimar D(n,m,H\'), a quantidade máxima de orientações livres de H\' de um grafo com n vértices e m arestas. Se substituirmos o máximo pelo \'máximo essencial\', ou seja, consideramos o máximo sobre quase todos os grafos de n vértices e com m arestas, em oposição à todos deles, o problema é mais acessível. Mostramos que esse máximo essencial é 2^o(m) se H\' é o circuito direcionado cíclico C\'_l de tamanho l (l >= 3), se m >> n^{1+1/(l-1)}. Por outro lado, o mínimo essencial é 2^(1-o(1))m, se m << n^{1+1/(l-1)}. O método de prova nos dá resultado da mesma natureza para grafos orientados bipartidos H\' que contém circuito direcionado cícliclo. |
