Aller au menu Aller au contenu
UGA
Optimisation Combinatoire
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Optimisation Combinatoire

Soutenance de thèse de Quentin Fortier le 27 octobre 2017 à 14 H en amphi C - Site Viallet Grenoble INP

Publié le 10 octobre 2017
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentTélécharger au format PDFEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
Soutenance 27 octobre 2017

Intitulée : Aspects de la connectivité avec contraintes de matroïdes dans les graphes - Aspects of connectivity with matroid constraints in graphs

Les membres du jury :

  • Monsieur Denis Cornaz, Maître de conférences, Université Paris Dauphine, Rapporteur
  • Monsieur Yann Vaxès, Professeur des Universités, Université Aix-Marseille, Rapporteur
  • Monsieur Stéphane Bessy, Maître de conférences, Université de Montpellier, Examinateur
  • Monsieur Roland Grappe, Maître de conférences, Université Paris 13, Examinateur
  • Madame Nadia Brauner, Professeur des Universités, Université Grenoble Alpes, Présidente du jury
  • Monsieur Zoltán Szigeti, Professeur des Universités, Grenoble INP, Directeur de thèse

Résumé :

La notion de connectivité est fondamentale en théorie des graphes. Nous proposons une étude approfondie d’un récent développement dans ce domaine, en ajoutant des contraintes de matroïdes. Dans un premier temps, nous exhibons deux opérations de réduction sur les graphes connectés avec contraintes de matroïdes. Ces opérations permettent de généraliser le théorème de caractérisation de la connectivité de Menger et le théorème de packing d’arborescences d’Edmonds. Cependant, cette extension du théorème d’Edmonds ne garantie plus que les arborescences soient couvrantes. Il a été conjecturé que l’on peut toujours trouver de telles arborescences couvrantes. Nous prouvons cette conjecture dans certains cas particuliers, notamment pour les matroïdes de rang deux et pour les matroïdes transversaux. Nous réfutons cette conjecture dans le cas général en construisant un contre-exemple à plus de 300 sommets, sur une extension parallèle du matroïde de Fano. Enfin, nous explorons d’autres notions de connexité avec contraintes de matroïdes: pour des graphes mixtes, des hypergraphes, et avec condition d’atteignabilité.

Abstract :
 
The notion of connectivity is fundamental in graph theory. We study thoroughly a recent development in this field, with the addition of matroid constraints. Firstly, we exhibit two reduction operations on connected graphs with matroid constraints. Using these operations, we generalize Menger’s theorem on connectivity and Edmond’s theorem on packing of arborescences. However, this extension of Edmond’s theorem does not ensure that the arborescences are spanning. It has been conjectured that one can always find such spanning arborescences. We prove this conjecture in some cases, including matroids of rank two and transversal matroids. We disprove this conjecture in the general case by providing a counter-example with more than 300 vertices, on a parallel extension of the Fano matroid. Finally, we explore other generalizations of connectivity with matroid constraints: in mixed graphs, hypergraphs and with reachability conditions.

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentTélécharger au format PDFEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

Rédigé par Fadila Messaoud-Djebara

mise à jour le 10 octobre 2017

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Communauté Université Grenoble Alpes
×
Afin d'améliorer la qualité de ce site et le service rendu à l'utilisateur, nous utilisons des cookies de mesure d’audience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies à cette fin. Pour en savoir plus