Un graphe arête-colorié Gc est un graphe dont les arêtes sont coloriées par un ensemble de couleurs données. Un sous-graphe de Gc est dit proprement colorié s'il ne contient pas d'arêtes adjacentes de même couleur. Un graphe ou multigraphe c-arête-colorié Gc, est dit k-lié (respectivement k-arête-lié) si et seulement si quelque soient 2k sommets distincts de V(Gc), notés, x1 y1 , x2 y2 , ..., xk yk , il existe k chaînes élémentaires sommet-disjointes (respectivement arête-disjointes) proprement arête-coloriées, reliant x1 à y1 , x2 à y2 , ... , xk à yk .Un arbre couvrant propre d'un graphe Gc est un sous-graphe de Gc qui est un arbre couvrant proprement colorié.Un arbre couvrant faiblement colorié est une arborescence telle qu'il existe une chaîne proprement coloriée entre la racine et chaque sommet du graphe.Dans la première partie de cette thèse, nous donnons des conditions suffisantes pour qu'un graphe arête-colorié soit k-lié. C'est un problème classique en théorie des graphes, avec des applications multiples. Ainsi, nous avons établi entre autres les résultats suivants.A) Tout multigraphe 2-arête-colorié d'ordre n ≥ 242k tel que dc(Gc) ≥ n/2+k -1, est k-lié. B) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k et de taille m≥ cn(n-1)/2 - c(n-2k +1)+1 est k-lié.C) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k tel que dc(x) ≥ n/2 pour tout sommet x, est k-arête-lié.D) Tout multigraphe 2-arête-colorié d'ordre n ≥ 2k ≥ 10 et de taille m ≥ n2 -5n + 11 tel que dc(x) ≥ 1 pour tout sommet x, est k-arête-lié.Dans la seconde partie de cette thèse, deux autres problèmes classiques en théorie des graphes sont traités dans la version arête-coloriée. Il s'agit des arbres couvrants et des chaînes hamiltoniennes. Nous donnons ci-dessous quelques résultats.E) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n-k-1 + k +1, a un arbre couvrant propre.F) Tout graphe Gc connexe c-arête-colorié de degré rainbow rd(Gc)=k et d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n-k-1 + k +1, possède un arbre couvrant propre.G) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ ((k + j)2 + 3(k + j) - 2)/2 avec c ≥ ((n - k - j)(n - k - j - 1))/2 + 2 , où j(j -1)=k , possède un arbre couvrant faiblement colorié.H) Tout multigraphe Gc d'ordre n ≥ 14 et de taille m ≥ (n - 3)(n - 4) + 3n - 2 tel que rd(Gc) = 2, possède une chaîne hamiltonienne propre. I) Tout multigraphe c-arête-colorié d'ordre n ≠ 5, 7 et de taille m ≥ n2 - 3n + 4, possède une chaîne hamiltonienne propre.La plupart des résultats exposés, sont les meilleurs possibles relativement aux propriétés sur les conditions suffisantes.

.

Au cours de ces dernières décennies, le développement de Systèmes Mobiles de Cartographie, soutenu par un progrès technologique important, est devenu plus apparent. Il a été stimulé par le besoin grandissant de collecte d'informations géographiques précises sur l'environnement. Nous considérons, au sein de cette thèse, des solutions pour l'acquisition des nuages de points mobiles de qualité topographique (précision centimétrique). Il s'agit, dans cette tâche, de mettre au point des méthodes de qualification des données, et d'en améliorer sur les erreurs systématiques par des techniques d'étalonnage et de recalage adéquates.Nous décrivons une démarche innovante d'évaluation de l'exactitude et/ou de la précision des relevés laser mobiles. Celle-ci repose sur l'extraction et la comparaison des entités linéaires de la scène urbaine. La distance moyenne calculée entre les segments appariés, étant la distance modifiée de Hausdorff, sert à noter les nuages par rapport à des références existantes. Pour l'extraction des arêtes, nous proposons une méthode de détection d'intersections entre segments plans retrouvés via un algorithme de RANSAC enrichi d'une analyse de composantes connexes. Nous envisageons également une démarche de correction de relevés laser mobiles à travers un recalage rigide fondé, lui aussi, sur les éléments linéaires. Enfin, nous étudions la pertinence des segments pour en déduire les paramètres de l'étalonnage extrinsèque du système mobile. Nous testons nos méthodes sur des données simulées et des données réelles acquises dans le cadre du projet TerraMobilita.

