In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.

Submitted by Jos? Henrique Henrique (jose.neves@ufvjm.edu.br) on 2017-04-25T14:57:15Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) lais_matos_oliveira.pdf: 1897599 bytes, checksum: f8cca6f71386c22ad68bc755f7803402 (MD5) / Approved for entry into archive by Rodrigo Martins Cruz (rodrigo.cruz@ufvjm.edu.br) on 2017-05-16T19:49:29Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) lais_matos_oliveira.pdf: 1897599 bytes, checksum: f8cca6f71386c22ad68bc755f7803402 (MD5) / Made available in DSpace on 2017-05-16T19:49:29Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) lais_matos_oliveira.pdf: 1897599 bytes, checksum: f8cca6f71386c22ad68bc755f7803402 (MD5) Previous issue date: 2016 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / Objetivou-se com este estudo avaliar as caracter?sticas fisiol?gicas de diferentes grupos gen?ticos mantidos no cerrado. Foram avaliados 48 bovinos de corte criados em sistema precoce para abate aos 24 meses, sendo seis machos e seis f?meas de cada grupo gen?tico (Nelore, ? Nelore x ?Caracu, ? Caracu x ? Nelore, ? Angus x ? Nelore x ?Caracu). Os par?metros fisiol?gicos taxa de suda??o (TS), frequ?ncia card?aca (FC), frequ?ncia respirat?ria (FR), temperatura retal (TR), temperatura da superf?cie corporal (TSC) foram obtidos entre 07:00 e 12:00h. Foram avaliados o comprimento, n?mero de pelos por unidade de ?rea, densidade de massa dos pelos e di?metro m?dio dos pelos. A colora??o do pelo e pele foram avaliadas por meio da Tabela Padr?o e do color?metro MniScan XE Plus. O delineamento experimental foi o inteiramente casualizado em esquema fatorial com seis repeti??es. Foi utilizado o procedimento GLM do SAS, adotando-se para compara??o de m?dias o teste t com n?vel de signific?ncia de 5%. O NEL apresentou maior FR seguido pelo ?NCAR. A FC foi maior no ver?o. A TS foi maior no ver?o em rela??o ao outono. A TR foi maior no ?NCAR, seguido pelo ?CAR, sendo a menor TR observada no NEL e TRI. Houve correla??o positiva entre a temperatura do olho e a temperatura retal. Os pelos do dorso e garupa foram mais compridos no outono, e, em rela??o ao sexo, maiores nas f?meas. O comprimento dos pelos na garupa foi maior no TRI, seguido pelo ?CAR, NEL e ?NCAR. O di?metro dos pelo do dorso foi maior para o ?NCAR, seguido pelo ?CAR, TRI e NEL. O n?mero de pelos na garupa foi maior n?mero no ver?o. Os pelos do dorso foram mais inclinados no ?NCAR, seguidos pelo ?CAR, NEL e TRI. No ver?o, os pelos do dorso permaneceram mais inclinados, e, em rela??o ao sexo, os machos tiveram maior inclina??o no dorso e garupa. A densidade dos pelos no dorso e garupa foi maior no outono. Os pelos da garupa foram mais densos no ?NCAR, seguidos do ?CAR, TRI e NEL. A EC no dorso foi maior no TRI, seguida pelo NEL, ?CAR e ?NCAR. Entre os sexos a EC foi maior nas f?meas. A EC na garupa foi maior no TRI, seguida pelo ?CAR, NEL e ?NCAR. Os pelos tanto do dorso quanto da garupa foram mais claros no NEL. Os pelos mais escuros no dorso foram observados no TRI e na garupa no ?CAR. O grupo gen?tico que demonstrou maior adapta??o ? cria??o no Cerrado foi o NEL seguido do ?NCAR. / Disserta??o (Mestrado) ? Programa de P?s-Gradua??o em Zootecnia, Universidade Federal dos Vales do Jequitinhonha e Mucuri, 2016. / The objective with this study was to evaluate the physiological characteristics of different genetic groups maintained in the savannah. Thirty-eight beef cattle raised in a system to be slaughter at 24 months of age were evaluated, with six males and six females of each genetic group (Nellore; ? Nellore x ? Caracu; ? Caracu x ? Nellore; and ? Angus x ? Nellore x ? Caracu). Sweating rate (SR), heart rate (HR), respiratory rate (RR), rectal temperature (RT) and body surface temperature (BST) were obtained between 07:00 and 12:00. Length, number of furs per unit area, mass density of the fur, and the average furs diameter were assessed. Fur and skin coloring were evaluated using the Standard Table and the MniScan XE Plus colorimeter. The experimental design was the completely randomized in a factorial scheme with six replicates. The GLM procedure of SAS was used, adopting the t test for mean comparison with significance level of 5%. The NEL presented higher RR followed by ? NCAR. The HR was higher in the summer. The SR was greater in the summer compared with the autumn. The RT was higher in the ?NCAR, followed by ?CAR, with the lower RT observed in NEL and TRI. There was a positive correlation between eye temperature and rectal temperature. The furs of the dorsum and rump were longer in the autumn, and, in relation to sex, larger in females. The fur length on the rump was longer in TRI, followed by ?CAR, NEL and ?NCAR. The fur diameter on the dorsum was larger for ?NCAR, followed by ?CAR, TRI and NEL. The number of furs on the rump was higher in the summer. The furs on the dorsum were more inclined in ?NCAR, followed by ?CAR, NEL, and TRI. In the summer, the furs on the dorsum remained more leaned, and, in relation to sex, the males have a higher inclination on the dorsum and rump. Fur density on the dorsum and rump was higher in autumn. The furs of the rump were denser in ?NCAR, followed by ?CAR, TRI, and NEL. The EC on the dorsum was higher in TRI, followed by NEL, ? CAR, and ?NCAR. Among the sexes, the EC was higher in females. The EC on the rump was higher in TRI, followed by ? CAR, NEL and ?NCAR. The furs on both dorsum and rump were clearer in the NEL. The darker furs on the dorsum were observed on TRI and on the rump on ? CAR. The genetic group that demonstrated the greatest adaptation to the raising in the savannah was NEL followed by ?NCAR.

Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits. / Graphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the use of decomposition technique in solving some optimization problems. We prove the optimal χ -bounding function for this class and show that it has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm.Finally, the connected greedy coloring in claw-free graphs is considered. A natural way to color a graph is to have an order of its vertices and assign for each vertex the first available color. A lot of researches have been done for general orders. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring. We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs.

