On présente tout d'abord une série d'essais de cisaillement direct 2D monotones et cycliques sur l'interface sable de Fontainebleau-plaque rugueuse et lisse, 'a contrainte normale constante (CNL) et à rigidité normale imposée (CNS). Le but de ces essais est de simuler la situation mécanique le long de pieux soumis à un grand nombre de cycles d'origine environnementale ou anthropique. Ces cycles (typiquement 10000) de faible amplitude (10'a 40 kPa en terme de contrainte de cisaillement) ne sont pas cens'es produire de rupture prématurée. Ces tests incluent une série de cycles d'amplitudes (successives) variées. Le problème de la perte de sable entre la boite et la plaque est trait'e avec attention. Nous avons interprété l'effet de la position du "centre des cycles" dans le plan de contraintes (variables cycliques moyennes) et de la densité initiale. Plusieurs facteurs tels que l'indice initial de densité (ID0), la contrainte normale cyclique moyenne (_n cm0), le niveau initial moyen de contrainte de cisaillement (_cm0), l'amplitude cyclique réduite (__) et la rigidité normale imposée (k qui dans cette thèse, va de 1000 'a 5000 kPa/mm), influencent les déplacements relatifs cycliques moyens normal ([u]cm) et tangentiel [w]cm) et sont pris en considération.On observe soit de la dilatance, soit de la contractance en accord avec l'état caractéristique développé par Luong. L'influence du chemin de contrainte (CNL ou CNS) est également analysée. Un modèle phénoménologique et analytique de comportement d'interface sur chemins cycliques CNL est propos'e. C'est également le cas pour le comportement monotone sur chemins oedométrique et CNL, la variable de mémoire unique étant la densité d'interface (sous contrainte) ou le déplacement relatif normal. Cette formulation permet de traiter, par incréments analytiques finis, les chemins comportant une variation d'amplitude cyclique, et les chemins CNS, ce qui introduit la notion de nombre de cycles équivalent. On notera que les chemins CNS sont toujours contractants. Ces essais sont utilisés pour aborder la simulation par éléments finis, avec le logiciel Plaxis, selon une approche de pseudo-viscoplasticité, le nombre de cycles tenant lieu de temps fictif. L'essai de cisaillement monotone'a la boite est modélisé en densités faible et forte, ainsi que deux essais de pieux modèles centrifugés, l'un en traction, l'autre en compression. Des recommandations sont proposées pour le calcul courant des pieux sous sollicitations cycliques. Cette thèse a été soutenue par l'ANR SOLCYP et le programme national " recherches sur le comportement des pieux soumis à des sollicitations cycliques".

Nous avons utilisé la décomposition par séparateurs minimaux complets. Pour décomposer un graphe G, il est nécessaire de trouver les séparateurs minimaux dans le graphe triangulé H correspondant. Dans ce contexte, nos premiers efforts se sont tournés vers la détection de séparateurs minimaux dans un graphe triangulé. Nous avons défini une structure, que nous avons nommée 'atom tree'. Cette dernière est inspirée du 'clique tree' et permet d'obtenir et de représenter les atomes qui sont les produits de la décomposition. Lors de la manipulation de données à l'aide de treillis de Galois, nous avons remarqué que la décomposition par séparateurs minimaux permettait une approche de type `Diviser pour régner' pour les treillis de Galois. La détection des gènes fusionnés, qui est une étape importante pour la compréhension de l'évolution des espèces, nous a permis d'appliquer nos algorithmes de détection de séparateurs minimaux complets, qui nous a permis de détecter et regrouper de manière efficace les gènes fusionnés. Une autre application biologique fut la détection de familles de gènes d'intérêts à partir de données de niveaux d'expression de gènes. La structure de `l'atom tree' nous a permis d'avoir un bon outils de visualisation et de gérer des volumes de données importantes. / We worked on clique minimal separator decomposition. In order to compute this decomposition on a graph G we need to compute the minimal separators of its triangulation H. In this context, the first efforts were on finding a clique minimal separators in a chordal graph. We defined a structure called atom tree inspired from the clique tree to compute and represent the final products of the decomposition, called atoms. The purpose of this thesis was to apply this technique on biological data. While we were manipulating this data using Galois lattices, we noticed that the clique minimal separator decomposition allows a divide and conquer approach on Galois lattices. One biological application of this thesis was the detection of fused genes which are important evolutionary events. Using algorithms we produced in the course of along our work we implemented a program called MosaicFinder that allows an efficient detection of this fusion event and their pooling. Another biological application was the extraction of genes of interest using expression level data. The atom tree structure allowed us to have a good visualization of the data and to be able to compute large datasets.

Cette thèse s'articule autour de la détection de similarités globales et locales dans les structures protéiques. Premièrement les structures sont comparées, mesurées en termes de distance métrique dans un but de classification supervisée. Cette classification des domaines structuraux au sein de classifications hiérarchiques se fait par le biais de dominances et d'apprentissages permettant d'assigner plus rapidement et de manière exacte de nouveaux domaines. Deuxièmement, nous proposons une méthode de manière de traduire un problème biologique dans les formalisme des graphes. Puis nous résolvons ce problème via le parcours de ces graphes pour extraire les différentes sous-structures similaires. Cette méthode repose sur des notions de compatibilités entre éléments des structures ainsi que des critères de distances entre éléments. Ces techniques sont capables de détecter des événements tels que des permutations circulaires, des charnières (flexibilité) et des répétitions de motifs structuraux. Finalement nous proposons une nouvelle approche dans l'analyse fine de structures afin de faciliter la recherche de régions divergentes entre structures 3D fortement similaires. / This thesis focusses on local and global similarities and divergences inside protein structures. First, structures are scored, with criteria of similarity and distance in order to provide a supervised classification. This structural domain classification inside existing hierarchical databases is possible by using dominances and learning. These methods allow to assign new domains with accuracy and exactly. Second we focusses on local similarities and proposed a method of protein comparison modelisation inside graphs. Graph traversal allows to find protein similar substructures. This method is based on compatibility between elements and criterion of distances. We can use it and detect events such that circular permutations, hinges and structural motif repeats. Finally we propose a new approach of accurate protein structure analysis that focused on divergences between similar structures.

Attention, ce résumé comporte un peu d'ironie et d'humour. Dans ce mémoire, nous défendons l'idée selon laquelle, pour tout modèle de calcul raisonnable, ce n'est plus tant le modèle qui compte pour caractériser les classes de complexité importantes que la complexité de la structure combinatoire sous-jacente et en définitive d'un graphe sous-jacent. Pour prendre l'exemple des circuits booléens ou algébriques comme modèles, tout ce qui importe est la complexité du graphe orienté sous-jacent au circuit. Par modèle de calcul raisonnable, nous entendons, comme il se doit, un modèle qui étudié sur une classe de graphes standard nous donne la classe de complexité standard attendue afin de satisfaire aux règles élémentaires des tautologies. On pourrait aussi choisir comme modèles raisonnables les modèles Turing-complet (ou une autre notion de complétude plus adaptée selon les objets calculés), formalisables dans une logique simple (afin d'éviter les "tricheries" et les modèles conçus spécialement pour faire échouer la belle idée défendue). Néanmoins, cette seconde option n'étant pas sans risque, nous nous contentons de la proposer. La thèse défendue est une version un peu plus formalisée et précise mathématiquement de cette idée aux contours un peu flous et qui est donc nécessairement un peu fausse telle quelle.

On présente tout d’abord une série d’essais de cisaillement direct 2D monotones et cycliques sur l’interface sable de Fontainebleau-plaque rugueuse et lisse, `a contrainte normale constante (CNL) et à rigidité normale imposée (CNS). Le but de ces essais est de simuler la situation mécanique le long de pieux soumis à un grand nombre de cycles d’origine environnementale ou anthropique. Ces cycles (typiquement 10000) de faible amplitude (10`a 40 kPa en terme de contrainte de cisaillement) ne sont pas cens´es produire de rupture prématurée. Ces tests incluent une série de cycles d’amplitudes (successives) variées. Le problème de la perte de sable entre la boite et la plaque est trait´e avec attention. Nous avons interprété l’effet de la position du ”centre des cycles” dans le plan de contraintes (variables cycliques moyennes) et de la densité initiale. Plusieurs facteurs tels que l’indice initial de densité (ID0), la contrainte normale cyclique moyenne (_n cm0), le niveau initial moyen de contrainte de cisaillement (_cm0), l’amplitude cyclique réduite (__) et la rigidité normale imposée (k qui dans cette thèse, va de 1000 `a 5000 kPa/mm), influencent les déplacements relatifs cycliques moyens normal ([u]cm) et tangentiel [w]cm) et sont pris en considération.On observe soit de la dilatance, soit de la contractance en accord avec l’état caractéristique développé par Luong. L’influence du chemin de contrainte (CNL ou CNS) est également analysée. Un modèle phénoménologique et analytique de comportement d’interface sur chemins cycliques CNL est propos´e. C’est également le cas pour le comportement monotone sur chemins oedométrique et CNL, la variable de mémoire unique étant la densité d’interface (sous contrainte) ou le déplacement relatif normal. Cette formulation permet de traiter, par incréments analytiques finis, les chemins comportant une variation d’amplitude cyclique, et les chemins CNS, ce qui introduit la notion de nombre de cycles équivalent. On notera que les chemins CNS sont toujours contractants. Ces essais sont utilisés pour aborder la simulation par éléments finis, avec le logiciel Plaxis, selon une approche de pseudo-viscoplasticité, le nombre de cycles tenant lieu de temps fictif. L’essai de cisaillement monotone`a la boite est modélisé en densités faible et forte, ainsi que deux essais de pieux modèles centrifugés, l’un en traction, l’autre en compression. Des recommandations sont proposées pour le calcul courant des pieux sous sollicitations cycliques. Cette thèse a été soutenue par l’ANR SOLCYP et le programme national ” recherches sur le comportement des pieux soumis à des sollicitations cycliques”. / A series of monotonic and cyclic 2D direct shear tests on sand (Fontainebleau)-rough/smoothmaterial interfaces under constant normal load (CNL) and constant normal stiffness (CNS)conditions are presented. The aim of these tests is to simulate the situation along the shaftof piles subjected to a large number of cycles due to environmental or anthropic loadings.These cycles (typically 104) are of small amplitude (10, 20 and 40 kPa in terms of shearstress) as the service loads are not supposed to produce an early failure. These tests in-clude the series of changing the cyclic amplitude in succession. The problem of loss of sandbetween the box and the rough plate, typical phenomenon in this type of test, receives aspecial attention. It is interesting to observe, according to the initial density, the positionof the ”center of cycles” in the stress plane (mean cyclic variables). Several factors such asinitial density (ID0), initial normal stress (_n cm0), level of initial mean cyclic stress ratio(_cm0), reduced cyclic amplitude (__) and imposed normal stiffness (in this thesis, k =1000, 2000 and 5000 kPa/mm) that influence the intensity of mean cyclic normal ([u]cm)and shear ([w]cm) displacements are considered. Along CNL paths either dilation or con-traction is exhibited, in agreement with the characteristic state developed by Luong. Theinfluence of the stress path (under constant normal stress or prescribed normal stiffness)is also highlighted. It should be highlighted that CNS paths are ever contractive. Themodel of monotonic interface behaviour under CNL and oedometer paths is fully analyt-ical and based on the rate-type framework with the normal relative displacement or theinterface density as unique memory parameter. While the analytical formulations for iden-tification are first proposed to describe the interface behaviour under cyclic CNL condition,the variation of cyclic amplitude and CNS condition are modeled by applying the analyticalformulations for validation using finite analytical increments and introducing the notion ofequivalent number of cycles. For numerical simulations by the FEM (Plaxis) these tests areinterpreted and formulated according to a pseudo visco-plastic framework, the number ofcycles being a fictitious time. The direct shear tests and two centrifuge pile tests (pull-outand compression) are also modeled. Recommendations are proposed for the calculation ofreal usual piles under cyclic loading. This thesis is one part of the national French project”ANR and National Program SOLCYP” (Research on behaviour of piles subjected to cyclicloading).

No description available.

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs. Cette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité. Le deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: Si G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G. La meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G) <= 3/2 n pour une classe de graphes la plus large possible. Un autre résultat associé à ce problème apporte la preuve de la conjecture pour une classe particulière de graphes: Soit G un graphe simple avec alpha(G) = 2. Si G a une arête dominante uv telle que G \ {u,v} est de diamètre 3, alors ecc(G) <= n. Le troisième problème étudie le jeu de policier et voleur sur un graphe. Presque toutes les études concernent les graphes statiques, et nous souhaitons explorer ce jeu sur les graphes dynamiques, dont les ensembles d’arêtes changent au cours du temps. Nowakowski et Winkler caractérisent les graphes statiques pour lesquels un unique policier peut toujours attraper le voleur, appellés cop-win, à l’aide d’une relation <= définie sur les sommets de ce graphe: Un graphe G est cop-win si et seulement si la relation <= définie sur ses sommets est triviale. Nous adaptons ce théorème aux graphes dynamiques. Notre démarche nous mène à une relation nous permettant de présenter une caractérisation des graphes dynamiques cop-win. Nous donnons ensuite des résultats plus spécifiques aux graphes périodiques. Nous indiquons aussi comment généraliser nos résultats pour k policiers et l voleurs en réduisant ce cas à celui d’un policier unique et un voleur unique. Un algorithme pour décider si, sur un graphe périodique donné, k policiers peuvent capturer l voleurs découle de notre caractérisation. / This thesis represents in three articles my eclectic interest for graph theory. The first problem is the conjecture of Erdos-Faber-Lovász: If k complete graphs, each having k vertices, have the property that every pair of distinct complete graphs have at most one vertex in common, then the vertices of the resulting graph can be properly coloured by using k colours. This conjecture is notable in that only a handful of classes of EFL graphs are proved to satisfy the conjecture. We prove that the Erdos-Faber-Lovász Conjecture holds for a new class of graphs, and we do so by an inductive argument. Furthermore, graphs in this class have no restrictions on the number of complete graphs to which a vertex belongs or on the number of vertices of a certain type that a complete graph must contain. The second problem addresses a conjecture concerning the covering of the edges of a graph: The minimal number of cliques necessary to cover all the edges of a simple graph G is denoted by ecc(G). If alpha(G) = 2, then ecc(G) <= n. The best known bound satisfied by ecc(G) for all the graphs with independence number two is the minimum of n + delta(G) and 2n − omega(square root (n log n)), where delta(G) is the smallest number of neighbours of a vertex in G. In this type of graph, all the vertices at distance two from a given vertex form a clique. Our approach is to extend all of these n cliques in order to cover the maximum possible number of edges. Unfortunately, there are graphs for which it’s impossible to cover all the edges with this method. However, we are able to use this approach to prove a bound of ecc(G) <= 3/2n for some newly studied infinite families of graphs. The third problem addresses the game of Cops and Robbers on a graph. Almost all the articles concern static graphs, and we would like to explore this game on dynamic graphs, the edge sets of which change as a function of time. Nowakowski and Winkler characterize static graphs for which a cop can always catch the robber, called cop-win graphs, by means of a relation <= defined on the vertices of such graphs: A graph G is cop-win if and only if the relation <= defined on its vertices is trivial. We adapt this theorem to dynamic graphs. Our approach leads to a relation, that allows us to present a characterization of cop-win dynamic graphs. We will then give more specific results for periodic graphs, and we will also indicate how to generalize our results to k cops and l robbers by reducing this case to one with a single cop and a single robber. An algorithm to decide whether on a given periodic graph k cops can catch l robbers follows from our characterization.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.