Eléments de théorie des matroïdes et matroïdes orientés - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Chapitre D'ouvrage Année : 2013

Eléments de théorie des matroïdes et matroïdes orientés

Résumé

Un matroïde - mot dérivé de ''matrice'' - est une structure combinatoire qui peut être définie en retenant les principales propriétés ensemblistes de la dépendance linéaire dans les espaces vectoriels. Ainsi, lorsqu'il est associé à un ensemble fini de points, il capture les relations d'incidence (alignement, coplanarité, etc.) entre ces points. Un matroïde orienté est une structure combinatoire proche qui capture - en plus, dans ce cas - les relations de convexité entre ces points, en prenant cette fois en compte les signes dans les relations de dépendance linéaire. Il correspond en toute généralité à un objet topologique : un arrangement de pseudosphères. Les matroïdes et les matroïdes orientés satisfont de nombreuses axiomatiques équivalentes, possèdent une notion fondamentale de dualité, et fournissent un cadre adéquat pour des notions classiques variées (en théorie des graphes, en optimisation discrète, en géométrie, etc.), ce qui leur confère un caractère très naturel.
Fichier principal
Vignette du fichier
2013 Gioan Ramirez-Alfonsin - Cours sur les matroides (orientes) - GDRIM2013.pdf (381.25 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01398338 , version 1 (24-01-2017)

Identifiants

  • HAL Id : lirmm-01398338 , version 1

Citer

Emeric Gioan, Jorge Ramirez Alfonsin. Eléments de théorie des matroïdes et matroïdes orientés. Philippe Langlois. Informatique mathématique - Une photographie en 2013, Presses Universitaires de Perpignan, pp.47-95, 2013, I-2.Théorie des matroïdes et des matroïdes orientés, 9782354121839. ⟨lirmm-01398338⟩
324 Consultations
852 Téléchargements

Partager

More