Un graphe arête-colorié Gc est un graphe dont les arêtes sont coloriées par un ensemble de couleurs données. Un sous-graphe de Gc est dit proprement colorié s'il ne contient pas d'arêtes adjacentes de même couleur. Un graphe ou multigraphe c-arête-colorié Gc, est dit k-lié (respectivement k-arête-lié) si et seulement si quelque soient 2k sommets distincts de V(Gc), notés, x1 y1 , x2 y2 , ..., xk yk , il existe k chaînes élémentaires sommet-disjointes (respectivement arête-disjointes) proprement arête-coloriées, reliant x1 à y1 , x2 à y2 , ... , xk à yk .Un arbre couvrant propre d'un graphe Gc est un sous-graphe de Gc qui est un arbre couvrant proprement colorié.Un arbre couvrant faiblement colorié est une arborescence telle qu'il existe une chaîne proprement coloriée entre la racine et chaque sommet du graphe.Dans la première partie de cette thèse, nous donnons des conditions suffisantes pour qu'un graphe arête-colorié soit k-lié. C'est un problème classique en théorie des graphes, avec des applications multiples. Ainsi, nous avons établi entre autres les résultats suivants.A) Tout multigraphe 2-arête-colorié d'ordre n ≥ 242k tel que dc(Gc) ≥ n/2+k –1, est k-lié. B) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k et de taille m≥ cn(n–1)/2 – c(n–2k +1)+1 est k-lié.C) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k tel que dc(x) ≥ n/2 pour tout sommet x, est k-arête-lié.D) Tout multigraphe 2-arête-colorié d'ordre n ≥ 2k ≥ 10 et de taille m ≥ n2 –5n + 11 tel que dc(x) ≥ 1 pour tout sommet x, est k-arête-lié.Dans la seconde partie de cette thèse, deux autres problèmes classiques en théorie des graphes sont traités dans la version arête-coloriée. Il s'agit des arbres couvrants et des chaînes hamiltoniennes. Nous donnons ci-dessous quelques résultats.E) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n–k–1 + k +1, a un arbre couvrant propre.F) Tout graphe Gc connexe c-arête-colorié de degré rainbow rd(Gc)=k et d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n–k–1 + k +1, possède un arbre couvrant propre.G) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ ((k + j)2 + 3(k + j) – 2)/2 avec c ≥ ((n – k – j)(n – k – j – 1))/2 + 2 , où j(j –1)=k , possède un arbre couvrant faiblement colorié.H) Tout multigraphe Gc d'ordre n ≥ 14 et de taille m ≥ (n – 3)(n – 4) + 3n – 2 tel que rd(Gc) = 2, possède une chaîne hamiltonienne propre. I) Tout multigraphe c-arête-colorié d'ordre n ≠ 5, 7 et de taille m ≥ n2 – 3n + 4, possède une chaîne hamiltonienne propre.La plupart des résultats exposés, sont les meilleurs possibles relativement aux propriétés sur les conditions suffisantes. / A c-edge-colored graph Gc is a graph whose edges are colored by a given set of colors. A subgraph of Gc is proper if no two adjacent edges have the same color.A c-edge-colored graph or multigraph Gc is k-linked (respectively k-edge-linked) if for any 2k distinct vertices, say x1 y1 , x2 y2 , ..., xk yk , there exist k vertex-disjoint (respectively edge-disjoint) proper paths joining x1 to y1 , x2 to y2 , ... , xk to yk .A proper spanning tree of a graph Gc is a spanning tree such that any two adjacent edges differ in colors.A weak spanning tree is a spanning rooted tree such that there exists a proper path between the root and every vertex of the graph.In the first part of this thesis, we provide conditions which are sufficient for an edge-colored graph to be k-linked. It is a classic problem in graph theory , with many applications. So, we established among others the following results.A) Every 2-edge-colored multigraph of order n ≥ 242k such that dc(Gc) ≥ n/2+k –1, is k-linked.B) Every c-edge-colored multigraph of order n ≥ 2k and size m≥ cn(n–1)/2 – c(n–2k +1)+1 is k-linked.C) Every c-edge-colored multigraph of order n ≥ 2k is k-edge-linked if for each vertex x, dc(x) ≥ n/2.D) Every 2-edge-colored multigraph of order n ≥ 2k ≥ 10 and size m ≥ n2 – 5n + 11 is k-edge-linked if for each vertex x, dc(x) ≥ 1.In the second part of this thesis, two other classic problems in graph theory are treated in edge-colored version: spanning trees and hamiltonian paths. We give below some results.E) Every c-edge-colored simple k-connected graph of order n ≥ C²k+1 + k + 2 with c ≥ C²n–k–1 + k +1, has a proper spanning tree.F) Every c-edge-colored connected graph Gc of rainbow degree rd(Gc)=k and order n ≥ C²k+1 + k + 2 with c ≥ C²n–k–1 + k +1, has a proper spanning tree. G) Every c-edge-colored simple k-connected graph of order n ≥ ((k + j)2 + 3(k + j) – 2)/2 and c ≥ ((n – k – j)(n – k – j – 1))/2 + 2 , with j(j –1)=k , has a weak spanning tree.H) Every c-edge-colored multigraph Gc of order n ≥ 14 and size m ≥ (n – 3)(n – 4) + 3n – 2 such that rd(Gc) = 2, has a proper hamiltonian path.I) Every c-edge-colored multigraph of order n ≠ 5, 7 and size m ≥ n2 – 3n + 4, has a proper hamiltonian path.Most of the given results are the best possible with regard to the properties on the sufficient conditions.

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes. / An oriented graph is a directed graph with no cycle of length at most two. A homomorphism of an oriented graph to another oriented graph is an arc preserving vertex mapping. To push a vertex is to switch the direction of the arcs incident to it. An orientable graph is an equivalence class of oriented graph with respect to the push operation. An orientable graph [−→G] admits a homomorphism to an orientable graph [−→H] if an element of [−→G] admits a homomorphism to an element of [−→H]. A signified graph (G, Σ) is a graph whose edges are assigned either a positive sign or a negative sign, while Σ denotes the set of edges with negative signs assigned to them. A homomorphism of a signified graph to another signified graph is a vertex mapping such that the image of a positive edge is a positive edge and the image of a negative edge is a negative edge. A signed graph [G, Σ] admits a homomorphism to a signed graph [H, Λ] if an element of [G, Σ] admits a homomorphism to an element of [H, Λ]. The oriented chromatic number of an oriented graph −→G is the minimum order of an oriented graph −→H such that −→G admits a homomorphism to −→H. A set R of vertices of an oriented graph −→G is an oriented relative clique if no two vertices of R can have the same image under any homomorphism. The oriented relative clique number of an oriented graph −→G is the maximum order of an oriented relative clique of −→G. An oriented clique or an oclique is an oriented graph whose oriented chromatic number is equal to its order. The oriented absolute clique number of an oriented graph −→G is the maximum order of an oclique contained in −→G as a subgraph. The chromatic number, the relative chromatic number and the absolute chromatic number for orientable graphs, signified graphs and signed graphs are defined similarly. In this thesis we study the chromatic number, the relative clique number and the absolute clique number of the above mentioned four types of graphs. We specifically study these three parameters for the family of outerplanar graphs, of outerplanar graphs with given girth, of planar graphs and of planar graphs with given girth. We also try to investigate the relation between the four types of graphs and prove some results regarding that. In this thesis, we provide tight bounds for the absolute clique number of these families in all these four settings. We provide improved bounds for relative clique numbers for the same. For some of the cases we manage to provide improved bounds for the chromatic number as well. One of the most difficult results that we prove here is that the oriented absolute clique number of the family of planar graphs is at most 15. This result settles a conjecture made by Klostermeyer and MacGillivray in 2003. Using the same technique we manage to prove similar results for orientable planar graphs and signified planar graphs. We also prove that the signed chromatic number of triangle-free planar graphs is at most 25 using the discharging method. This also implies that the signified chromatic number of trianglefree planar graphs is at most 50 improving the previous upper bound. We also study the 2-dipath and oriented L(p, q)-labeling (labeling with a condition for distance one and two) for several families of planar graphs. It was not known if the categorical product of orientable graphs and of signed graphs exists. We prove both the existence and also provide formulas to construct them. Finally, we propose some conjectures and mention some future directions of works to conclude the thesis.

