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 |
Files in this item
This item appears in the following Collection(s)
This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.