Nous étudions les poids de graphes (c'est-à-dire, les invariants de graphes) qui apparaissent naturellement dans la théorie de Mayer et la théorie de Ree-Hoover pour le développement du viriel dans le contexte d'un gaz imparfait. Nous portons une attention particulière au deuxième poids ωM(C) de Mayer et au poids ωRH(C) de Ree-Hoover d'un graphe 2-connexe c dans le cas d'un gaz à noyaux durs et à positions continues en une dimension. Ces poids sont calculés à partir de volumes signés de polytopes convexes associés au graphe c en utilisant la méthode des homomorphismes de graphes, que nous avons aussi adaptée au cas du poids de Ree-Hoover, ainsi que les transformées de Fourier. En faisant appel à l'inversion de Möbius, nous présentons des relations entre les poids de Mayer et de Ree-Hoover. Ces relations nous permettent de donner une définition simple explicite du concept du "star content" introduit par Ree-Hoover et d'analyser certaines de ses propriétés fondamentales. Parmi nos résultats, nous donnons des tables contenant les valeurs du poids de Mayer et du poids de Ree-Hoover pour tous les graphes 2-connexes de taille au plus 8 ainsi que d'autres paramètres descriptifs. Nous développons aussi des formules explicites pour les poids de Mayer et de Ree-Hoover pour certaines familles de graphes 2-connexes simplement, doublement et triplement infinies, incluant par exemple, le poids de Mayer des graphes bipartis complets K m,n. En analysant les tables précédentes à l'aide du logiciel Maple, nous montrons que les poids de Mayer et de Ree-Hoover ne sont pas exprimables comme des fonctions faisant seulement appel à certains paramètres classiques de la théorie des graphes. Finalement, nous présentons une méthode générale pour le calcul du poids de Mayer d'un graphe connexe quelconque basée sur les arborescences couvrantes en utilisant les transformées de Fourier. Nous illustrons cette méthode sur des cas particuliers incluant les particules dures en dimension quelconque d. Cette méthode donne aussi lieu à un algorithme de calcul basé sur les différences divisées pour le cas des particules dures en dimension d = 1. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Poids de Mayer, Poids de Ree-Hoover, Mécanique statistique, Méthode des homomorphismes de graphes, Transformées de Fourier, Gaz imparfaits.

Daniel Kan associe a tout ensemble simplicial réduit x un fibre principal contractile de base x et de fibre un groupe simplicial libre, note gx. Un concept généralisé de prisme nous permet de considérer ce groupe comme sous-quotient canonique d'un modèle simplicial de l'espace de lacets de x, et de munir l'espace total du fibre d'une contraction combinatoire évoquant l'idée topologique de contraction des chemins. Est ainsi établie une correspondance biunivoque explicite entre les représentants algébriques des classes d'homotopie de Gx et certains représentants géométriques des classes d'homotopie de x. En utilisant les propriétés homotopiques du commutant de Gx nous obtenons enfin une version effective du théorème de Hurewicz comportant entre autres la construction algorithmique de sphères combinatoires a partir de certains cycles homologique

Un graphe mixte est un graphe simple tel que un sous-ensemble des arêtes a une orientation. Pour entiers non négatifs j et k, un graphe mixte-(j,k) est un graphe mixte avec j types des arcs and k types des arêtes. La famille de graphes mixte-(j,k) contient graphes simple, (graphes mixte−(0,1)), graphes orienté (graphes mixte−(1,0)) and graphe coloré arête −k (graphes mixte−(0,k)).Un homomorphisme est un application sommet entre graphes mixte−(j,k) que tel les types des arêtes sont conservés et les types des arcs et leurs directions sont conservés. Le nombre chromatique−(j,k) d’un graphe mixte−(j,k) est le moins entier m tel qu’il existe un homomorphisme à une cible avec m sommets. Quand on observe le cas de (j,k) = (0,1), on peut déterminer ces définitions correspondent à les définitions usuel pour les graphes.Dans ce mémoire on etude le nombre chromatique−(j,k) et des paramètres similaires pour diverses familles des graphes. Aussi on etude les coloration incidence pour graphes and digraphs. On utilise systèmes de représentants distincts et donne une nouvelle caractérisation du nombre chromatique incidence. On define le nombre chromatique incidence orienté et trouves un connexion entre le nombre chromatique incidence orienté et le nombre chromatic du graphe sous-jacent. / A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j,k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j,k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)−mixed graphs) and k−edge- coloured graphs ((0,k)−mixed graphs).A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. The (j,k)−chromatic number of a (j,k)−mixed graph is the least m such that an m−colouring exists. When (j,k)=(0,1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring.In this thesis we study the (j,k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1,0)−chromatic number, more commonly called the oriented chromatic number, and the (0,k)−chromatic number.In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.

Dans cette thèse, nous etudions deux principaux problèmes de la théorie des graphes: problème d’homomorphisme des graphes planaires (signés) et problème de cycle hamiltonien.Comme une extension du théorème des quatre couleurs, il est conjecturé([80], [41]) que chaque graphe signé cohérent planaire de déséquilibré-maille d+1(d>1) admet un homomorphisme à cube projective signé SPC(d) de dimension d. La question suivant étalés naturelle:Est-ce que SPC(d) une borne optimale de déséquilibré-maille d+1 pour tous les graphes signés cohérente planaire de déséquilibré-maille d+1?Au Chapitre 2, nous prouvons que: si (B,Ω) est un graphe signé cohérente dedéséquilibré-maille d qui borne la classe des graphes signés cohérents planaires de déséquilibré-maille d+1, puis |B| ≥2^{d−1}. Notre résultat montre que si la conjecture ci-dessus est vérifiée, alors le SPC(d) est une borne optimale à la fois en terme du nombre des sommets et du nombre de arêtes.Lorsque d=2k, le problème est équivalent aux problème des graphes:est-ce que PC(2k) une borne optimale de impair-maille 2k+1 pour P_{2k+1} (tous les graphes planaires de impair-maille au moins 2k+1)? Notez que les graphes K_4-mineur libres sont les graphes planaires, est PC(2k) aussi une borne optimale de impair-maille 2k+1 pour tous les graphes K_4-mineur libres de impair-maille 2k+1? La réponse est négative, dans[6], est donné une famille de graphes d’ordre O(k^2) que borne les graphes K_4-mineur libres de impair-maille 2k+1. Est-ce que la borne optimale? Au Chapitre 3, nous prouvons que: si B est un graphe de impair-maille 2k+1 qui borne tous les graphes K_4-mineur libres de impair-maille 2k+1, alors |B|≥(k+1)(k+2)/2. La conjonction de nos résultat et le résultat dans [6] montre que l’ordre O(k^2) est optimal. En outre, si PC(2k) borne P_{2k+1}, PC(2k) borne également P_{2r+1}(r>k).Cependant, dans ce cas, nous croyons qu’un sous-graphe propre de P(2k) serait suffisant à borner P_{2r+1}, alors quel est le sous-graphe optimal de PC2k) qui borne P_{2r+1}? Le premier cas non résolu est k=3 et r= 5. Dans ce cas, Naserasr [81] a conjecturé que le graphe Coxeter borne P_{11}. Au Chapitre 4, nous vérifions cette conjecture pour P_{17}.Au Chapitres 5, 6, nous étudions les problèmes du cycle hamiltonien. Dirac amontré en 1952 que chaque graphe d’ordre n est hamiltonien si tout sommet a un degré au moins n/2. Depuis, de nombreux résultats généralisant le théorème de Dirac sur les degré ont été obtenus. Une approche consiste à construire un cycle hamiltonien à partir d'un ensemble de sommets en contrôlant leur position sur le cycle. Dans cette thèse, nous considérons deux conjectures connexes. La première est la conjecture d'Enomoto: si G est un graphe d’ordre n≥3 et δ(G)≥n/2+1, pour toute paire de sommets x,y dans G, il y a un cycle hamiltonien C de G tel que dist_C(x,y)=n/2.Notez que l’ ́etat de degre de la conjecture de Enomoto est forte. Motivé par cette conjecture, il a prouvé, dans [32], qu’une paire de sommets peut être posé des distances pas plus de n/6 sur un cycle hamiltonien. Dans [33], les cas δ(G)≥(n+k)/2 sont considérés, il a prouvé qu’une paire de sommets à une distance entre 2 à k peut être posé sur un cycle hamiltonien. En outre, Faudree et Li ont proposé une conjecture plus générale: si G est un graphe d’ordre n≥3 et δ(G)≥n/2+1, pour toute paire de sommets x,y dans G et tout entier 2≤k≤n/2, il existe un cycle hamiltonien C de G tel que dist_C(x,y)=k. Utilisant de Regularity Lemma et Blow-up Lemma, au chapitre 5, nous donnons une preuve de la conjeture d'Enomoto conjecture pour les graphes suffisamment grand, et dans le chapitre 6, nous donnons une preuve de la conjecture de Faudree et Li pour les graphe suffisamment grand. / In this thesis, we study two main problems in graph theory: homomorphism problem of planar (signed) graphs and Hamiltonian cycle problem.As an extension of the Four-Color Theorem, it is conjectured ([80],[41]) that every planar consistent signed graph of unbalanced-girth d+1(d>1) admits a homomorphism to signed projective cube SPC(d) of dimension d. It is naturally asked that:Is SPC(d) an optimal bound of unbalanced-girth d+1 for all planar consistent signed graphs of unbalanced-girth d+1?In Chapter 2, we prove that: if (B,Ω) is a consistent signed graph of unbalanced-girth d which bounds the class of consistent signed planar graphs of unbalanced-girth d, then |B|≥2^{d-1}. Furthermore,if no subgraph of (B,Ω) bounds the same class, δ(B)≥d, and therefore,|E(B)|≥d·2^{d-2}.Our result shows that if the conjecture above holds, then the SPC(d) is an optimal bound both in terms of number of vertices and number of edges.When d=2k, the problem is equivalent to the homomorphisms of graphs: isPC(2k) an optimal bound of odd-girth 2k+1 for P_{2k+1}(the class of all planar graphs of odd-girth at least 2k+1)? Note that K_4-minor free graphs are planar graphs, is PC(2k) also an optimal bound of odd-girth 2k+1 for all K_4-minor free graphs of odd-girth 2k+1 ? The answer is negative, in [6], a family of graphs of order O(k^2) bounding the K_4-minor free graphs of odd-girth 2k+1 were given. Is this an optimal bound? In Chapter 3, we prove that: if B is a graph of odd-girth 2k+1 which bounds all the K_4-minor free graphs of odd-girth 2k+1,then |B|≥(k+1)(k+2)/2. Our result together with the result in [6] shows that order O(k^2) is optimal.Furthermore, if PC(2k) bounds P_{2k+1},then PC(2k) also bounds P_{2r+1}(r>k). However, in this case we believe that a proper subgraph of PC(2k) would suffice to bound P_{2r+1}, then what’s the optimal subgraph of PC(2k) that bounds P_{2r+1}? The first case of this problem which is not studied is k=3 and r=5. For this case, Naserasr [81] conjectured that the Coxeter graph bounds P_{11} . Supporting this conjecture, in Chapter 4, we prove that the Coxeter graph bounds P_{17}.In Chapter 5,6, we study the Hamiltonian cycle problems. Dirac showed in 1952that every graph of order n is Hamiltonian if any vertex is of degree at least n/2. This result started a new approach to develop sufficient conditions on degrees for a graph to be Hamiltonian. Many results have been obtained in generalization of Dirac’s theorem. In the results to strengthen Dirac’s theorem, there is an interesting research area: to control the placement of a set of vertices on a Hamiltonian cycle such that thesevertices have some certain distances among them on the Hamiltonian cycle.In this thesis, we consider two related conjectures, one is given by Enomoto: if G is a graph of order n≥3, and δ(G)≥n/2+1, then for any pair of vertices x, y in G, there is a Hamiltonian cycle C of G such that dist_C(x, y)=n/2. Motivated by this conjecture, it is proved,in [32],that a pair of vertices are located at distances no more than n/6 on a Hamiltonian cycle. In [33], the cases δ(G) ≥(n+k)/2 are considered, it is proved that a pair of vertices can be located at any given distance from 2 to k on a Hamiltonian cycle. Moreover, Faudree and Li proposed a more general conjecture: if G is a graph of order n≥3, and δ(G)≥n/2+1, then for any pair of vertices x, y in G andany integer 2≤k≤n/2, there is a Hamiltonian cycle C of G such that dist_C(x, y) = k. Using Regularity Lemma and Blow-up Lemma, in Chapter 5, we give a proof ofEnomoto’s conjecture for graphs of sufficiently large order, and in Chapter 6, we give a proof of Faudree and Li’s conjecture for graphs of sufficiently large order.

