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 Access content directly
Book Sections Year : 2013

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

Abstract

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
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : lirmm-01398338 , version 1

Cite

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⟩
305 View
810 Download

Share

Gmail Facebook X LinkedIn More