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

Emeric Gioan 1 Jorge Ramirez Alfonsin 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Chapitre d'ouvrage
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. 〈http://www.lcdpu.fr/livre/?GCOI=27000100531990&fa=complements〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01398338
Contributeur : Isabelle Gouat <>
Soumis le : mardi 24 janvier 2017 - 13:05:24
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 25 avril 2017 - 17:57:47

Fichier

2013 Gioan Ramirez-Alfonsin - ...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01398338, version 1

Citation

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. 〈http://www.lcdpu.fr/livre/?GCOI=27000100531990&fa=complements〉. 〈lirmm-01398338〉

Partager

Métriques

Consultations de la notice

182

Téléchargements de fichiers

298