Orientadores: Akebo Yamakami, Marcia Tomie TakahashiTese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de ComputaçãoResumo: A teoria de grafos é uma importante área da programação matemática, tendo um importante papel em áreas tais como engenharia e pesquisa operacional. Em particular, ela fornece ferramentas para tratar problemas de redes (tais como: alocação, caminho mínimo, fluxo máximo, etc.), que têm aplicações em diversas subáreas da engenharia (por exemplo: telecomunicações, transporte, manufatura, etc.). Estas aplicações podem, entretanto, possuir incertezas em seus parâmetros ou em sua estrutura. Baseado nisto, este trabalho trata de algumas importantes aplicações de problemas em grafos com incertezas em seus parâmetros ou estruturas e propõe algoritmos para encontrar suas soluções. As aplicações estudadas são: problemas de caminho mínimo, problemas de fluxo máximo, problemas de fluxo de custo mínimo e problemas de coloração de grafos. As incertezas são modeladas por meio da teoria dos conjuntos fuzzy, que tem sido aplicada com sucesso em problemas com incertezas e imprecisõesAbstract: The graph theory is an important area of mathematical programming, it has an important role in fields such as engineering and operational research. In particular, it provides the tools to tackle network problems (e.g. allocation, shortest path, maximum flow, etc), which have applications in several sub areas of engineering (e.g. telecommunications, transportation, manufacturing, etc). These applications can, however, possess uncertainties in their parameters or in their structure. Based on that, this work addresses some important applications of graph problems with uncertainties in their structure or parameters and proposes algorithms to find the solution to them. The applications studied are: shortest path problems, maximum flow problems, minimum cost flow problems and graph coloring problems. The uncertainties are modeled by means of the fuzzy sets theory, which has been successfully applied to problems with uncertainties and vaguenessDoutorado�rea de Concentração: AutomaçãoTitulação: Doutor em Engenharia Eletrica