Matroïde

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), mais aussi à la théorie des graphes (circuit, cycle), à l'algorithmique (algorithme glouton), et à la géométrie (pour diverses questions liées à la représentation).

La notion a été introduite en 1935 par Whitney. Le mot matroïde provient du mot matrice.

Notion d'indépendance

Trois vecteurs linéairement dépendants.

L'indépendance linéaire d'une famille de vecteurs correspond au fait que l'on ne peut réécrire l'un des vecteurs comme combinaison linéaire des autres. En prenant l'exemple de la figure à droite, les vecteurs {a, b} forment un ensemble indépendant. Par contre, l'ensemble des vecteurs {a, b, c} n'est pas indépendant puisque c peut s'écrire comme c₁a + c₂b où c₁ et c₂ sont des scalaires.

C'est cette notion d'indépendance que cherchent à généraliser les matroïdes.

Définition

La définition originale de Whitney (Whitney 1935) est la suivante. Soient E un ensemble fini non vide et I une famille non vide de parties de E. Le couple (E, I) est appelé un matroïde s'il vérifie les deux axiomes suivants :

• 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$.

Les sous-ensembles de I s'appellent les ensembles indépendants, ou parfois plus simplement les indépendants.

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.

Définitions alternatives

Il existe différentes définitions équivalentes 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 E le cardinal maximal d'un indépendant inclus dans U), ou encore un opérateur de fermeture (satisfaisant la propriété d'échange de Mac Lane–Steinitz). 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 (E, I) tels que I est une collection de sous-ensembles de E fermée par rapport à la différence symétrique.

Exemples de matroïdes

Matroïde libre

On considère un ensemble E quelconque. En prenant I l'ensemble de tous les sous-ensembles de E, on vérifie les propriétés d'hérédité et d'échange : (E, I) est un matroïde. Il s'appelle le matroïde libre.

Matroïdes uniformes

Soient deux entiers non nuls n et k. On obtient un matroïde en prenant pour E 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

Considérons une matrice A sur un certain corps, par exemple $A={\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\\\end{pmatrix}}$. À partir de cette matrice, on définit le matroïde (E, I) où E est l'ensemble des indices de colonnes de la matrice A, et où I est la collection des sous-ensembles d'indices correspondants aux vecteurs-colonnes linéairement indépendants. De tels matroïdes sont dits représentables ou linéaires.

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^{[réf. nécessaire]}. Les matroïdes représentables sur n'importe quel corps sont dits réguliers. Tutte les a aussi caractérisés^{[réf. nécessaire]}.

Matroïdes définis à partir de graphes

Matroïdes graphiques

Une autre source d'inspiration de la théorie des matroïdes est la théorie des graphes.

Considérons un graphe fini non orienté G. On définit son matroïde associé M(G) de la façon suivante. L'ensemble E est l'ensemble des arêtes de G. Puis les ensembles indépendants sont les forêts de G (c'est-à-dire les sous-ensembles d'arêtes acycliques). 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).

Il existe des matroïdes non graphiques, c'est-à-dire que l'on ne peut pas voir leurs éléments comme des arêtes d'un graphe, de façon que les ensembles indépendants soient les forêts. Par contre, tous les matroïdes de taille 3 sont graphiques.

Les matroïdes graphiques sont un cas particulier de matroïdes binaires et donc un cas particulier de matroïdes linéaires. En effet, toute forêt de G correspond à un sous-ensemble de vecteurs-colonnes linéairement indépendants dans la matrice d'incidence de G, dont les entrées sont binaires.^{[réf. nécessaire]}. Ils sont aussi réguliers (il suffit d'orienter arbitrairement G et de prendre la matrice d'incidence)^{[pas clair][réf. nécessaire]}.

Matroïdes cographiques

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

Circuits

Un circuit est un ensemble dépendant minimal, c'est-à-dire un ensemble dont tous les sous-ensembles stricts sont indépendants. 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}$.

Rang

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

Polytopes

Le polytope des indépendants : polymatroïdes

À tout matroïde, on peut associer son polytope des indépendants dans l'espace à $|E|$ dimensions comme suit. Un vecteur caractéristique d'un ensemble indépendant S est le vecteur de {0, 1}^E, où on met un 1 sur la coordonnée d'un élément e de E si e est dans S, et 0 sinon. Le polytope des indépendants est l'enveloppe convexe des vecteurs caractéristiques 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|}:\sum _{e\in S}x_{e}\leq r_{M}(S),x_{e}\geq 0~\forall S\subseteq E,\forall e\in E\}.$

Il existe plusieurs preuves de ce résultat. On appelle polymatroïde tout polytope des indépendants d'un matroïde.

Algorithmes gloutons

La théorie des matroïdes décrit plusieurs applications où la méthode gloutonne fournit une solution optimale. Malheureusement, la théorie des matroïdes ne couvre pas toutes les applications où la méthode gloutonne est optimale : par exemple, le codage de Huffman, bien que reposant sur la méthode gloutonne, ne se décrit pas avec la théorie des matroïdes (cf. p. 404 dans ).

Pour les problèmes d'optimisation, on introduit les matroïdes pondérés. Un matroïde (E, I) est pondéré s'il existe une fonction de poids w qui assigne un poids strictement positif w(x) à chaque élément x de E. La fonction de poids s'étend de manière naturelle aux sous-ensembles F de E : w(F) est la somme des w(x) pour x dans F.

Il existe un algorithme glouton qui permet de déterminer un indépendant de poids maximal. Cet algorithme est un schéma générique : il fonctionne dès lors que le problème algorithmique peut se formuler comme le calcul d'un indépendant de poids maximal pour un certain matroïde (E, I). Voici des problèmes algorithmiques où la théorie des matroïdes s'applique :

• Calcul d'un arbre couvrant de poids minimal dans un graphe non orienté pondéré (p. 406 dans ). L'algorithme glouton générique est l'algorithme de Kruskal.
• problème d'ordonnancement de tâches avec échéance (cf. p. 410 dans )

La théorie des gloutonoïdes (cf. p. 416 dans ) (en anglais : greedoids), initiée par Korte et Lovász, étend la théorie des matroïdes pour capturer plus de situations où la méthode gloutonne fonctionne.

Voir aussi

Bibliographie

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

• Michel Goemans, « Lecture notes on matroid optimization », sur Massachusetts Institute of Technology, 2009

• Emeric Gioan, Jorge Ramirez Alfonsin, "Eléments de théorie des matroïdes et matroïdes orientés", 2013.

Articles connexes

• Cryptomorphisme
• Antimatroïde (en)
• Matroïde orienté (en)