Logique et ensemblesNotion · Glossaire
matroïde
Un matroïde est un ensemble fini muni d'une famille de sous-ensembles dits indépendants : elle contient l'ensemble vide, reste stable quand on retire des éléments et permet d'ajouter à tout indépendant plus petit un élément d'un indépendant plus grand qui n'appartient pas au premier, sans perdre l'indépendance. Cette règle d'échange abstrait l'indépendance linéaire et explique l'efficacité des algorithmes gloutons pour certains problèmes d'optimisation.
Sommaire
Ce que vous allez apprendre
- Interpréter l'indépendance abstraite à partir des arêtes d'un triangle.
- Vérifier les axiomes d'hérédité et d'augmentation avec des notations introduites.
- Suivre un choix glouton de poids 1, 2 et 3 et contrôler son optimum parmi les trois bases.
- Relier les matroïdes aux graphes, aux espaces vectoriels et à l'optimisation combinatoire.
- Repérer une famille héréditaire qui n'est pas un matroïde parce que l'échange échoue.
En clair
Imaginez les trois arêtes d'un triangle. On peut en choisir une, puis une deuxième, sans fermer de boucle. La troisième est alors refusée : avec les deux premières, elle formerait le cycle complet.
Un matroïde retient cette idée de choix compatibles. Un choix reste permis si l'on en retire des éléments, et deux choix permis de tailles différentes peuvent s'équilibrer en ajoutant au plus petit un élément du plus grand. Cette règle rend les choix gloutons fiables.
Définition
Un matroïde est un couple formé d'un ensemble fini E, appelé ensemble support, et d'une famille I de sous-ensembles de E, dits indépendants. Cette famille doit satisfaire trois axiomes. Le vide est indépendant. Tout sous-ensemble d'un ensemble indépendant est indépendant : c'est l'hérédité. Enfin, si A et B sont indépendants et si B contient un élément de plus que A, un élément de B absent de A peut être ajouté à A sans perdre l'indépendance.
En notant |A| le nombre d'éléments de A, l'axiome d'augmentation s'écrit :
Il garantit que tous les ensembles indépendants maximaux, appelés bases, ont la même taille. Cette taille est le rang du matroïde. Un ensemble dépendant minimal est appelé circuit.
Dans un espace vectoriel, les éléments de E peuvent être des vecteurs et I rassemble les familles linéairement indépendantes. Dans un graphe fini, E peut être l'ensemble des arêtes et I les sous-ensembles d'arêtes sans cycle : on obtient le matroïde graphique. Les mêmes axiomes décrivent ainsi une indépendance abstraite, sans supposer que les éléments sont des vecteurs.
Un exemple, pas à pas
Considérons un triangle dont les arêtes sont a, b et c. Leurs poids respectifs sont 1, 2 et 3. Un ensemble d'arêtes est déclaré indépendant lorsqu'il ne contient aucun cycle. Le but est d'obtenir une base de poids total minimal.
1. Trions les arêtes par poids croissant : a, puis b, puis c.
2. Ajoutons a, de poids 1. Une seule arête ne forme pas de cycle ; le choix {a} est indépendant.
3. Ajoutons b, de poids 2. Les deux arêtes forment un chemin, pas un cycle ; {a, b} est indépendant. Le schéma matérialise ces deux choix et la fermeture que provoquerait c.
4. L'arête c, de poids 3, fermerait le triangle. On la rejette. L'ensemble {a, b} est maximal et contient deux arêtes : c'est une base, de poids total 1 + 2 = 3.
5. Contrôlons le minimum. Les trois bases possibles sont {a, b}, {a, c} et {b, c}, de poids respectifs 3, 4 et 5. Le choix glouton donne bien la base la plus légère.
En pratique
Dans un réseau modélisé par un graphe, on peut chercher des liaisons peu coûteuses qui raccordent tous les sommets sans cycle. L'indépendance graphique autorise l'ajout d'une arête tant qu'elle ne ferme pas de boucle ; une base est une forêt couvrante, formée d'un arbre couvrant dans chaque composante connexe.
Avec une liste finie de vecteurs, le même geste consiste à conserver un vecteur seulement s'il n'est pas combinaison linéaire de ceux déjà retenus. On préfère cette modélisation au matroïde graphique lorsque la dépendance vient d'équations linéaires, et non de cycles.
En optimisation combinatoire, on trie les éléments par poids puis on accepte chaque ajout qui préserve l'indépendance. Cette garantie gloutonne appartient au cadre des matroïdes. Si les choix admissibles n'en vérifient pas l'échange, le même geste peut manquer la meilleure solution et il faut employer une autre méthode.
À ne pas confondre
Indépendance linéaire. Elle concerne des vecteurs et se teste par une combinaison linéaire nulle. L'indépendance d'un matroïde est plus générale : dans le triangle, les éléments sont des arêtes et le critère est l'absence de cycle.
Indépendance en probabilité. Elle affirme qu'une information sur un événement ne modifie pas la probabilité d'un autre. Elle n'est pas une famille héréditaire de sous-ensembles munie de l'axiome d'échange ; deux lancers indépendants ne constituent donc pas, par ce seul fait, un matroïde.
Base d'un matroïde et base vectorielle. Une base de matroïde est tout ensemble indépendant maximal. Elle devient une base vectorielle seulement dans le matroïde issu de vecteurs et lorsque ces vecteurs engendrent l'espace considéré. Dans le triangle, une base est un couple d'arêtes.
Limites et pièges
L'hérédité ne suffit pas. Sur E = {a, b, c}, prenons tous les sous-ensembles de {a, b}, ainsi que {c}. La famille est héréditaire, mais ses ensembles maximaux {a, b} et {c} ont des tailles différentes. Aucun élément de {a, b} ne peut augmenter {c} : l'échange échoue, donc ce n'est pas un matroïde.
Maximal ne signifie pas maximum dans une famille quelconque. Sans l'axiome d'échange, un choix impossible à agrandir peut rester plus petit qu'un autre choix admissible. Il faut tester l'échange avant de conclure que toutes les bases ont même taille ou qu'un algorithme glouton est optimal.
Boucles et éléments parallèles. Un élément e est une boucle si {e} est dépendant : il n'entre dans aucune base. Deux éléments sont parallèles si chacun est indépendant seul mais si leur paire est dépendante. Il faut alors les traiter comme des possibilités concurrentes, pas comme deux gains cumulables.
Pour aller plus loin
Arbre couvrant : approfondir la base du matroïde graphique et son rôle pour relier tous les sommets sans cycle.
Espace vectoriel : replacer l'indépendance linéaire, les familles génératrices et les bases dans leur cadre algébrique.
Algorithme : situer la stratégie gloutonne parmi les procédures finies qui transforment des données en résultat.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres