In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / O presente trabalho aborda um teorema classico de decomposiÃÃo do espaÃo das p-formas suaves sobre uma variedade Riemaniana compacta e orientada, conhecido como teorema da decomposiÃÃo de Hodge, assim como suas consequÃncias. No decorrer do mesmo, foi feita uma passagem por diversas ferramentas interessantes, como espaÃos Sobolev (capÃtulo 2) e EDP elÃptica (capÃtulo 3), assim como uma abordagem suscinta de formas diferenciÃveis. / This dissertation presents a classical theorem of decomposition of the space of smooths p-forms on compact oriented Riemannian manifold , known as the theorem of Hodge decomposition, and its consequences. During the same was made a passage for several interesting tools, such as Sobolev spaces(Chapter 2) and elliptical PDE (Chapter 3), as well as a succinct approach about diferenciable forms (Chapter 1).

Made available in DSpace on 2016-08-17T14:52:58Z (GMT). No. of bitstreams: 1 Carlos Enrique Portugal Poma.pdf: 930704 bytes, checksum: 1e44612726c21248a8ea95ec5cc5ebe8 (MD5) Previous issue date: 2005-04-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The present work investigates and compares the computational performance of numerical techniques, selected from specialized literature and applied to the solution of large-scale algebraic and differential equations. Among the considered techniques, emphasis was given to the method known as MEBDF (Modified Extended Backward Differentiation Formulae), because it presents properties that the conventional BDF (Backward Differentiation Formulae) methods do not have, and these properties may improve its computational performance in certain applications. The numerical methods considered in this research are available as computational numerical codes, known as solvers, and they are of public domain. The ones considered here are the MEBDFSD, MEBDFI, DASSL and RADAU. The computational tests considering these numerical codes are related to simulations of power system transient angular stability and long-term voltage stability in the time domain. The main objective was to check the efficiency of these numerical techniques under two aspects, namely, the computational efficiency and numerical accuracy. The computational aspect is related to the simulation CPU time, and accuracy is related to the obtained numerical results, since these methods use, in general, approximation techniques. A conventional stability program was used to validate the results. Computational analysis was performed using the following test systems: IEEE118 buses with 54 generators, IEEE145 buses with 50 generators, and an equivalent south-southeast Brazilian power system. The obtained results indicate that the MEBDFSD performance is better rather than the other methods considered here. / O presente trabalho investiga e compara o desempenho computacional de técnicas numéricas selecionadas na literatura especializada aplicadas na solução de sistemas de equações diferenciais e algébricas de grande-porte. Entre os métodos considerados, foi dada maior ênfase ao método conhecido como MEBDF (Método de Diferenciação Regressiva Modificado Estendido), por este apresentar propriedades que os BDF (Método de Diferenciação Regressiva) convencionais não apresentam, sendo que estas propriedades podem resultar em melhorias no seu desempenho computacional em certas aplicações. Os métodos numéricos considerados neste trabalho estão disponíveis sob a forma de códigos numéricos computacionais (solvers) de domínio público, sendo estes o MEBDFSD, MEBDFI, DASSL e RADAU. Os testes computacionais considerando estes códigos envolvem simulações no domínio do tempo de fenômenos de estabilidade em sistemas de energia elétrica de curta-, e de longa-duração (angular e de tensão, respectivamente). O objetivo principal foi verificar a eficiência dessas técnicas numéricas sob dois aspectos, computacional e precisão. O aspecto computacional está relacionado com o tempo de cpu gasto nas simulações. Já o aspecto precisão está relacionado com os valores numéricos obtidos já que estes métodos utilizam, em geral, técnicas de aproximação. Um programa convencional de estabilidade foi usado para validar a precisão numérica dessas técnicas. Nas análises computacionais, foram usados os seguintes sistemas-testes: IEEE118 barras com 54 geradores, IEEE150 barras com 50 geradores e uma configuração de um sistema brasileiro equivalente sul-sudeste com 44 geradores. Os resultados comprovaram a melhor eficiência do MEBDFSD em comparação com as demais técnicas consideradas neste trabalho.

