Dans ce mémoire, nous utiliserons l’approche de Pólya pour dénombrer et énumérer des graphes répondant à certaines conditions. Nous étendons ensuite ce résultat pour des graphes plus spécifiques comme des réseaux, et des réseaux de type "feed-forward". Finalement, nous supposons ensuite que deux sommets d’un graphe puissent être connectés ou non, et étant donné une probabilité de connexion donnée, nous étudions, en tant que variables aléatoires, certaines propriétés que l’on aimerait retrouver parmi ces graphes. Le but de ce mémoire est donc d’étendre la portée du théorème de Pólya afin de dénombrer efficacement plusieurs familles de graphes. Le chapitre 1 servira à l’étude de ce théorème, des rappels nécessaires et suffisants de la théorie des groupes jusqu’à la démonstration du théorème de Pólya. Le chapitre 2 nous permettra de voir la flexibilité du résultat primordial développé au chapitre précédent. Finalement, au chapitre 3, nous abordons une approche plus probabiliste du problème d’énumération de graphes. / In this memoir, we use Pólya approach to count and enumerate graphs under a set of conditions. We then extend the reach of this result for some particular types of graphs, namely networks and feed forward networks. Finally, given probabilistic constraints, e.g. two nodes are connected with probability p, we find the probability that a random graph meets those constraints. The objective of this memoir is thus to remind necessary and sufficient notions of group theory in order to state and prove Pólya Enumeration Theorem, an extremely efficient theorem as for counting objects. We then use this result throughout chapter 2 to enumerate many types of graphs. Chapter 3 is where we get more probabilistic.

Dans la pratique, énormément de problèmes concrets peuvent être modélisés par un graphe. Par exemple, une carte géographique est typiquement un graphe dans lequel on serait amener à chercher des chemins courts entre les villes, ou à passer par toutes les routes ou toutes les villes.... Cela explique pourquoi la théorie des graphes est certainement le domaine le plus populaire des mathématiques discrètes malgré son jeune âge....

Sur la base de recherches à caractère expérimental, nous revisitons et approfondissons le paradigme de la consistance cognitive. Contrairement à ce que prévoient les théories de la consistance, nous montrons que, non seulement les gens ne présentent pas systématiquement des structures cognitives consistantes, mais aussi qu’ils se défendent fort peu face à des « agressions » idéologiques induisant de l’inconsistance. Nous expliquons ces observations, par le fait que la consistance n’est une valeur cognitive que dans des univers de croyances dotés d’une pertinence minimale. Par ailleurs, l’étude de la consistance cognitive donne lieu à la comparaison du formalisme classique des graphes et d’un formalisme nouveau : le graphe des parentés. Ces deux derniers convergent sur les indices de consistance. Le graphe des parentés met en évidence deux nouveaux indices : l’assimilation et la disjonction. Leur analyse donne lieu à une interprétation psychologique. / Based on experimental research we reviewed and thoroughly examined the paradigm of cognitive consistency. In contrast with various consistence theory predictions, we showed that people are not systematically endowed with consistent cognitive structures and do not defend themselves very carefully against ideological “aggressions” inducing inconsistency. We explained these findings by the fact that consistency has a cognitive value only in self relevant fields. On the other hand, studies on cognitive consistency gave rise to comparisons between classical formalism of graphs and a new formalism one: the graph of relationships. Both graphs converge on consistency factors. The graph of relationships underlies two new factors: assimilation and disjunction. Their analysis gave rise to psychological interpretations.