Au cours de ces dernières décennies, le développement de Systèmes Mobiles de Cartographie, soutenu par un progrès technologique important, est devenu plus apparent. Il a été stimulé par le besoin grandissant de collecte d'informations géographiques précises sur l'environnement. Nous considérons, au sein de cette thèse, des solutions pour l'acquisition des nuages de points mobiles de qualité topographique (précision centimétrique). Il s'agit, dans cette tâche, de mettre au point des méthodes de qualification des données, et d'en améliorer sur les erreurs systématiques par des techniques d'étalonnage et de recalage adéquates.Nous décrivons une démarche innovante d'évaluation de l'exactitude et/ou de la précision des relevés laser mobiles. Celle-ci repose sur l'extraction et la comparaison des entités linéaires de la scène urbaine. La distance moyenne calculée entre les segments appariés, étant la distance modifiée de Hausdorff, sert à noter les nuages par rapport à des références existantes. Pour l'extraction des arêtes, nous proposons une méthode de détection d'intersections entre segments plans retrouvés via un algorithme de RANSAC enrichi d'une analyse de composantes connexes. Nous envisageons également une démarche de correction de relevés laser mobiles à travers un recalage rigide fondé, lui aussi, sur les éléments linéaires. Enfin, nous étudions la pertinence des segments pour en déduire les paramètres de l'étalonnage extrinsèque du système mobile. Nous testons nos méthodes sur des données simulées et des données réelles acquises dans le cadre du projet TerraMobilita. / Over the past few decades, the development of land-based Mobile Mapping Systems (MMS), supported by significant technological progress, has become more prominent. It has been motivated by the growing need for precise geographic information about the environment. In this thesis, we consider approaches for the acquisition of mobile point clouds with topographic quality (centimeter-level accuracy). The aim is to develop techniques for data quality assessment and improvement. In particular, we eliminate the systematic errors inherent to an MMS data using appropriate calibration and registration methods.We describe a novel approach to assess the accuracy and/or the precision of mobile laser point clouds. It is based on the extraction and comparison of line features detected within the urban scene. The computed average distance between corresponding pairs of line segments, taking advantage of a modified Hausdorff distance, is used to evaluate the MMS data with respect to a reference data set. For edge extraction, we propose a method which relies on the intersections between planes modelled via the RANSAC algorithm refined by an analysis of connected components. We also consider an approach to correct point clouds using a line-based rigid registration method. Finally, we study the use of line segments for estimating the boresight angles of a land-based mobile mapping system. We apply our methods to synthetic data and to real data acquired as part of the TerraMobilita project.