L'indication Géographique, signe distinctif particulièrement spécifique, a connu au XIXème et XXème siècle, par, notamment des législations nationales éparses, des accords bilatéraux ou des conventions multilatérales, voire même l'utilisation contentieuse des moyens juridiques de lutte contre la concurrence déloyale, différents types de protection utiles mais limités. Ces derniers, appuyés par l'intervention de la Communauté Européenne, ont, néanmoins, eu le grand avantage de rendre possible l'émergence internationale, dans l'Accord ADPIC, d'une section spécifique dédiée. Ce texte issu des Accords de Marrakech instituant, en 1994, l'Organisation Mondiale du Commerce (OMC) reconnaît, en effet, l'Indication Géographique comme l'objet d'un droit autonome de Propriété Intellectuelle. Il lui permet de disposer d'une définition et d'un régime juridique, et surtout oblige les différents Membres de l'OMC, à le reconnaître et à le protéger. En posant un principe de liberté dans la mise en œuvre de ce dispositif nouveau qui, contrairement aux autres Droits de Propriété Intellectuelle, et en particulier aux marques, ne s'applique pas à un système préexistant, cet Accord a eu pour conséquence non pas une uniformisation, mais une certaine hétérogénéité des situations nationales. Celles-ci ont pu conduire, dans certains cas, à un métissage ou à une substitution des concepts, notamment à cause de l'intégration des Indications Géographiques dans des systèmes préexistants de Propriété Intellectuelle, comme celui des marques de certification / Geographical Indication, a particularly specific distinguishing sign, experienced throughout the XIXth and XXth centuries, under specially scattered national legislations, joint conventions or bilateral agreements, even under the contentious use of legal means to combat unfair competition, different types of useful but limited protection. These latter, supported by the intervention of the European Community, had however the advantage of contributing to make a specific dedicated section emergence possible in the Trip's agreement. This text coming from the Marrakech Agreements which established in 1994 the World Trade Organization (WTO), recognizes in fact the Geographical Indications as an independent law of Intellectual Property. It allows them to rely on a definition and a legal system, and bind the different members of the WTO to their recognition and protection. In asserting a principle of liberty in the implementation of this new system which, contrary to the other rights of Intellectual Property, and particularly of marks, does not apply to a preexisting system, this Agreement has not resulted in a uniform effect but heterogeneity of national situations. In special cases, these situations may have led to a knowledgeable mix or substitution of concepts, particularly because of the Geographical Indications integration into preexisting systems of Intellectual Property such as certification marks. Beyond the recognition of the Geographical Indication definition in these texts, the existence of two types of protection, simple and additional, has also practical consequences on these different integrations

Dans cette thèse nous étudions quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjecture. / In this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture.