Ce document présente une vue synthétique de mes travaux de recherche menés ces cinq dernières années, au sein du LaBRI.<br />Les activités de recherche d'un enseignant-chercheur ne s'inscrivent pas souvent dans un plan de recherche soigneusement pensé. Elles évoluent en fonction de multiples impondérables, dont notamment les rencontres avec d'autres chercheurs ou encore les opportunités ``stratégiques'' de financement. De ce fait, il n'est pas toujours facile de dégager un fil conducteur qui permette de regrouper un ensemble des résultats obtenus ``au fil de l'eau'' sans avoir recours à des raccourcis un peu ``artificiels''. <br /><br />Lorsque je me suis efforcé de dégager un point commun à mes travaux, je me suis aperçu que des objets mathématiques bien particuliers n'étaient jamais très loin de mes activités: les groupes cycliques finis. En creusant un peu plus cette perception, il m'est apparu que mes travaux accordent une place considérable à des graphes élémentaires associés aux groupes cycliques, dits graphes ou encore webs.<br /><br />Ce document est donc consacré à la mise en valeur des multiples facettes de ces graphes. ``Facettes'' est ici à double sens, puisqu'une partie conséquente de mes résultats est précisément dédiée à la détermination des facettes de certains polytopes associés aux graphes!<br /><br />Sur la forme, les preuves ont été omises afin d'alléger le texte, à l'exception de quelques preuves sélectionnées pour leur brièveté et pour la pertinence du résultat qu'elles procurent. Des hyperliens pointent vers la version anglaise des preuves manquantes, telles qu'elles figurent dans le recueil d'articles en annexe. Pour faciliter également la lecture, l'index à la fin de l'ouvrage redonne toutes les principales définitions.<br /><br />Sur le fond, ce document est structuré de la manière suivante.<br /><br />Le premier chapitre est consacré aux principaux résultats connus sur les graphes parfaits. Ceci permet de définir les objets mathématiques utilisés par la suite, et de rappeler l'extraordinaire richesse conceptuelle des graphes parfaits.<br /><br />Dans le second chapitre, nous abordons un raffinement de la coloration usuelles des graphes, appelé ``coloration circulaire''. Cette coloration est à l'origine d'une généralisation récente des graphes parfaits: les ``graphes circulaires-parfaits''. Nous étudions la possibilité d'une caractérisation analogue à celles des graphes parfaits, que ce soit par sous-graphes exclus ou bien polyédrale. <br /><br />Dans le troisième chapitre, nous nous intéressons à une généralisation naturelle des webs: ``les graphes quasi-adjoints''. Il s'agit d'une sous-famille des graphes sans griffe, et à ce titre, l'étude de leur polytope des stables est de première importance.<br /><br />Dans le quatrième chapitre, nous menons des investigations directes sur le polytope des stables des graphes sans griffe.<br /><br />La conclusion est donnée dans le dernier et cinquième chapitre, qui contient également une brève présentation de quelques résultats préliminaires quant au calcul en temps polynomial du nombre circulaire-chromatique des graphes circulaires-parfaits et au calcul du nombre de stabilité des graphes quasi-adjoints. Tout repose sur l'introduction d'un nouveau polytope construit à partir des webs ...

L'objectif visé dans ce travail consiste en la présentation du polynôme de Tutte, et ce à la manière de son idéateur, M. William Thomas Tutte. Nous dressons également un portrait de l'éventail des applications possibles de ce polynôme, notamment en théorie des graphes, en physique de la mécanique statistique, de même qu'en théorie des noeuds. À cet égard, nous faisons la démonstration que le polynôme de Tutte admet une spécialisation en terme de la fonction de partition d'un modèle de Potts, ainsi qu'en terme du polynôme de Jones d'un entrelacs alterné. Ce travail se conclut par une série de calculs sur les graphes 2-connexes et connexes, pour lesquels nous utilisons une équation fonctionnelle bien connue de la théorie des espèces, de même que des fonctions de poids bloc-multiplicatives. Ces calculs nous ont permis, entre autres, d'établir l'égalité entre le poids total des λ-flots à flux non nuls sur les graphes 2-connexes à quatre sommets et le nombre de marelles de longueur trois dans l'hypercube de dimension λ -1. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Polynôme de Tutte, Polynôme chromatique, Polynôme de flot, Polynôme de fiabilité, Polynôme de Jones, Entrelacs alterné, Fonction de partition, Modèle de Potts, Graphes 2-connexes.

Cette thèse s’intéresse à la résolution de problèmes d’optimisation combinatoires NP-difficiles en utilisant des méthodes de résolution approchées. Deux domaines d’application sont ciblés ici, d’une part la problématique générale du réseau de transport avec une variante portant plus précisément sur la planification des tournées avec une équipe de véhicules, d’autre part le problème de gestion de sessions en mode multicast dans un réseau de télécommunication, abordé ici du point de vue plus général du partitionnement dans un graphe biparti. Ces deux applications sont évidemment d’intérêt, tant du point de vue fondamental pour les méthodes de résolution qui doivent toujours progresser face à de nouveaux challenges, que du point de vue des retombées industrielles potentielles. La résolution de tels problèmes comporte généralement deux phases : dans un premier temps il s’agit de définir un ou plusieurs modèles mathématiques, de les comparer éventuellement pour choisir le plus efficace en fonction des outils de résolution disponibles; dans un deuxième temps il est possible d’utiliser un paradigme de résolution générique, comme par exemple un solveur de programmation linéaire, ou bien de spécialiser un algorithme en y incluant des heuristiques et connaissances spécifiques, afin d’optimiser sa performance. C’est dans cette deuxième démarche que se situe cette thèse, démarche souvent nécessaire lorsque les problèmes abordés deviennent complexes et/ou de grande taille et que l’on souhaite concevoir des algorithmes plus efficaces / This thesis focuses on solving combinatorial optimization problems NP-hard using approximate solving methods. Two practical application areas are targeted here, firstly the general problem of vehicule routing network with a variant specifically with planning tours with a vehicle team, on the other hand the multicast session management problem on a telecommunications network, addressed by the broader perspective of clustering in a bipartite graph. Both applications are obviously of interest both from the fundamental point of view for the resolution methods that must always progress facing new challenges, from the point of view of potential industrial benefits. The resolution of such problems usually has two phases: initially it comes to define one or more mathematical models to compare possibly to choose the most effective according to the available resolution tools; secondly it is possible to use a generic resolution paradigm, such as a linear programming solver, or specialize an algorithm by including specific heuristics and knowledge to optimize its performance. This thesis is in this second approach. This is often necessary when the problems addressed become complex and / or large and that we need to be designing more efficient algorithms

