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. vignette|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épendants puisque c peut s'écrire comme c1a + c2b où c1 et c2 sont des scalaires. C'est cette notion d'indépendance que cherche à généraliser les matroïdes. La définition originale de Whitney 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 , si alors . l'échange : si et , , alors tel que . 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. 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).