O teste de software engloba diferentes técnicas, métodos e conceitos capazes de garantir a qualidade dos mais variados tipos de sistemas. Dentre tais técnicas, encontra-se o teste baseado em Máquinas de Estados Finitos (MEFs), que visa a garantir a conformidade entre a implementação e a especificação de um software. Com esse propósito, diversos métodos foram propostos para a geração de seqüências de verificação que garantam cobertura total das possíveis falhas existentes em uma implementação. A maioria dos métodos conhecidos são baseados na utilização de seqüências de distinção. Esse recurso, porem, não existe para toda MEF. Alguns métodos buscam a geração de seqüências de verificação baseados em recursos alternativos as seqüências de distinção, contudo, as seqüências geradas são exponencialmente longas. Este trabalho apresenta um método para geração de seqüências de verificação que visa a reduzir o tamanho das seqüências geradas para o domínio de MEFs que não dispõem de seqüência de distinção. Para isso, o método proposto baseia-se na utilização de conjuntos de distinção. Uma avaliação experimental foi realizada afim de mensurar a redução proporcionada pelo método proposto em relação aos principais métodos existentes na literatura. Com esse intuito, foram geradas MEFs aleatórias sob a perspectiva diferentes fatores. Em relação a variação do número de estados, os resultados indicaram reduções acima de 99; 5% em comparação com os métodos existentes, quando analisadas 75% das MEFs geradas / Software testing involves several techniques, methods, and concepts employed to guarantee a high level of quality in different application domains. Among such techniques, Finite State Machine (FSM) based testing aims to guarantee the conformance between the implementation and the specification of a system under test. In this context, several methods were proposed to generate checking sequences that cover all the possible faults existing in an implementation. Most of these methods are based on a special sequence, named distinguishing sequence, which does not exist for every minimal machine. Some methods were proposed to generate checking sequences based on alternative solutions in order to be applied on FSMs that do not have distinguishing sequences. However, these methods generate checking sequences exponentially long. This work proposes a method to generate checking sequences using identification sets. These sets exist for every minimal FSM and also lead to shorter checking sequences. We conducted an experimental study to compare the proposed method with the main existing methods. In the experiments, we used random FSMs that have different configurations of states, inputs, and outputs. Concerning the variation of number of states, the results show reductions higher than 99:5% in comparison with the existing methods for 75% of the experimented machines

Ce mémoire analyse la notion de fonctionnalité. D'origine jurisprudentielle, ce concept tend à maintenir la dichotomie traditionnelle entre le régime des marques de commerce et celui des brevets. À la lecture des jugements rendus en la matière, le maintien d'une telle dichotomie empêcherait notamment de prolonger indûment un monopole échu sous le régime des brevets par l'enregistrement d'une marque de commerce. Cette étude tente de mieux cerner le concept de fonctionnalité et, plus précisément, de justifier son existence. Pour ce faire, une étude approfondie des régimes des marques de commerce et des brevets, nous permet de comprendre que chacun de ces corps de règles répond à une logique différente. Les fonctions des marques de commerce et des brevets sont en effet distinctes et aucun chevauchement ne semble être permis. Cette situation est d'ailleurs propre à ces régimes spécifiques. Un examen de l'étendue de la notion de fonctionnalité nous permet de constater que d'autres droits de propriété intellectuelle peuvent coexister. À titre d'exemple, nous croyons qu'une intersection est possible entre les régimes des dessins industriels et des marques de commerce. À l'issue de ces recherches, nous constatons que la notion de fonctionnalité est un principe jurisprudentiel bien établi en droit canadien visant à empêcher tout renouvellement à perpétuité d'un brevet par le biais du droit des marques de commerce. L'existence de ce principe nous semble être justifiée en matière de marques de commerce et de brevets. Cette conclusion pourrait toutefois différer dans le cadre d'autres droits de propriété intellectuelle, les fonctions de ces autres régimes semblant permettre des chevauchements. / This memory analyzes the notion of functionality. Of case law origin, this concept tends to maintain the traditional dichotomy between trademarks and patents regimes. In light of judgments rendered on that matter, the preservation of such dichotomy would notably prevent from illegally prolonging a monopoly fallen under the regime of patents by the registration of a trademark. This study tries to understand the concept of functionality and, more specifically, to justify its existence. In order to reach this goal, a detailed study of the regimes of trademarks and patents lead us to conclude that each of these bodies of rules answers to a different logic. Indeed, the functions of trademarks and patents are different and no overlapping seems to be allowed. This situation is particular to these two specific regimes. An examination of the area of the notion of functionality leads us to notice that other rights of intellectual property can coexist. For example, we believe that an intersection is possible between the regimes of industrial designs and trademarks. As a conclusion, we notice that the notion of functionality is a well established principle in Canada which tends to prevent any perpetual renewal of a patent under the trademarks regime. We believe that the existence of this concept is justified under trademarks and patents laws. However, this conclusion could differ within the framework of the other intellectual property rights, since these other rights' functions seem to allow an intersection between them.