La science des réseaux est notamment à la recherche de modèles mathématiques capables de reproduire le comportement de systèmes complexes empiriques. Cependant, la représentation usuelle, le graphe, est parfois inadéquate étant donné sa limitation à encoder uniquement les relations par paires. De nombreux travaux récents suggèrent que l'utilisation de l'hypergraphe, une généralisation décrivant les interactions d'ordre supérieur (plus de deux composantes), permet d'expliquer des phénomènes auparavant incompris avec le graphe. Or, la structure de ces réseaux complexes est rarement ou difficilement observée directement. De fait, on mesure plutôt une quantité intermédiaire, comme la fréquence de chaque interaction, pour ensuite reconstruire la structure originale. Bien que de nombreuses méthodes de reconstruction de graphes aient été développées, peu d'approches permettent de retrouver les interactions d'ordre supérieur d'un système complexe. Dans ce mémoire, on développe une nouvelle approche de reconstruction pouvant déceler les interactions connectant trois noeuds parmi des observations dyadiques bruitées. Basée sur l'inférence bayésienne, cette méthode génère la distribution des hypergraphes les plus plausibles pour un jeu de données grâce à un algorithme de type Metropolis-Hastings-within-Gibbs, une méthode de Monte-Carlo par chaînes de Markov. En vue d'évaluer la pertinence d'un modèle d'interactions d'ordre supérieur pour des observations dyadiques, le modèle d'hypergraphe développé est comparé à un second modèle bayésien supposant que la structure sous-jacente est un graphe admettant deux types d'interactions par paires. Les résultats obtenus pour des hypergraphes synthétiques et empiriques indiquent que la corrélation intrinsèque à la projection d'interactions d'ordre supérieur améliore le processus de reconstruction lorsque les observations associées aux interactions dyadiques et triadiques sont semblables. / Network science is looking for mathematical models capable of reproducing the behavior of empirical complex systems. However, the usual representation, the graph, is sometimes inadequate given its limitation to encode only pairwise relationships. Many recent works suggest that the use of the hypergraph, a generalization describing higher-order interactions (more than two components), allows to explain phenomena previously not understood with graphs. However, the structure of these complex networks is seldom or hardly observed directly. Instead, we measure an intermediate quantity, such as the frequency of each interaction, and then reconstruct the original structure. Although many graph reconstruction methods have been developed, few approaches recover the higher-order interactions of a complex system. In this thesis, we develop a new reconstruction approach which detects interactions connecting three vertices among noisy dyadic observations. Based on Bayesian inference, this method generates the distribution of the most plausible hypergraphs for a dataset using a Metropolis-Hastings-within-Gibbs algorithm, a Markov chain Monte Carlo method. In order to evaluate the relevance of a higher-order interaction model for dyadic observations, the developed hypergraph model is compared to a second Bayesian model assuming that the underlying structure is a graph admitting two types of pairwise interactions. Results for synthetic and empirical hypergraphs indicate that the intrinsic correlation to the projection of higher-order interactions improves the reconstruction process when observations associated with dyadic and triadic interactions are similar.

Dans ce mémoire, nous allons nous intéresser aux graphes obtenus en considérant l'image inverse d'un polygone (en particulier d'un segment) dont les sommets sont les valeurs critiques d'un polynôme. Nous allons commencer par des rappels de notions préliminaires sur les polynômes complexes, la topologie algébrique et la théorie des espèces. Ensuite, nous allons voir le lien entre les arbres plans bicolorés et les polynômes de Shabat, qui sont des polynômes ayant au plus deux valeurs critiques, mis à part l'infini. Subséquemment, nous étudierons quelques notions portant sur les cactus. Finalement nous bouclerons le tout par une exploration, à l'aide du logiciel Maple, des concepts élaborés dans les chapitres précédents. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : point critique, valeur critique, revêtement, polynôme de Shabat, arbre plan bicoloré, cactus, constellation, fonction symétrique, espèce de structures, itération de Newton-Raphson.

Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats gurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons de coloration des graphes qui est l'un des domaines les plus étudiés de théorie des graphes. Nous considérons d'abord trois problèmes de coloration appelés coloration gloutone, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un probl ème de décision, appelé bon étiquetage de arêtes, dont la dé nition a été motivée par le problème d'affectation de longueurs d'onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d'optimisation des graphes appelé le nombre enveloppe (géodésique). La dé nition de ce paramètre est motivée par une extension aux graphes des notions d'ensembles et d'enveloppes convexes dans l'espace Euclidien. En n, nous présentons dans l'annexe d'autres travaux développées au cours de cette thèse, l'un sur les hypergraphes orientés Eulériens et Hamiltoniens et l'autre concernant les systèmes de stockage distribués.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.