Reference number : GC-2017-Q1-02807, amendment number : , agreement type : G, recipient legal name : Hertz, Alain (École Polytechnique de Montréal), recipient country : CA, recipient province : nan, recipient city : Quebec|Québec, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : Les projets de recherche que je compte r&eacute;aliser et encadrer durant ces 5 prochaines ann&eacute;es sont multiples et compl&eacute;mentaires. Ils vont de la recherche fondamentale en th&eacute;orie des graphes (aspects structurels, th&eacute;orie extr&eacute;male, etc.) au d&eacute;veloppement d&rsquo;algorithmes efficaces pour la r&eacute;solution de probl&egrave;mes r&eacute;els qu&rsquo;on peut mod&eacute;liser &agrave; l&rsquo;aide des graphes. Ces projets sont regroup&eacute;s en 3 th&egrave;mes principaux. 
 
 Le premier th&egrave;me est l'&eacute;tude d'extensions de probl&egrave;mes classiques de colorations de graphes. Par exemple, au lieu d&rsquo;interdire que les extr&eacute;mit&eacute;s d'une ar&ecirc;te aient la m&ecirc;me couleur, on peut imposer une limite sur le nombre de violations de cette contrainte; ceci donne lieu &agrave; des colorations impropres qui apparaissent naturellement en t&eacute;l&eacute;communication. Comme autre exemple, on peut citer la coloration de graphes mixtes dans lesquels des contraintes de pr&eacute;c&eacute;dence forcent certains sommets &agrave; avoir une couleur (repr&eacute;sent&eacute;e par un nombre) plus petite que d&rsquo;autres; ces colorations permettent de mod&eacute;liser des probl&egrave;mes d&rsquo;ordonnancement de type job-shop. 
 
 Le deuxi&egrave;me th&egrave;me est l'&eacute;tude du probl&egrave;me de l'arbre de Steiner avec capacit&eacute;, qui est un mod&egrave;le naturel lors de la conception de r&eacute;seaux de collecte d&rsquo;&eacute;nergie &eacute;olienne ou de distribution d&rsquo;&eacute;lectricit&eacute;. &Eacute;tant donn&eacute; un graphe pond&eacute;r&eacute; dont les ar&ecirc;tes ont des capacit&eacute;s, et un sous-ensemble S de sommets contenant une racine r, le probl&egrave;me &agrave; r&eacute;soudre est de d&eacute;terminer un arbre induit, enracin&eacute; en r, contenant tous les sommets de S, qui soit de poids minimum (probl&egrave;me de Steiner classique), tout en satisfaisant la contrainte de capacit&eacute; suivante : pour chaque ar&ecirc;te e, le nombre de cha&icirc;nes qui contiennent e et qui relient r aux sommets de S ne doit pas exc&eacute;der la capacit&eacute; de e. 
 
 Le troisi&egrave;me th&egrave;me consiste &agrave; borner les invariants d&rsquo;un graphe ou &agrave; les comparer entre eux (plus grande ou petite diff&eacute;rence de valeur) et &agrave; d&eacute;terminer les graphes extr&eacute;maux qui atteignent ces bornes. Un int&eacute;r&ecirc;t particulier sera port&eacute; sur les invariants tels que la proximit&eacute;, l&rsquo;&eacute;loignement ou l&rsquo;excentricit&eacute; pour lesquels de nombreuses bornes restent &agrave; d&eacute;terminer et qui sont essentiels &agrave; une bonne compr&eacute;hension de la structure d&rsquo;un r&eacute;seau donn&eacute;. 
 
