On établit la dimension de l'enveloppe convexe des couplages maximums d'un graphe, avec un résultat sur le cas des couplages parfaits. On étudie le squelette des polytopes. On démontre que si chaque sommet du polytope peut être représenté par un vecteur à valeurs 0 ou 1 alors ce squelette est soit un hypercube soit Hamilton connexe. On considère le polyèdre associé au problème du voyageur de commerce. Une méthode de décomposition permet de décrire entièrement ce polyèdre dans un cas particulier. Pour une version dite graphique de ce problème, on donne un ensemble d'inéquations nécessaires a la description du polyèdre associé.

Dans cette thèse, nous étudions des problèmes d'identification des sommets dans les graphes. Identifier les sommets d'un graphe consiste à attribuer à chaque sommet un objet qui rend le sommet unique par rapport aux autres. Nous nous intéressons particulièrement aux codes identifiants : sous-ensembles de sommets d'un graphe, dominants, tels que le voisinage fermé de chaque sommet du graphe a une intersection unique avec l'ensemble. Les sommets du code identifiant peuvent être considérés comme des capteurs et chaque sommet du graphe comme un lieu possible pour une défaillance. Nous caractérisons tout d'abord l'ensemble des graphes pour lesquels tous les sommets sauf un sont nécessaires dans tout code identifiant. Le problème consistant à trouver un code identifiant optimal, c'est-'a-dire de taille minimale, étant NP-difficile, nous l'étudions sur quatre classes restreintes de graphes. Suivant les cas, nous pouvons résoudre complètement le problème (pour les graphes de Sierpinski), améliorer les bornes générales (pour les graphes d'intervalles, les graphes adjoints, la grille du roi) ou montrer que le problème reste difficile même restreint (pour les graphes adjoints). Nous considérons ensuite des variations autour des codes identifiants permettant plus de flexibilité pour les capteurs. Nous étudions par exemple des capteurs du plan capables de détecter des défaillances 'a un rayon connu avec une erreur tolérée. Nous donnons des constructions de tels codes et bornons leur taille pour des valeurs de rayons et d'erreurs fixés ou asymptotiques. Nous introduisons enfin la notion de coloration identifiante d'un graphe, permettant d'identifier les sommets d'un graphe avec les couleurs présentes dans son voisinage. Nous comparons cette coloration avec la coloration propre des graphes et donnons des bornes sur le nombre de couleurs nécessaires pour identifier un graphe, pour plusieurs classes de graphes.

Pour les systèmes de commande sous la forme de dx/dt = f (x, u), dans la littérature, les chercheurs s'intéressaient à la stabilisation de ce système de différentes manières : asymptotique, uniformément asymptotique, partielle, en temps fini, etc. Pour aboutir à ces résultats, les méthodes utilisées font appel aux techniques suivantes : Lyapunov, Lasalle, Barbalat, surface glissante, etc. Dans cette thèse, nous nous sommes intéressés à une autre fonctionnalité de la commande, dite commande répulsive stabilisante. Les résultats ont été généralisés au cas d'un système avec dérive et sans dérive. Comme résultat, l'approche de commande qu'on propose assure la stabilité du système autour d'une position désirée et la répulsion de celui-ci par rapport à un ensemble indésirable, construit dans l'espace de navigation. Toute forme d'application sera concernée par nos résultats théoriques, on peut citer, la navigation terrestre et aérienne dans un environnement peu ou pas connu. De même, la commande qu'on propose préserve la communication inter-agent, une fois planifiées. En terme d'application, on a considéré le modèle d'un véhicule à roues type unicycle, sans tenir compte de l'orientation (cas non holonôme) et dans le cas où l'environnement contient un ou plusieurs obstacle(s). Contrairement aux résultats de la littérature, qui sont basés sur une commande à structure variable pour l'évitement d'un obstacle, la commande répulsive-stabilisante trouvée est une commande continue sur l'espace de navigation. La deuxième partie de cette thèse traite le problème de stabilité d'une formation d'agents (système multi-véhicules) qui évolue dans un environnement hostile tout en préservant la communication entre les agents. Pour réussir la formation, la décentralisation de la commande par rapport aux agents est rendue robuste à travers des graphes de communication. Ces graphes relèvent de la stratégie et objectifs de la formation. Nos résultats de stabilité ont fait l'objet d'une implémentation rigoureuse sur un simulateur réalisé sous Matlab.

