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) |
