Matroïde

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, et plus particulièrement en combinatoire, un matroïde est une structure introduite comme un cadre général pour le concept d'indépendance linéaire. Elle est donc naturellement liée à l'algèbre linéaire (déjà au niveau du vocabulaire : indépendant, base, rang), et aussi par ailleurs, essentiellement à la théorie des graphes (circuit, cycle), à l'algorithmique (glouton), et à la géométrie (pour diverses questions liées à la représentation)[1].

La notion a été introduite en 1935 par Whitney.

Définitions[modifier | modifier le code]

Il existe différentes définitions équivalente de la notion de matroïde. La première consiste à donner les axiomes que les ensembles indépendants doivent satisfaire. On peut aussi définir les axiomes des bases (c'est-à-dire les indépendants maximaux pour l'inclusion), ou encore définir les axiomes des circuits (pour des raisons de correspondance avec les graphes, les dépendants minimaux par rapport à l'inclusion sont appelés les circuits). Enfin, d'autres définitions concernent la fonction de rang (qui associe à tout sous-ensemble U de S le cardinal maximum d'un indépendant inclus dans U), ou encore un opérateur de fermeture (satisfaisant la propriété d'échange de Mac LaneSteinitz). Une propriété importante de la fonction de rang d'un matroïde est sa sous-modularité.

Pour les matroïdes binaires, il existe encore une autre définition basée sur les cycles d'un matroïde (c'est-à-dire les unions disjointes de circuits). Ce sont précisément les couples (S, C) tels que C est une collection de sous-ensembles de S fermée par-rapport à la différence symétrique.

Par les indépendants[modifier | modifier le code]

La définition originale de Whitney (Whitney 1935) est la suivante:

Soient S un ensemble fini non vide et I une famille non vide de parties de S (les « indépendants »). Le couple (S, I) est appelé un matroïde s'il vérifie les deux axiomes suivants[2] :

  • l'hérédité : pour tout X \in I , si Y \subseteq X alors Y \in I .
  • l'échange : si X \in I et Y \in I , |X|<|Y|, alors \exists e \in Y \setminus X tel que X \cup \{ e\}\in I.

Une base est un indépendant maximal. L'axiome d'échange induit que tout ensemble maximal est maximum, et donc que toutes les bases ont même cardinal[2].

Exemples de matroïdes[modifier | modifier le code]

Matroïde uniforme[modifier | modifier le code]

Un exemple est le matroïde uniforme : soient deux entiers non nuls n et k, on obtient un matroïde en prenant pour S un ensemble de n éléments quelconques et pour indépendants les sous-ensembles de cardinalité inférieure à k.

Matroïdes représentables ou linéaires[modifier | modifier le code]

L'exemple le plus mathématiquement parlant de matroïde est donc un couple (S, I)S correspond à l'ensemble des indices des colonnes d'une matrice sur un certain corps, et où I correspond à la collection des sous-ensembles d'indices correspondants aux vecteurs linéairement indépendants. De tels matroïdes sont dits représentables ou linéaires[2]. Il existe des matroïdes qui ne sont pas représentables. Les matroïdes représentables en n'utilisant que le corps à deux éléments sont dits binaires. Tutte et Whitney ont donné des caractérisations de ces matroïdes. Les matroïdes représentables sur n'importe quel corps sont dits réguliers. Tutte les a caractérisés.

Matroïdes graphiques[modifier | modifier le code]

Un matroïde graphique est un matroïde tel que S est en bijection avec les arêtes d'un graphe G et où un sous-ensemble de S est indépendant s'il forme une forêt dans G (sous-graphe acyclique). Les circuits (au sens de la théorie des matroïdes) correspondent alors aux circuits de G (au sens de la théorie des graphes). Les matroïdes graphiques sont binaires (il suffit de prendre la matrice d'incidence de G). Ils sont aussi réguliers (il suffit d'orienter arbitrairement G et de prendre la matrice d'incidence).

L'ensemble des coupes d'un graphe constitue l'ensemble des cycles d'un matroïde, que l'on appelle le matroïde cographique.

Notions importantes et propriétés[modifier | modifier le code]

Circuits[modifier | modifier le code]

Un circuit est un ensemble dépendant minimal. Pour un matroïde graphique, il s'agit d'un cycle au sens usuel. Les circuits ont la propriété suivante : si S \in I et e \in E tel que S \cup {e} \notin I, alors il existe un unique circuit inclus dans S \cup {e}[2].

Rang[modifier | modifier le code]

Comme en algèbre linéaire, on peut définir une notion de rang sur les parties de E dans un matroïde M[2]. r_M:2^E \mapsto \mathbb{N}:\max\{|Y|:Y\subseteq X, Y\in I \}. Le rang d'un matroïde est une fonction sous-modulaire.

Polytopes et optimisation[modifier | modifier le code]

Le polytope des indépendants : polymatroïdes[modifier | modifier le code]

À tout matroïde on peut associer son polytope des indépendants dans l'espace à |S| dimensions, qui est l'enveloppe convexe des vecteurs caractéristiques (dans {0,1} à la puissance S) de ses indépendants. Edmonds a montré que ce polytope peut être décrit par les inégalités linéaires de positivité et de rang. Plus précisément le polytope est :

\{ x \in \mathbb{R}^{|E|}:\forall S \subseteq E, \sum_{e\in S}x_e \leq r_M(S) ; \forall e \in E x_e \geq 0 \}.

Il existe plusieurs preuves de ce résultat[2]. On appelle polymatroïde, tout polytope qui est le polytope des indépendants d'un matroïde.

Lien avec les algorithmes gloutons[modifier | modifier le code]

Les matroïdes sont précisément les couples (S, I) satisfaisant l'axiome d'hérédité tels que pour toute fonction associant un poids (un réel) à chaque élément de S l'algorithme glouton permet de déterminer un indépendant de poids maximum.

Notes et références[modifier | modifier le code]

  1. (en) « Matroids you have known », sur Mathematical Association of America,‎ 2009 (consulté le 30 octobre 2014)
  2. a, b, c, d, e et f Michel Goemans, « Lecture notes on matroid optimization », sur Massachusetts Institute of Technology,‎ 2009

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Hassler Whitney, « On the abstract properties of linear dependence », American Journal of Mathematics, The Johns Hopkins University Press, vol. 57, no 3,‎ , p. 509–533 (DOI 10.2307/2371182)

Articles connexes[modifier | modifier le code]