Skip to Main content Skip to Navigation
Book sections

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.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01398338
Contributor : Isabelle Gouat <>
Submitted on : Tuesday, January 24, 2017 - 1:05:24 PM
Last modification on : Tuesday, December 8, 2020 - 9:57:19 AM
Long-term archiving on: : Tuesday, April 25, 2017 - 5:57:47 PM

File

2013 Gioan Ramirez-Alfonsin - ...
Files produced by the author(s)

Identifiers

  • 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. ⟨lirmm-01398338⟩

Share

Metrics

Record views

283

Files downloads

890