Matroïde
Un article de Wikipédia, l'encyclopédie libre.
La notion de matroïde (introduite en 1935 par Whitney) a pour vocation initiale de saisir l'essence du concept d'indépendance linéaire. Elle est donc naturellement liée à l'algèbre linéaire (déja 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 combinatoire (pour diverses questions liées à la représentation).
L'exemple le plus mathématiquement parlant de matroïde est donc un couple (S,I) ou S correspond à l'ensemble des indices des colonnes d'une matrice sur un certain corps et I est la collection des sous-ensembles d'indices correspondants aux vecteurs linéairement indépendants. De tels matroïdes sont dit représentables. Il est à noter qu'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 dit binaires. Tutte et Whitney ont donné des caractérisations de ces matroïdes. Les matroïdes représentables sur n'importe quel corps sont dit réguliers. Tutte les a caractérisés.
Parmis les différentes manières de décrire (axiomatiquement) un matroïde, la première consiste à définir les ensembles indépendants. On peut aussi, ce qui est équivalent, décrire à la place les bases ou bien les circuits (pour des raisons de correspondance avec les graphes les dépendants minimaux par-rapport à l'inclusion sont appellés les circuits), ou même donner la fonction de rang, ou encore un opérateur de fermeture (satisfaisant la propriété d'échange de MacLane–Steinitz). Donnons maintenant la définition selon Withney:
Sommaire |
[modifier] La définition originale (Whitney, 1935)
Soient S un ensemble fini non vide et I une famille non vide de parties de S. Le couple (S,I) est appelé un matroïde si il verifie les deux axiomes suivants:
- l'hérédité : à savoir, pour tout sous-ensemble X de S appartenant à I, et pour tout sous-ensemble Y de X, alors Y appartient aussi à I.
- l'échange : à savoir, si A et B sont deux sous-ensembles de S appartenant tous les deux à I et tels que A a plus d'éléments que B, alors il existe au-moins un élément propre à A (dans A mais pas dans B) tel que B union cet élément soit encore dans I.
Les sous-ensembles de S appartenant à I sont appelés les indépendants. Une base est un indépendant maximal au sens de l'inclusion. On peut montrer que toutes les bases ont même cardinal.
Un exemple est le matroïde uniforme: Soient deux entiers non nuls n et k, alors on obtient un matroïde en prenant S un ensemble de n éléments quelconques et les indépendants sont les sous-ensembles de cardinalité inférieur à k.
[modifier] Matroïdes graphiques
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. Les circuits correspondent alors aux circuits de G. Un concept de dualité fait aussi correspondre les coupes d'un graphe aux circuits (en fait aux cycles c'est-à-dire aux unions disjointes de circuits). Les matroïdes graphiques sont binaires (il suffit de prendre la matrice d'adjacence de G). Ils sont aussi réguliers (il suffit d'orienter arbitrairement G et de prendre la matrice d'adjacence).
[modifier] Une définition algorithmique
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.
[modifier] Le polytope des indépendants
Le polytope des indépendants est l'enveloppe convexe des vecteurs caractéristiques (dans {0,1} à la puissance S) des indépendants. Edmonds a montré que ce polytope peut-être décrit par les inégalités linéaires de positivité et de rang.
 |
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