La visualisation d'information est une discipline récente en pleine expansion et qui a pour objet l'étude des méthodes de représentation visuelle de données abstraites, c'est-à-dire non géolocalisées. La sémiotique est quant à elle une discipline beaucoup plus ancienne (fin du XIXième siècle) qui s'intéresse aux divers systèmes de signes nécessaires aux processus de communication. A ce jour, peu de travaux ont été réalisés pour mettre en parallèle ces deux disciplines. C'est pourquoi le premier chapitre de cette thèse est dédié à l'étude de la visualisation d'information selon les paradigmes élaborés par son ainée tout au long du XXième siècle. Nous montrons en particulier comment l'un des modèles les plus aboutis de validation de visualisations (modèle imbriqué de Tamara Munzner) correspond au processus d'étude sémiotique d'énoncés. Le second chapitre est consacré à la visualisation de graphe, outil de modélisation puissant de divers ensembles de données abstraites. Nous proposons d'une part une application permettant de visualiser et de naviguer à travers les pages Internet retournées par un moteur de recherche et d'autre part un algorithme de visualisation de hiérarchies dynamiques sous forme de "cartes géographiques". Enfin, nous évoquons dans le troisième chapitre un autre outil de modélisation de données abstraites : les hypergraphes. Nous proposons des résultats théoriques concernant leur représentation et donnons une ébauche de solution permettant de les visualiser.

Cette thèse porte sur l'étude d'équations d'évolution sur certains groupes hyperboliques, en particulier, nous étudions l'équation de la chaleur, l'équation de Schrödinger et l'équation des ondes modifiée, d'abord sur les arbres homogènes, ensuite sur des graphes symétriques. Sur les arbres homogènes, nous montrons que, sous une hypothèse d'invariance de jauge, on a existence globale des solutions de l'équation de Schrödinger ainsi qu'un phénomène de 'scattering' pour des données arbitraires dans l'espace des fonctions de carré intégrable sans restriction sur le degré de la non-linéarité, contrairement au cas euclidien ou au cas hyperbolique. Nous généralisons ensuite ce résultat sur les graphes symétriques de degré (k − 1)(r − 1) sous la condition k < r. Un de nos principaux résultats sur les graphes symétriques est l'estimation du noyau de la chaleur associé au laplacien combinatoire. Pour finir, nous établissons une expression explicite des solutions de l'équation des ondes modifiée sur les graphes symétriques.

Les réseaux complexes, issus de relevés de terrain d'origines trèsvariées, en biologie, science de l'information ou sociologie,présentent une caractéristique remarquable dénommée structurecommunautaire. Des groupes, ou communautés, à l'intérieur duréseau, ont une cohésion interne forte et des liens entre eux plusfaibles. Sans connaissance a priori du nombre de communautés, ladifficulté réside dans la caractérisation d'un bon partitionnement encommunautés. La modularité est une mesure globale de qualité departitionnement très utilisée qui capture les contraintes de cohésioninterne forte et de liens externes faibles. Elle transforme le problèmede détection de communautés en problème d'optimisationNP-difficile. Elle souffre d'un défaut, la limite de résolution, qui tendà rendre indétectables les très petites communautés d'autant plusque le réseau est grand. L'algorithme le plus efficace pour optimiserla modularité, dit de Louvain, procède par fusion de communautés.Cette thèse s'attache à modifier cet algorithme pour qu'il réalisemajoritairement des fusions pertinentes, qui n'aggravent pas lalimite de résolution, en utilisant une condition de fusion. De plus, enl'associant à un algorithme mémétique, les partitions proposéessont très proches des partitions attendues pour des graphesgénérés par un modèle qui reproduit les caractéristiques desréseaux complexes. Enfin, cet algorithme mémétique réduitfortement l'inconsistance de solution, défaut de la modularité selonlequel deux partitions trouvées à partir d'un examen des noeudsdans un ordre aléatoire, pour le même graphe, peuvent êtrestructurellement très différentes, rendant leur interprétation délicate.