Ce mémoire analyse la notion de fonctionnalité. D'origine jurisprudentielle, ce concept tend à maintenir la dichotomie traditionnelle entre le régime des marques de commerce et celui des brevets. À la lecture des jugements rendus en la matière, le maintien d'une telle dichotomie empêcherait notamment de prolonger indûment un monopole échu sous le régime des brevets par l'enregistrement d'une marque de commerce. Cette étude tente de mieux cerner le concept de fonctionnalité et, plus précisément, de justifier son existence. Pour ce faire, une étude approfondie des régimes des marques de commerce et des brevets, nous permet de comprendre que chacun de ces corps de règles répond à une logique différente. Les fonctions des marques de commerce et des brevets sont en effet distinctes et aucun chevauchement ne semble être permis. Cette situation est d'ailleurs propre à ces régimes spécifiques. Un examen de l'étendue de la notion de fonctionnalité nous permet de constater que d'autres droits de propriété intellectuelle peuvent coexister. À titre d'exemple, nous croyons qu'une intersection est possible entre les régimes des dessins industriels et des marques de commerce. À l'issue de ces recherches, nous constatons que la notion de fonctionnalité est un principe jurisprudentiel bien établi en droit canadien visant à empêcher tout renouvellement à perpétuité d'un brevet par le biais du droit des marques de commerce. L'existence de ce principe nous semble être justifiée en matière de marques de commerce et de brevets. Cette conclusion pourrait toutefois différer dans le cadre d'autres droits de propriété intellectuelle, les fonctions de ces autres régimes semblant permettre des chevauchements. / This memory analyzes the notion of functionality. Of case law origin, this concept tends to maintain the traditional dichotomy between trademarks and patents regimes. In light of judgments rendered on that matter, the preservation of such dichotomy would notably prevent from illegally prolonging a monopoly fallen under the regime of patents by the registration of a trademark. This study tries to understand the concept of functionality and, more specifically, to justify its existence. In order to reach this goal, a detailed study of the regimes of trademarks and patents lead us to conclude that each of these bodies of rules answers to a different logic. Indeed, the functions of trademarks and patents are different and no overlapping seems to be allowed. This situation is particular to these two specific regimes. An examination of the area of the notion of functionality leads us to notice that other rights of intellectual property can coexist. For example, we believe that an intersection is possible between the regimes of industrial designs and trademarks. As a conclusion, we notice that the notion of functionality is a well established principle in Canada which tends to prevent any perpetual renewal of a patent under the trademarks regime. We believe that the existence of this concept is justified under trademarks and patents laws. However, this conclusion could differ within the framework of the other intellectual property rights, since these other rights' functions seem to allow an intersection between them.

Cette thèse se situe dans le domaine de graphes et de leurs applications, Elleest constitué de trois grandes parties, la première est consacrée à l’étude d’unnouveau type de coloration sommets distinguantes, les arête-colorations sommetsdistinguantespar écarte. Il consiste de trouver une valuation des arêtes qui permettede distinguer les sommets de graphes telle que chaque sommet v du graphe est identifiéde façon unique par la différence entre la plus grande et la plus petite des valeursincidentes à v. Le plus entier pour lequel le graphe G admet une arête-colorationsommets-distinguantes par écarte est le nombre chromatique par écart de G, notégap(G). Nous avons étudié ce paramètre pour diverses familles de graphes. Uneconjecture intéressante, proposée dans cette partie, suggère que le nombre chromatiquepar écart de tout graphe connexe d’ordre n > 2 vaut n - 1, n ou n + 1.La deuxième partie du manuscrit concerne le problème du placement de graphes.Nous proposons un état de l’art des problèmes de placement de graphes, puis nousintroduisons la nouvelle notion de placement de graphes étiquetés. Il s’agit d’unplacement de graphes qui préserve les étiquettes des sommets. Ensuite, nous proposonsdes encadrements de ce nouveau paramètre pour plusieurs classes de graphes.La troisième partie de la thèse s’intéresse au problème d’appariement d’arbres dansle cadre de la recherche d’information dans des documents structurés de type XML.Les algorithmes holistique de jointure structurelle est l’une des premières méthodesproposées pour résoudre l’appariement exact des documents XML. Ces algorithmessont souvent divisés en deux grandes étapes. La première étape permet de décomposerl’arbre de la requête en un ensemble de petites composantes connexes. Ensuite,des solutions intermédiaires pour chaque composante de la requête sont trouvées, cesrésultats intermédiaires sont joints pour obtenir la solution finale. Nous proposonsdans cette partie un nouvel algorithme appelé TwigStack++ qui vise principalementà diminuer le coût de la jointure et le calcule inutile recherche. Notre algorithmeobtient de meilleurs résultats en comparaison avec deux autres méthodes de l’étatde l’art. / In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

