Neste trabalho estudamos vários tipos de problemas envolvendo circuitos em grafos mistos. Tais grafos generalizam a noção de grafos orientados e não-orientados, no sentido de poderem conter tanto arcos como arestas. O seguinte problema é tratadoextensivamente em nosso trabalho: dado um grafo misto M com pesos inteiros não-negativos p(e) associados a cada arco/aresta e de M, decidir se existe uma coleção de circuitos de M tal que cada arco/aresta e de M pertence a exatamente p(e)circuitos dessa coleção. Apresentamos uma boa caracterização para o problema assim como um algoritmo polinomial, baseado no método dos elipsóides, para o caso em que M é um grafo misto série-paralelo. Além disso, mostramos que esse problema éNP-difícil para grafos mistos planares. Consideramos também uma relaxação linear desse problema e descrevemos resultados de polinomialidade/complexidade similares. Resultados sobre dois problemas combinatórios bem conhecidos, o problema dedetectar/encontrar circuitos negativos e o problema de encontrar caminhos mínimos, também são apresentados. Seu estudo foi motivado pelas implicações algorítmicas para os problemas mencionados acima. Mostramos que esses problemas são NP-difíceispara grafos mistos planares. Estudamos também o problema de cobrir os arcos e as arestas de um grafo misto com circuitos de modo a minimizar a soma dos comprimentos dos circuitos. Discutimos vários resultados sobre a complexidade (de casosespeciais) do problema, algoritmos de aproximação e sua relação com o problema do carteiro chinês. Descrevemos algoritmos polinomiais para o problema em grafos mistos com largura arbórea limitada. Por fim, estudamos uma famosa conjectura deWoodall que relaciona circuitos e transversais em grafos orientados planares. Provamos que a conjectura é verdadeira para grafos orientados série-paralelos

We study several problems on circuits in mixed graphs. These graphs generalise the notion of undirected graphs, in the sense that they may contain edges as well as arcs. The following problem is extensively studied in our work: given a mixedgraph M with non-negative integer weights p(e) associated with each arc/edge e of M, decide whether there exists a collection of circuits of M such that each arc/edge e of M is contained in exactly p(e) circuits from this collection. We give agood caracterization for the problem and describe a polynomial (ellipsoid based) algorithm for the case in which M is a series-parallel mixed graph. Furthermore, we show that the problem is NP-hard for planar mixed graphs. We also consider alinear relaxation of the problem and describe similar results on complexity and polinomiality. Results on two well-known combinatorial problems, the problem of detecting negative circuits and the problem of finding shortest paths, are alsopresented. This study was motivated by the algorithmic consequences for the problems above mentioned. We prove that these problems are NP-hard for planar mixed graphs. We also study the problem of covering the arcs and the edges of a mixed graphwith circuits so as to minimize the sum of the lenghts of the circuits. We discuss results on the complexity of (special cases of) this problem, approximation algorithms and its relationship with the Chinese Postman problem. We describepolynomial algorithms for the problem restricted to mixed graphs of bounded tree-width. Finally, we study a famous conjecture of Woodall which relates circuits and transversals in planar directed graphs. We show that this conjecture holds forseries-parallel directed graphs