Detalhes bibliográficos
Ano de defesa: |
1994 |
Autor(a) principal: |
Lee, Orlando |
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: |
https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005856/
|
Resumo: |
Nesta dissertacao estudamos varios problemas relacionados com grafos mistos. Tais grafos generalizam a nocao de grafos nao orientados e orientados, no sentido de e que podem conter tanto arco como arestas. Assim, procuramos estudar problemas sobre esses grafos que fossem extencoes naturais de problemas conhecidos sobre grafos nao-orientados e orientados. Tres problemas bastante conhecidos foram tratados no nosso trabalho: o problema de encontrar uma trilha fechada euleriana, o problema do carteiro chines e o problema do caminho minimo. Discutimos a complexidade computacional desses problemas e descrevemos algoritmos polinomiais para alguns (casos particulares) deles. Problemas de orientacao formam outra classe natural de problemas dentro do contexto de grafos mistos. Em particular, estudamos o problema de encontrar orientacoes fortemente conexas e o problema mais geral de encontrar orientacoes k-aresta-conexas de grafos mistos. Por fim, estudamos tambem o problema de aumentar a aresta-conexidade local de grafos mistos. Mais precisamente, estudamos o problema de encontrar um conjunto minimo de arestas (arcos) a serem acrescentados (os) a um grafo misto de modo que no grafo resultante a aresta conexidade entre cada par (u,v) de vertices distintos seja pelo menos um valor pre-estabelecido r (u,v) |