Ce document pr esente les travaux que j'ai r ealis es depuis ma th ese de doctorat. Outre la pr esentation de mes contributions, j'ai essay e de pr esenter des survols des domaines dans lesquels mes travaux s'inscrivent et d'indiquer les principales questions qui s'y posent. Mes travaux visent a r epondre aux nouveaux challenges algorithmiques que posent la croissance des r eseaux de telecommunications actuels ainsi que l'augmentation des donnees et du trafi c qui y circulent. Un moyen de faire face a la taille de ces probl emes est de s'aider de la structure particuliere des r eseaux. Pour cela, je m'attache a d e nir de nouvelles caract erisations des propri et es structurelles des graphes pour les calculer et les utiliser effi cacement a des fins algorithmiques. Autant que possible, je propose des algorithmes distribu es qui ne reposent que sur une connaissance locale/partielle des r eseaux. En particulier, j' etudie les jeux de poursuite - traitant de la capture d'une entit e mobile par une equipe d'autres agents - qui off rent un point de vue int eressant sur de nombreuses propri et es de graphes et, notamment, des d ecompositions de graphes. L'approche de ces jeux d'un point de vue agents mobiles permet aussi l' etude de mod eles de calcul distribu e. Le chapitre 1 est d edi e a l' etude de plusieurs variantes des jeux de gendarmes et voleur. Le chapitre 2 traite des decompositions de graphes et de leur relation avec les problemes d'encerclement dans les graphes. Le chapitre 3 se concentre sur les probl emes d'encerclement dans des contextes a la fois centralis e et distribu e. Finalement, le chapitre 4 traite de probl emes de routage dans diff erents contextes, ainsi que de mod eles de calcul distribu e.

Ce travail est consacré à l'étude de certaines propriétés spectrales des opérateurs de Schrödinger aléatoires. Il est divisé en deux parties : 1. Une étude de la localisation d'Anderson pour des systèmes multi-particules sur un graphe quantique. 2. Une formulation abstraite de quelques estimées de Wegner, suivie par une liste d'applications pour des modèles concrets. Au Chapitre 1 on essaie d'introduire les problèmes et les résultats de la thèse de façon élémentaire. La première partie occupe les chapitres 2 et 3. Le Chapitre 2 consiste essentiellement en notre article "Anderson Localization for a multi-particle quantum graph" [97] sur le sujet. Au Chapitre 3 on discute quelques propriétés supplémentaires du modèle, et on donne surtout des démonstrations alternatives de certains résultats du Chapitre 2. La deuxième partie occupe les chapitres 4 et 5. Le Chapitre 4 reproduit essentiellement notre article "Some abstract Wegner estimates with applications" [98]. Au Chapitre 5 on poursuit l'étude des estimées de Wegner, en donnant notamment quelques théorèmes abstraits supplémentaires dans la Section 5.2 et encore d'autres applications dans la Section 5.3. On conclut avec deux annexes A et B. Dans la première on expose de manière très détaillée les développements en fonctions propres généralisées. Dans l'Annexe B, on démontre quelques résultats classiques utilisés dans le texte.

Dans cette thèse nous étudions les transformées de Riesz et les espaces de Hardy associés à un opérateur sur un espace métrique mesuré. Ces deux sujets sont en lien avec des estimations du noyau de la chaleur associé à cet opérateur. Dans les Chapitres 1, 2 et 4, on étudie les transformées quasi de Riesz sur les variétés riemannienne et sur les graphes. Dans le Chapitre 1, on prouve que les quasi transformées de Riesz sont bornées dans Lp pour 1

Comme dans de nombreux autres domaines, la construction des applications en Informatique Ambiantes (IAm) se fait par réutilisation d'entités logicielles disponibles. Pour des raisons de conductivités, de pannes, de charge de batterie mais aussi de nombreuses autres, la disponibilité de ces entités est imprévisible ce qui implique que l'auto-adaptation dynamique des applications est une nécessité. Cela passe par la spécification en parallèle des adaptations par des experts de divers domaines. Ce parallélisme de construction, peut amener des problèmes d'interférences lors de la composition dynamique de plusieurs adaptations. Dans cette thèse, par l'utilisation de graphes, nous contribuons à la définition d'un cadre formel pour la détection et la résolution de ces interférences. L'assemblage des entités logicielles repose sur des connecteurs d'assemblage qui sont utilisés dans la spécification des adaptations. Des règles de réécriture de graphe permettront de résoudre les interférences détectées, cette résolution étant guidée par la connaissance de connecteurs définis. De plus, pour pouvoir étendre dynamiquement et automatiquement notre mécanisme de gestion des interférences, nous proposons la modélisation comportementale de ces connecteurs. Ceci permet de ne pas reposer sur une connaissance à priori des connecteurs et autorise par la même d'étendre dynamiquement l'ensemble des connecteurs disponibles pour la spécification des adaptations.