Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1.

Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1. / In this thesis, we investigate the extraction of trees from edge-colored graphs. We focus on finding trees with properties based on coloring. Namely, we deal with proper and weak proper spanning trees, denoted PST and WST.- We show the optimization versions of these problems to be NP-hard in the general case of edge-colored graphs and we provide algorithms to find these trees in the case of edge-colored graphs without properly edge-colored cycles. We also provide some nonapproximability bounds.- We investigate the existence of a PST in the case of edge-colored graphs under certain conditions on the graph, both structural and related to the coloration. We consider sufficient conditions that guarantee the existence of a PST in edge-colored (not necessarily proper) graphs with any number of colors. The conditions we consider are combinations ofvarious parameters such as : total number of colors, number of vertices, connectivity and the number of incident edges of different colors to the vertices.- We then consider properly edge-colored Hamiltonian paths in the edge-colored multigraphs, which are relevant to our study since they are also PST. We establish sufficient conditions for a multigraph to contain a proper edge-colored Hamiltonian path, depending on several parameters such as the number of edges, the degree of edges, etc.- Since one of the sufficient conditions for the existence of proper spanning trees is connectivity, we prove several upper bounds for the smallest number of colors needed to color a graph such that it is k-proper-connected. We state several conjectures for general and bipartite graphs, and we prove them for k = 1.

.

.

Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$.