L'objectif de ces travaux est la modélisation des efforts de coupe dans le cas de la superfinition à l'outil coupant du cuivre Cu-c2 par le biais de la démarche Couple-Arête-Matière. La prédiction des efforts permet d'adapter les conditions de coupe pour une opération d'usinage où de définir les spécifications des outils lors de leur conception. Le Couple-Arête-Matière repose sur la discrétisation d'arête et la mise en place sur chaque élément d'arête des efforts élémentaires fonctions de la géométrie et des conditions de coupe locales. Cette dépendance de la géométrie et de ces conditions de coupe est introduite par la mise en place d'un modèle d'efforts. Par sommation sur la longueur d'arête en prise, il est possible de déterminer les efforts globaux dans les repères liés à l'outil ou à la pièce. Cette étude vise le calcul de ces efforts au travers de trois modèles. Les deux premiers modèles développés sont de type phénoménologique et calculent les efforts à partir des paramètres opératoires courants tels que l'épaisseur coupée, la géométrie de l'outil et la qualité de l'arête. Le troisième modèle est analytique et basé sur les mécanismes de formation du copeau. Les efforts sont déterminés à partir des contributions des trois zones communément identifiées ; la zone de cisaillement primaire est caractérisée par une loi de comportement de type Norton-Hoff, les deuxième et troisième zones, respectivement en contact avec le copeau et la face en dépouille sont caractérisées par une distribution de contraintes. Les performances de ces trois modèles sont comparées via le Couple-Arête-Matière. Les données expérimentales sont obtenues à partir d'images réalisées en cours d'usinage par une caméra à haute résolution ainsi que par des mesures d'efforts en coupe orthogonale sur des disques et des tubes, permettant la mise en évidence de l'effet du diamètre de la pièce usinée sur la zone de contact en dépouille.

