La conjecture de partitionnement des chemins
dc.contributor.advisor | Rosenberg, Ivo G. | |
dc.contributor.author | Champagne-Paradis, Audrey | |
dc.date.accessioned | 2011-09-16T15:25:07Z | |
dc.date.available | NO_RESTRICTION | en |
dc.date.available | 2011-09-16T15:25:07Z | |
dc.date.issued | 2011-07-07 | |
dc.date.submitted | 2011-05 | |
dc.identifier.uri | http://hdl.handle.net/1866/5288 | |
dc.subject | Théorie des graphes | en |
dc.subject | Graph theory | en |
dc.subject | Détour | en |
dc.subject | Detour | en |
dc.subject | Chemin | en |
dc.subject | Path | en |
dc.subject | Plus long chemin | en |
dc.subject | Longest path | en |
dc.subject | Partition | en |
dc.subject.other | Mathematics / Mathématiques (UMI : 0405) | en |
dc.title | La conjecture de partitionnement des chemins | en |
dc.type | Thèse ou mémoire / Thesis or Dissertation | |
etd.degree.discipline | Mathématiques | en |
etd.degree.grantor | Université de Montréal | fr |
etd.degree.level | Maîtrise / Master's | en |
etd.degree.name | M. Sc. | en |
dcterms.abstract | Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés. | en |
dcterms.abstract | Let G = (V,E) be a finite simple graph. We denote the number of vertices in a longest path in G by τ(G). A partition (A,B) of V is called an (a,b)−partition if τ(⟨A⟩) ≤ a and τ(⟨B⟩) ≤ b. If G can be (a,b)−partitioned for every pair of positive integers (a, b) satisfying a + b = τ (G), we say that G is τ −partitionable. The following conjecture, called The Path Partition Conjecture, has been stated by Lovász and Mihók in 1981 : every graph is τ−partitionable. Since that, many researchers prove that this conjecture is true for several classes of graphs and digraphs. This study summarizes the different results about the Path Partition conjecture. | en |
dcterms.language | fra | en |
Fichier·s constituant ce document
Ce document figure dans la ou les collections suivantes
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Il peut être utilisé dans le cadre d'une utilisation équitable et non commerciale, à des fins d'étude privée ou de recherche, de critique ou de compte-rendu comme le prévoit la Loi. Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.