La théorie des graphes est considérée comme un vaste champ qui permet d'explorer différentes techniques de preuve des mathématiques discrètes. Ainsi, les différents problèmes traités dans cette théorie ont plein d'applications dans d'autres domaines scientifiques tels que l'informatique, la physique, la sociologie, la théorie des jeux, etc. Dans cette optique, nous proposons, dans cette thèse, de mettre l'accent sur trois problèmes de graphes, à savoir la multidécomposition de multigraphes, la [1, 2]-domination et le monitoring des arêtes. Ainsi, le fait d'explorer, dans ce travail de thèse, trois problèmes de graphes relativement distincts dans des classes de graphes différentes, nous a permis de développer plusieurs techniques de preuve ainsi qu'une multitude de façon d'aborder un problème. La première partie de cette thèse touche un aspect très important de la théorie des graphes, appelé la décomposition des graphes. Intuitivement, une décomposition en sous-graphe permet de représenter le graphe d'origine par un ensemble de copies du sous-graphe, où chaque arête du graphe initial appartient à une et une seule copie du sous-graphe. Dans cette partie, on s'intéresse plus particulièrement à la décomposition multiple d'un multigraphe complet en étoiles et cycles de même taille, c.à.d. générer à partir d'un multigraphe, plusieurs composantes disjointes (étoiles et cycles). Dans ce sens, des preuves formelles sont présentées pour déterminer les conditions nécessaires et suffisantes que doit avoir le multigraphe complet pour qu'une telle décomposition existe. Les deux autres parties de cette thèse, les parties les plus consistantes, abordent un problème suscitant beaucoup d'attention actuellement, qui est l'étude de la domination dans les graphes. Le problème original de domination consiste à trouver un ensemble de sommets (de taille minimum) dominant le reste des sommets d'un graphe. De nombreuses variantes d'intérêts à la fois théoriques et pratiques ont été proposées et étudiées dans la littérature. Dans cette partie de thèse et celle qui suit, nous nous sommes intéressés à deux variantes de domination. La première variante, appelée [i, j]-domination dans les graphes, a été introduite par Chellali et al. en 2013. En plus de ses propriétés de domination, la particularité de cette variante est que chaque sommet non dominant doit être adjacent à au moins i et au plus j sommets dominants. Plus particulièrement, nous nous somme intéresses à la [1, 2]-domination. Il convient de souligner qu'il a été démontré que le problème reste NP-complet. Dans ce sens, nous avons étudié ce paramètre dans des graphes particuliers, tels que les graphes de Petersen généralisés, ce qui rend ce problème tout aussi intéressant. Introduite par Watkins, cette famille de graphes possède un nombre de propriétés très intéressantes. D'ailleurs, plusieurs paramètres de graphes ont été étudiés sur cette classe de graphes de par sa structure qui est assez particulière. De plus, une étude de la [1, 2]-total domination sur cette classe de graphes est aussi menée dans cette thèse. La deuxième et dernière variante étudiée, aussi une variante de la domination, appelée monitoring des arêtes, a été introduite par Dong et al. en 2008. Elle consiste à trouver un ensemble de sommets qui surveille (domine) l'ensemble des arêtes dans un graphe sachant qu'un sommet surveille une arête s'il forme un triangle avec les deux extrémités de l'arête. Une arête peut être monitorée par un ou plusieurs sommets. Dans ce contexte, plusieurs variantes du monitoring des arêtes sont considérées dans cette partie à savoir monitoring des arêtes, monitoring uniforme des arêtes et monitoring pondéré des arêtes. L'essence de ce problème réside dans sa nature combinatoire ainsi que son domaine d'application, plus particulièrement dans les réseaux de capteurs sans fil. De plus, il a été prouvé que trouver un ensemble minimum pour ce problème est NP-difficile [etc....] / Graph theory is considered as a field exploring a large variety of proof techniques in discrete mathematics. Thus, the various problems treated in this theory have applications in a lot of other scientific fields such as computer science, physics, sociology, game theory, etc. In this thesis, three major problems are considered: the multidecomposition of multigraphs, the [1, 2]- domination and the edge monitoring. The fact that these three problems are of different nature allowed us to explore several proof techniques in this thesis. The first part of this thesis deals with a popular aspect of research in graph theory called graph decomposition. Intuitively, a decomposition into subgraphs allows us to describe the original graph with a set of copies of these subgraphs. In this part, we give a particular interest to the multidecomposition of a complete multigraph into edge disjoint stars and cycles. Thus, we investigate the problem of (Sk, Ck)-multidecomposition of the complete multigraph and give necessary and sufficient conditions for such a multidecomposition to exist. The second and third parts are the most important parts in terms of effort and spent time. They are devoted to problems related to domination in graphs. The original domination problem is to find a minimum set of vertices such that every vertex outside the dominating set is adjacent to at least one vertex from the dominating set. Many variants of theoretical and practical interest have been studied in the literature. The second studied problem is called the [i, j]-domination in graphs. This problem was introduced by Chellali et al. in 2013. In addition to the properties of domination, this variant has the particularity that each non-dominating vertex should be adjacent to at least i dominating vertices but also to at most j of them. We particularly focus on the [1, 2]-domination. It has been shown that the problem remains NP-complete. We are interested to study this problem on a particular graph namely the generalized Petersen graph. This graph was introduced by Watkins and has a lot of interesting properties. Moreover, several graph theoretical parameters have been studied on this graph class because of it unique structure. In addition, a study of the [1, 2]-total domination is also proposed at the end of this part. The last problem is a new variant called edge monitoring problem and was introduced by Dong et al. in 2008. It consists to find a set of vertices that monitors (dominates) the edge set of a graph such as a vertex monitors an edge if it forms a triangle with it i.e. it dominates both extremities of the edge. An edge can be monitored by one or more vertices. Three variants of the problem are considered in this part namely the edge monitoring, uniform edge monitoring and weighted edge monitoring. The essence of this problem lies on its combinatorial aspect and its range of applications in networks; especially wireless sensor networks. This problem is known to be NP-hard. Given the complexity of this kind of problems, we are first interested by a theoretical study: variants of the problem, bounds, characterizations, etc. We give more in depth studies of the problem for several graph classes

Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément, 1) Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$. 2) Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc. 3) Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux. 4) Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$. / In this thesis, we study different problems in edge-colored graphs and edge-colored multigraphs, such as proper connection, strong edge colorings, and proper hamiltonian paths and cycles. Finally, we improve the known $O(n^4)$ algorithm to decide the behavior of a graph under the biclique operator, by studying bicliques in graphs withoutfalse-twin vertices. In particular: 1) We first study the $k$-proper-connection number of graphs, this is, the minimum number of colors needed to color the edges of a graph such that between any pair of vertices there exist $k$ internally vertex-disjoint paths. We denote this number $pc_k(G)$. We prove several upper bounds for $pc_k(G)$. We state some conjectures for general and bipartite graphs, and we prove all of them for the case $k=1$. 2) Then, we study the existence of proper hamiltonian paths and proper hamiltonian cycles in edge-colored multigraphs. We establish sufficient conditions, depending on several parameters such as the number of edges, the rainbow degree, the connectivity, etc. 3) Later, we showthat the strong chromatic index is linear in the maximum degree for any $k$-degenerate graph where $k$ is fixed. As a corollary, our result leads to considerable improvement of the constants and also gives an easier and more efficient algorithm for this familly of graphs. Next, we consider outerplanar graphs. We give a formula to find exact strong chromatic index for bipartite outerplanar graphs. We also improve the upper bound for general outerplanar graphs from the $3\Delta-3$ bound. 4) Finally, we study bicliques in graphs without false-twin vertices and then we present an $O(n+m)$ algorithm to recognize convergent and divergent graphs improving the $O(n^4)$ known algorithm.