L'objet de cette thèse se rapporte principalement au problème de la transmission d'ondes spériques à travers une interface plane séparant deux milieux fluides, la source se trouvant dans le milieu de plus faible célérité. Sous certaines conditions, ce modèles physique simple présente un intérêt particulier dû à l'existence d'une onde de "surface", appelée onde latérale ou inhomogène.<br /> Dans un premier temps, nous avons traité le cas s'une source ponctuelle monochromatique à l'aide de méthodes asymptotiques, de façon à vérifier l'existence physique de cette contribution. Dans le cas du dioptre plan air-eau, nous avons pu séparer expérimentalement la contribution latérale de la contribution géométrique, et mettre en évidence le comportement et les propriétés de celles-ci. Le champ réfracté total fait alors apparaître des zones d'interférences en parfait accord avec l'étude théorique et numérique. La contribution latérale présentant un caractère "dispersif", montre l'intérêt dans le cas du régime transitoire, d'utiliser une méthode de type temps-échelle. <br /> La fonction de Green peut être décomposée de façon naturelle en trois contributions analogues à celles du régime harmonique. La transformée en ondelettes permet alors de calculer de façon exacte ces différentes contributions et d'en étudier leur comportement. L'orginalité des résultats obtenus est la mise en évidence à certaines échelles, de phénomènes transitoires très brefs (échos) qui permettent d'engager une discussion nouvelle de ce type de problème. Une expérimentation combinée à une analyse temps-échelle (ondelettes) a confirmé ces observations. <br /> Par analogie à la formule de reconstitution simple de la transformée en ondelettes inverse, nous avons pu élaborer, pour de grandes distances radiales, une formule de reconstruction de la dépendance temporelle du signal-source (problème inverse) à partir de la mesure de la pression transmise (jouant le rôle de "pseudo-coefficients d'ondelettes") sur les profondeurs. <br /> Enfin, l'application de cette transformation à un problème de rétrodiffusion acoustique par des coques sphériques élastiques (interface fluide/solide) a montré qu'il est possible d'accéder à certaines caractéristiques physiques de la cible.