Dans cette thèse, nous nous intéressons aux aspects algorithmiques et applications de deux problèmes de graphes, à savoir, la coloration et les alliances. La première partie concerne deux variantes de la coloration de graphes, la coloration Grundy et la coloration forte stricte. Nous commençons par l'étude du nombre Grundy des graphes réguliers. Nous donnons une condition fixe k, nous fournissons une condition nécessaire et suffisante pour que le nombre Grundy d'un graphe régulier soit au moins égal k. Nous caractérisons la classe des graphes cubiques (3-réguliers) pour laquelle le nombre Grundy est égal à 4, et nous présentons un algorithme linéaire pour déterminer le nombre Grundy d'un graphe cubique quelconque. Par ailleurs, en se basant sur la coloration forte stricte pour décomposer les arbres en petites composantes, nous présentons un nouvel algorithme pour l'appariement d'arbres étiquetés, non-ordonnés non-enracinés. Nous montrons que la distance calculée entre deux arbres est une pseudo-métrique. Nos expérimentations sur de larges bases synthétiques et des bases de données réelles confirment nos résultats analytiques et montrent que la distance proposée est précise et son algorithme est scalable. La seconde partie de cette thèse est consacrée aux alliances dans les graphes. Nous proposons un algorithme distribué autostabilisant pour la construction d'alliance offensive globale minimale dans un graphe arbitraire. Nous démontrons que cet algorithme converge sous le démon synchrone en temps linéaire. Ensuite, nous donnons le premier algorithme distribué autostabilisant pour le problème de l'alliance forte globale minimale dans un graphe quelconque. Nous prouvons que cet algorithme est polynomial sous le démon inéquitable distribué. Nous montrons par la suite, comment cet algorithme peut être adapté pour des généralisations du problème, comme la k-alliance forte et l'alliance forte pondérée. Enfin, en se basant sur les propriétés structurelles de l'alliance offensive, nous présentons une solution pour décentraliser le protocole de signalisation SIP. Ceci rend possible son déploiement dans un réseau mobile ad hoc / This thesis investigates the algorithmic aspects and applications of two graph problems, namely, colorings and alliances. In the first part, we focus on two variants of the proper vertex coloring, the Grundy coloring and the strict strong coloring. We start by the study of Grundy number for regular graphs. We give a sufficient condition for d-regular graphs with sufficiently large girth to have Grundy number equals d + 1. Then, using graph homomorphism, we obtain a necessary and sufficient condition for d-regular graphs to have Grundy number at least k. Moreover, we characterize cubic graphs (3-regular) for which the Grundy number is d + 1, and present a linear-time algorithm to determine the Grundy number of any arbitrary cubic graph. Subsequently, based on the strict strong coloring, we present an approach for the problem of matching labeled trees. Using this coloring, we propose a new algorithm to deterministically decompose a tree into small components. This leads to an efficient algorithm to measure an accurate distance between unrooted unordered labeled trees. The second part is devoted to the alliances in graphs. We first propose a linear-time self-stabilizing algorithm for the minimal global offensive alliance set problem, under the synchronous distributed scheduler. Then, we give the first self-stabilizing algorithm for the minimal global powerful alliance set problem in arbitrary graphs. Moreover, we show how this algorithm can be adapted to find the minimal global powerful k-alliance and the minimal weighted global powerful alliance sets. We prove that all these algorithms converge in polynomial-time under the unfair distributed scheduler. Finally, based on the structural properties of the offensive alliance, we propose a solution to decentralize the signaling protocol SIP. This enables SIP applications in mobile ad hoc networks

This thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices is connected by atleast one path in which no two edges are coloured the same. The rainbow connection number of a graph is the minimum number of colours required to rainbow colour it. In this thesis we give upper bounds on rainbow connection number based on graph invariants like minimum degree, vertex connectivity, and radius. We also give some computational complexity results for special graph classes. Product dimension The product dimension or Prague dimension of a graph G is the smallest natural number k such that G is an induced subgraph of a direct product of k complete graphs. In this thesis, we give upper bounds on the product dimension for forests, bounded tree width graphs and graphs of bounded degeneracy. Boxicity and cubicity The boxicity (cubicity of a graph G is the smallest natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes(axis-parallel unit cubes) in Rk .In this thesis, we study the boxicity and the cubicity of Cartesian, strong and direct products of graphs and give estimates on the boxicity and the cubicity of a product graph based on invariants of the component graphs. Separation dimension The separation dimension of a hypergraph H is the smallest natural number k for which the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyper plane normal to one of the axes. While studying the boxicity of line graphs, we noticed that a box representation of the line graph of a hypergraph has a nice geometric interpretation. Hence we introduced this new parameter and did an extensive study of the same.

Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possible. / In this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible.

The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.

In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.

「甲骨塗辭」乃指在甲骨刻辭筆畫中塗以朱、墨，以往學者將之稱為「塗朱/墨」或「填朱/墨」，這類刻辭在刻寫完成之後，以朱砂或墨填入刻痕。其中，塗朱甲骨色彩鮮明奪目，很早就受到學者注意，其目的有美觀、宗教意涵、重要訊息的不同說法。然而，受限於甲骨著錄多為黑白拓本形式、早期彩色印刷不發達，目前甲骨學界尚無學者對塗辭做出專門且深入的研究。所幸，近年來出版之甲骨著錄附有彩色相片，部分甲骨收藏單位架設數位資料庫，如中研院史語所，所能蒐羅之資料備於完善，為甲骨塗辭研究奠定基礎。 本文以「塗朱甲骨」作為主要討論對象，試圖將辭例或形狀完整的塗朱卜辭進行分類。首先於第二章探討塗朱甲骨的年代以及塗朱甲骨的幾項特徵，包含：牛胛骨骨面塗朱卜辭、犯兆塗朱卜辭、塗朱記事刻辭。第三章及第四章則以塗朱甲骨的形態進行討論，分別以顏色及辭例的完整度作為分類標準。以顏色劃分塗朱甲骨可分為三類：僅見塗朱者、朱墨褐三色同版者、朱墨或朱褐同版者。以辭例完整度可分成八類。 / The incised characters on oracle bones rubbed with cinnabar or ink are called cinnabar inscriptions or ink inscription. The vermillion colored cinnabar used on the coloring of oracle bones is said to have religious messages or aesthetic purposes. Previously limited by the immature color printing and computer technology, oracle bones inscriptions were mostly rubbing editions in black and white, and thus there are few in-depth studies on the coloring of oracle bone inscriptions. But now a corpus of oracle bones is taking form, such as editions with color pictures and digitalization of oracle bones images by Institute of History and Philosophy, Academia Sinica. This paper aims to examine the cinnabar inscriptions on oracle bones, discuss their characteristics in different periods, and categorize them into three categories based on colors, and eight categories based on the intactness of the inscriptions.

J'ai étudié trois problèmes d'optimisation dans les graphes et les jeux combinatoires.Tout d'abord, les codes identifiants dans les graphes où les sommets font faces à des failles: les codes cherchent à repérer les failles pour les réparer. On s'est intéressé aux codes identifiants dans les graphes circulants en utilisant des plongements de ces graphes dans des grilles infinies.Ensuite, j'ai étudié le jeu de marquage de sommets et le jeu de coloration d'arêtes: ici deux joueurs se font face, le premier cherche à construire une coloration correcte (ou un marquage correct) et le deuxième cherche à l'en empêcher. Pour le jeu de marquage on s'est intéressé aux changements de stratégie gagnante lorsqu'on modifie le graphe. Pour le jeu de coloration d'arêtes on a donné une stratégie gagnante pour le premier joueur pourvu que le graphe considéré admette une certaine décomposition sur les arêtes. On améliore notamment des résultats sur les graphes planaires.Enfin j'ai étudié les jeux à tas purement de casse: deux joueurs à tour de rôle prennent un tas et le cassent en un certain nombre de tas non vides. On s'intéresse aux stratégies gagnantes lorsque les joueurs jouent sur un unique tas contenant n jetons. Ces jeux de pure casse semblent, à l'oeil nu, être réguliers. On a montré que c'est effectivement le cas pour certains et on a donné un test qui permet de déterminer la régularité cas par cas. Un seul cas ne semble pas correspondre à cette régularité: son comportement reste un mystère.En conclusion, je me suis intéressé à trois problèmes bilatéraux qui utilisent différentes méthodes et qui remplissent des propos différents dans le domaine de la combinatoire / I studied three optimization problems on graphs and combinatorial games.First, identifying codes were studied : vertices couteract faults. Identifying codes help locate the fault to repare it. We focused on circulant graphs by embedding them on infinite grids.Then, the marking and the coloring games were studied : two player games were one player wants to build something (a proper coloration or a proper marking) and the other wants to prevent the first player from doing so. For the marking game we studied the evolution of the strategy when modifying the graph. For the coloring game we defined a new edge-wise decomposition of graphs and we defined a new strategy on this decomposition that improves known results on planar graphs.In the end, I studied pure breaking games : two players take turns to break a heap of tokens in a given number of non-empty heaps. We focused on winning strategies for the game starting with a unique heap on n tokens. These games seem, on first sight, to be all regular : we showed this is the case for some of them and we gave a test to study one game at a time. Only one of these games does not seem to be regular, its behavior remains a mystery.To sum up, I studied three bilateral problems that use different methods and have different purposes in combinatorics