Le concept d'auto-stabilisation a été introduit par Dijkstra en 1973. Un système distribué est auto-stabilisant s'il peut démarrer de n'importe quelle configuration initiale et retrouver une configuration légitime en un temps fini par lui-même et sans aucune intervention extérieure. La convergence est également garantie lorsque le système est affecté par des fautes transitoires, ce qui en fait une approche élégante, non masquante, pour la tolérance aux pannes. L'auto-stabilisation a été étudiée dans divers domaines des systèmes distribués tels que les problèmes de synchronisation de l'horloge, de la communication et les protocoles de routage. Vu l'importance des paramètres de graphes notamment pour l'organisation et l'optimisation des communications dans les réseaux et les systèmes distribués, plusieurs algorithmes auto-stabilisants pour des paramètres de graphe ont été proposés dans la littérature, tels que les algorithmes autostabilisants permettant de trouver les ensembles dominants minimaux, coloration des graphes, couplage maximal et arbres de recouvrement. Dans cette perspective, nous proposons, dans cette thèse, des algorithmes distribués et autostabilisants pour certains problèmes de graphes bien connus, en particulier pour les décompositions de graphes et les ensembles dominants qui n'ont pas encore été abordés avec le concept de l'autostabilisation. Les quatre problèmes majeurs considérés dans cette thèse sont: partitionnement en triangles, décomposition en p-étoiles, Monitoring des arêtes, fort ensemble dominant et indépendant. Ainsi, le point commun entre ces problèmes, est qu'ils sont tous considérés comme des variantes des problèmes de domination et de couplage dans les graphes et leur traitement se fait d'une manière auto-stabilisante / The concept of self-stabilization was first introduced by Dijkstra in 1973. A distributed system is self-stabilizing if it can start from any possible configuration and converges to a desired configuration in finite time by itself without using any external intervention. Convergence is also guaranteed when the system is affected by transient faults. This makes self-stabilization an effective approach for non-masking fault-tolerance. The self-stabilization was studied in various fields in distributed systems such as the problems of clock synchronization, communication and routing protocols. Given the importance of graph parameters, especially for organization and communication of networks and distributed systems, several self-stabilizing algorithms for classic graph parameters have been developed in this direction, such as self-stabilizing algorithms for finding minimal dominating sets, coloring, maximal matching, spanning tree and so on. Thence, we propose in this thesis, distributed and self-stabilizing algorithms to some wellknown graphs problems, particularly for graph decompositions and dominating sets problems that have not yet been addressed in a view of self-stabilization. The four major problems considered in this thesis are: the partitioning into triangles, p-star decomposition, edge monitoring set and independent strong dominating set problems. The common point between these four problems is that they are considered as variants of dominating set and matching problems and all propositions deal with the self-stabilization paradigm