Les mod&egrave;les standards en th&eacute;orie des graphes sont souvent trop simples pour traiter les probl&egrave;mes rencontr&eacute;s en pratique. Ce n&rsquo;est qu&rsquo;en les &eacute;tendant et en les adaptant qu&rsquo;on peut r&eacute;ussir &agrave; g&eacute;n&eacute;rer des solutions satisfaisantes. Les projets susmentionn&eacute;s ont pour but de produire des mod&egrave;les et des techniques de r&eacute;solution adapt&eacute;s &agrave; un grand &eacute;ventail de probl&egrave;mes auxquels les entreprises sont quotidiennement confront&eacute;es. L&rsquo;incidence principale de ces recherches sera de procurer des outils efficaces aux d&eacute;cideurs des principaux secteurs industriels qu&eacute;b&eacute;cois et d'ailleurs. Aussi, les &eacute;tudiants impliqu&eacute;s dans ces travaux seront confront&eacute;s &agrave; des probl&egrave;mes industriels r&eacute;els, ce qui leur ouvrira d'excellentes perspectives d'emploi &agrave; la fin de leurs &eacute;tudes., program purpose french : Les projets de recherche que je compte r&eacute;aliser et encadrer durant ces 5 prochaines ann&eacute;es sont multiples et compl&eacute;mentaires. Ils vont de la recherche fondamentale en th&eacute;orie des graphes (aspects structurels, th&eacute;orie extr&eacute;male, etc.) au d&eacute;veloppement d&rsquo;algorithmes efficaces pour la r&eacute;solution de probl&egrave;mes r&eacute;els qu&rsquo;on peut mod&eacute;liser &agrave; l&rsquo;aide des graphes. Ces projets sont regroup&eacute;s en 3 th&egrave;mes principaux. 
 
 Le premier th&egrave;me est l'&eacute;tude d'extensions de probl&egrave;mes classiques de colorations de graphes. Par exemple, au lieu d&rsquo;interdire que les extr&eacute;mit&eacute;s d'une ar&ecirc;te aient la m&ecirc;me couleur, on peut imposer une limite sur le nombre de violations de cette contrainte; ceci donne lieu &agrave; des colorations impropres qui apparaissent naturellement en t&eacute;l&eacute;communication. Comme autre exemple, on peut citer la coloration de graphes mixtes dans lesquels des contraintes de pr&eacute;c&eacute;dence forcent certains sommets &agrave; avoir une couleur (repr&eacute;sent&eacute;e par un nombre) plus petite que d&rsquo;autres; ces colorations permettent de mod&eacute;liser des probl&egrave;mes d&rsquo;ordonnancement de type job-shop. 
 
 Le deuxi&egrave;me th&egrave;me est l'&eacute;tude du probl&egrave;me de l'arbre de Steiner avec capacit&eacute;, qui est un mod&egrave;le naturel lors de la conception de r&eacute;seaux de collecte d&rsquo;&eacute;nergie &eacute;olienne ou de distribution d&rsquo;&eacute;lectricit&eacute;. &Eacute;tant donn&eacute; un graphe pond&eacute;r&eacute; dont les ar&ecirc;tes ont des capacit&eacute;s, et un sous-ensemble S de sommets contenant une racine r, le probl&egrave;me &agrave; r&eacute;soudre est de d&eacute;terminer un arbre induit, enracin&eacute; en r, contenant tous les sommets de S, qui soit de poids minimum (probl&egrave;me de Steiner classique), tout en satisfaisant la contrainte de capacit&eacute; suivante : pour chaque ar&ecirc;te e, le nombre de cha&icirc;nes qui contiennent e et qui relient r aux sommets de S ne doit pas exc&eacute;der la capacit&eacute; de e. 
 
 Le troisi&egrave;me th&egrave;me consiste &agrave; borner les invariants d&rsquo;un graphe ou &agrave; les comparer entre eux (plus grande ou petite diff&eacute;rence de valeur) et &agrave; d&eacute;terminer les graphes extr&eacute;maux qui atteignent ces bornes. Un int&eacute;r&ecirc;t particulier sera port&eacute; sur les invariants tels que la proximit&eacute;, l&rsquo;&eacute;loignement ou l&rsquo;excentricit&eacute; pour lesquels de nombreuses bornes restent &agrave; d&eacute;terminer et qui sont essentiels &agrave; une bonne compr&eacute;hension de la structure d&rsquo;un r&eacute;seau donn&eacute;. 
 
Les mod&egrave;les standards en th&eacute;orie des graphes sont souvent trop simples pour traiter les probl&egrave;mes rencontr&eacute;s en pratique. Ce n&rsquo;est qu&rsquo;en les &eacute;tendant et en les adaptant qu&rsquo;on peut r&eacute;ussir &agrave; g&eacute;n&eacute;rer des solutions satisfaisantes. Les projets susmentionn&eacute;s ont pour but de produire des mod&egrave;les et des techniques de r&eacute;solution adapt&eacute;s &agrave; un grand &eacute;ventail de probl&egrave;mes auxquels les entreprises sont quotidiennement confront&eacute;es. L&rsquo;incidence principale de ces recherches sera de procurer des outils efficaces aux d&eacute;cideurs des principaux secteurs industriels qu&eacute;b&eacute;cois et d'ailleurs. Aussi, les &eacute;tudiants impliqu&eacute;s dans ces travaux seront confront&eacute;s &agrave; des probl&egrave;mes industriels r&eacute;els, ce qui leur ouvrira d'excellentes perspectives d'emploi &agrave; la fin de leurs &eacute;tudes., agreement title english : Théorie des graphes : algorithmique, aspects structurels, théorie extrémale et applications, agreement title french : Théorie des graphes : algorithmique, aspects structurels, théorie extrémale et applications, agreement number : RGPIN, agreement value : 205000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada