- FR
- EN
Mardi 5 novembre 2019, 14h, en salle A411
Abstract :
Dans cet exposé je vais parler de quelques systèmes total dual
box-intégraux (box-TDI) que j’ai traité pendant ma thèse.
Les concepts de total dual intégralité et total dual box-intégralité ont
étés introduits dans les années 70, par Edmonds, Giles, et Pulleyblank.
Ces concepts sont liés avec les relations de min-max en optimisation
combinatoire.
Dans un premier temps, nous parlerons du cône des flots, c’est-à-dire le
cône généré par les vecteurs d’incidence des flots et des arêtes du
graphe. Ce cône est box-TDI si et seulement si le graphe associé est
série-parallèle. Lorsque le graphe est série-parallèle, nous montrons une description du
cône des flots à l’aide du système de Schrijver, qui est l’unique
système TDI à coefficients entiers dont la suppression de n’importe quelle
inégalité détruit le caractère TDI.
Deuxièmement, nous étudions le polyèdre des sous-graphes
k-arête-connexes Pk(G). Nous montrons que P1(G) est un polyèdre box-TDI pour
n’importe quel graphe G. Ensuite, nous montrons que, pour chaque k fixé,
Pk(G) est box-TDI si et seulement si G est un graphe série-parallèle.
Finalement, nous donnons un système à coefficients entiers qui décrit Pk(G) et
qui est TDI si et seulement si G est série-parallèle.