Cette thèse étudie la coloration d'arcs et de cycles dans les graphes orientés. Elle se concentre sur les sujets suivants : la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés, les cycles courts dans les graphes orientés avec des sous-graphes interdits, les cycles sommet-disjoints dans dans les tournois bipartis, les cycle-facteurs dans les tournois bipartis régulier et les arcs universels dans les tournois. La thèse est basée sur cinq articles originaux publiés ou présentés dans des journaux. Les principaux résultats sont les suivants. Nous introduisons la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés. Nous avons proposé une conjecture sur le nombre arc-chromatique sommet-distingué et nous avons aussi donné quelque résultats partiels. Nous avons étendu un résultat de Razborov en prouvant que la conjecture de Caccetta-Häggkvist est vraie pour certains graphes orientés avec des sous-graphes interdits. Nous avons montré que chaque tournoi biparti avec degré sortant minimum au moins qr-1 contient r cycles de sommets-disjoints de toutes longueurs possibles. Le cas spécial q=2 confirme le cas du tournoi biparti de la conjecture de Bermond-Thomassen. Nous avons montré que chaque tournoi biparti k-régulier avec k>2 que l'on notera B a deux cycles complémentaires de longueurs 6 et |V(B)-6|, à moins que B soit isomorphe à un graphe spécifique, étayant ainsi une conjecture sur des 2-cycles-facteurs dans les tournois bipartis. En outre, nous montrons que tous les tournois bipartis réguliers ont un k-cycle-facteur. Nous donnons une condition nécessaire et suffisante pour l'existence d'un arc universel dans un tournoi et nous caractérisons tous les tournois où chaque arc est universel. / In this thesis, we study arc colorings and cycles in digraphs. The following topics are considered: vertex-distinguishing proper arc colorings in digraphs, short cycles in digraphs with forbidden subgraphs , disjoint cycles in bipartite tournaments, cycle factors in regualr bipartite tournaments and universal arcs in tournaments. The main results are contained in five original articles published or submitted to an international journal. We introduce vertex-distinguishing proper arc colorings of digraphs. A conjecture on the vertex-distinguishing arc-chromatic number is given and some partial results are obtained. We extend a result of Razborov by proving that the Caccetta-Häggkvist conjecture is true for digraphs with certain induced forbidden subgraphs or with certain forbidden subgraphs. We show that every bipartite tournament with minimum outdegree at least qr-1 has r vertex disjoint cycles of any given possible lengths. The special case q=2 of the result verifies the bipartite tournament case of the Bermond-Thomassen conjecture. As a partial support of a conjecture on 2-cycle-factors in bipartite tournaments, we prove that every k-regular bipartite tournament B with k>2 has two complementary cycles of lengths 6 and |V(B)|-6, unless B is isomorphic to a special digraph. Besides, we show that every k-connected regular bipartite tournament has a k-cycle-factor. We also give a sufficient and necessary condition for the existence of a universal arc in a tournament and characterize all the tournaments in which every arc is universal.