.

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2. / Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem. At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed. Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

RDF est un langage de représentation des connaissances dédié à l'annotation des ressources dans le Web Sémantique. Bien que RDF peut être lui-même utilisé comme un langage de requêtes pour interroger une base de connaissances RDF (utilisant la conséquence RDF), la nécessité d'ajouter plus d'expressivité dans les requêtes a conduit à définir le langage de requêtes SPARQL. Les requêtes SPARQL sont définies à partir des patrons de graphes qui sont fondamentalement des graphes RDF avec des variables. Les requêtes SPARQL restent limitées car elles ne permettent pas d'exprimer des requêtes avec une séquence non-bornée de relations (par exemple, Existe-t-il un itinéraire d'une ville A à une ville B qui n'utilise que les trains ou les bus?"). Nous montrons qu'il est possible d'étendre la syntaxe et la sémantique de RDF, définissant le langage PRDF (pour Path RDF) afin que SPARQL puisse surmonter cette limitation en remplaçant simplement les patrons de graphes basiques par des graphes PRDF. Nous étendons aussi PRDF à CPRDF (pour Constrained Path RDF) permettant d'exprimer des contraintes sur les sommets des chemins traversés (par exemple, "En outre, l'une des correspondances doit fournir une connexion sans fil."). Nous avons fourni des algorithmes corrects et complets pour répondre aux requêtes (la requête est un graphe PRDF ou CPRDF, la base de connaissances est un graphe RDF) basés sur un homomorphisme particulier, ainsi qu'une analyse détaillée de la complexité. Enfin, nous utilisons les graphes PRDF ou CPRDF pour généraliser les requêtes SPARQL, définissant les extensions PSPARQL et CPSPARQL, et fournissons des tests expérimentaux en utilisant une implémentation complète de ces deux langages.

Cette thèse porte sur les invariants des sphères d'homologie entière de dimension 3, et en particulier sur les invariants de type fini pour la filtration de Goussarov-Habiro.<br />Dans une première partie, on étudie la variation d'un invariant de degré 2n après chirurgie le long d'une surface par un élément du 2n-ième terme de la série centrale descendante du groupe de Torelli. Dans le cas d'un commutateur de 2n éléments du groupe de Torelli, on exprime cette variation en fonction de l'homomorphisme de Johnson évalué sur ces 2n éléments et du système de poids de l'invariant.<br /><br />Le calcul des claspers de Goussarov-Habiro donne des équivalences topologiques entre des chirurgies sur des corps en anses plongés dans les variétés. Ce calcul a déjà permis de préciser le comportement des invariants de type fini lors de nombreuses modifications topologiques. La deuxième partie de cette thèse est consacrée à un raffinement de ce calcul. Ce raffinement est ensuite appliqué à l'obtention d'une formule de chirurgie géométrique sur les noeuds pour les invariants de degré 4, c'est-à-dire que l'on exprime la variation d'un tel invariant après chirurgie sur un noeud en fonction d'invariants de courbes tracées au voisinage d'une surface de Seifert de ce noeud.

Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode de les voir comme des problèmes d'homomorphismes vers des structures relationnelles. Un axe de recherche actuel est la caractérisation des classes de complexité auxquelles appartient le problème d'homomorphisme, ceci dans la perspective de confirmer des conjectures reliant les propriétés algébriques des structures relationelles à la complexité du problème d'homomorphisme. Cette thèse propose dans un premier temps la caractérisation des digraphes pour lesquels le problème d'homomorphisme avec listes appartient à FO. On montre également que dans le cas du problèmes d'homomorphisme avec listes sur les digraphes télescopiques, les conjectures reliant algèbre et complexité sont confirmées. Dans un deuxième temps, on caractérise les graphes pour lesquels le problème d'homomorphisme avec listes est résoluble par cohérence d'arc. On introduit la notion de polymorphisme monochromatique et on propose un algorithme simple qui résoud le problème d'homomorphisme avec listes si le graphe cible admet un polymorphisme monochromatique TSI d'arité k pour tout k ≥ 2. / Constraint satisfaction problems, consisting in assigning values to variables while respecting a set of constraints, form a large class of natural problems. In order to study the complexity of these problems, it is convenient to see them as homomorphism problems on relational structures. One current research topic is to characterise complexity classes where the homomorphism problem belongs. The ultimate goal is to confirm conjectures that bind together algebraic properties of the relationnal structure and complexity of the homomorphism problem. At first, the thesis characterizes digraphs which generate FO list-homomorphism problems. It is shown that in the particular case of telescopic digraphs, conjectures binding together algebra and complexity are confirmed. Subsequently, we characterize graphs which generate arc-consistency solvable list-homomorphism problems. We introduce the notion of monochromatic polymorphism and we propose a simple algorithm which solves the list-homomorphism problem if the target graph admits a monochromatic TSI polymorphism of arity k for every k ≥ 2.