On suppose que S=Sg,n est un surface connexe orientable de type topologique fini, de genre g≥3 et n≥0 épointements. Dans les chapitres 1 et 2 on décrit l'ensemble principal d'une surface et prouve que en utilisant expansions rigides itérés, on peut créer suites croissantes d'ensembles finis qui sa réunion est le complexe des courbes de la surface C(S). Dans le 3ème chapitre on introduit l'ensemble rigide X(S) de Aramayona et Leininger et l'utilise pour montrer que la suite des chapitres précédents est eventuellement une suite d'ensembles rigides. On utilise cela pour prouver que si Si=Sgi,ni pour i=1,2 sont surfaces telles que k(S1)≥k(S2) et g1≥3, toute application qui préserve les arêtes de C(S1) dans C(S2) est induite par un homéomorphisme. Ceci est utilisé pour montrer un résultat similaire pour les homomorphismes de sous-groupes de Mod*(S1) dans Mod*(S2). Dans le 4ème chapitre on utilise les résultats précédents pour prouver que l'unique façon d'obtenir une application qui préserve les arêtes et qui est alternante du graphe de Hatcher-Thurston de S1, HT(S1), dans soi de S2, HT(S2) est en utilisant un homéomorphisme de S1 et puis piquer la surface n fois pour obtenir S2. Ceci implique que toute application qui préserve les arêtes et qui est alternante de HT(S) dans soi même et aussi tous les automorphismes de HT(S), sont induits par homéomorphismes. Dans le 5ème chapitre on montre que toute application super-injective du graphe des courbes qui ne sépare pas et courbes extérieures de S1, NO(S1), dans soi de S2, NO(S2), est induite par un homéomorphisme. Finalement, dans les conclusions on discute la signifiance des résultats et les façons possibles d'étendre leur. / Suppose S = Sg,n is an orientable connected surface of finite topological type, with genus g ≥ 3 and n ≥ 0 punctures. In the first two chapters we describe the principal set of a surface, and prove that through iterated rigid expansions we can create an increasing sequence of finite sets whose union in the curve complex of the surface C(S). In the third chapter we introduced Aramayona and Leininger's finite rigid set X(S) and use it to prove that the increasing sequence of the previous two chapters becomes an increasing sequence of finite rigid sets after, at most, the fifth iterated rigid expansion. We use this to prove that given S1 = Sg1,n1 and S2 = Sg2,n2 surfaces such that k(S1) ≥ k(S2) and g1 ≥ 3, any edge-preserving map from C(S1) to C(S2) is induced by a homeomorphism from S1 to S2. This is later used to prove a similar statement using homomorphisms from certain subgroups of Mod*(S1) to Mod*(S2). In the fourth chapter we use the previous results to prove that the only way to obtain an edge-preserving and alternating map from the Hatcher-Thurston graph of S1 = Sg,0, HT(S1), to the Hatcher-Thurston graph of S2 = Sg,n, HT(S2), is using a homeomorphism of S1 and then make n punctures to the surface to obtain S2. As a consequence, any edge-preserving and alternating self-map of HT(S) as well as any automorphism is induced by a homeomorphism. In the fifth chapter we prove that any superinjective map from the nonseparating and outer curve graph of S1, NO(S1), to that of S2, NO(S2), is induced by a homeomorphism assuming the same conditions as in the previous chapters. Finally, in the conclusions we discuss the meaning of these results and possible ways to expand them.

La détermination de la forme d'un obstacle élastique immergé dans un milieu fluide à partir de mesures du champ d'onde diffracté est un problème d'un vif intérêt dans de nombreux domaines tels que le sonar, l'exploration géophysique et l'imagerie médicale. A cause de son caractère non-linéaire et mal posé, ce problème inverse de l'obstacle (IOP) est très difficile à résoudre, particulièrement d'un point de vue numérique. De plus, son étude requiert la compréhension de la théorie du problème de diffraction direct (DP) associé, et la maîtrise des méthodes de résolution correspondantes. Le travail accompli ici se rapporte à l'analyse mathématique et numérique du DP élasto-acoustique et de l'IOP. En particulier, nous avons développé un code de simulation numérique performant pour la propagation des ondes associée à ce type de milieux, basé sur une méthode de type DG qui emploie des éléments finis d'ordre supérieur et des éléments courbes à l'interface afin de mieux représenter l'interaction fluide-structure, et nous l'appliquons à la reconstruction d'objets par la mise en oeuvre d'une méthode de Newton régularisée.