Matroide

Matroide

Matroïde

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é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).

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 dit représentables. 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.

Il existe différentes manières, toutes équivalentes, de définir (axiomatiquement) un 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 MacLane–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 (S, C) tels que C est une collection de sous-ensembles de S fermée par-rapport à la différence symétrique.

Donnons maintenant la définition selon Withney :

Sommaire

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 s'il vérifie 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 X et Y sont deux sous-ensembles de S appartenant tous les deux à I et tels que Y a plus d'éléments que X, alors il existe au-moins un élément propre à Y (dans Y mais pas dans X) tel que X union cet élément soit encore dans I.

Les sous-ensembles de S appartenant à I sont appelés les indépendants. 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érieure à k.

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 (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.

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.

Le polytope des indépendants : polymatroïde

A 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. On appelle polymatroïde, tout polytope qui est le polytope des indépendants d'un matroïde.

Voir aussi

Articles connexes

  • Portail des mathématiques Portail des mathématiques
  • Portail de la programmation informatique Portail de la programmation informatique
Ce document provient de « Matro%C3%AFde ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Matroide de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • matroïde — [matʀɔid] n. m. ÉTYM. Après 1935; angl. matroid, 1935, Withney; p. ê. de matrix « matrice ». ❖ ♦ Math. Objet mathématique, couple formé par un ensemble fini et un ensemble non vide de parties de cet ensemble, vérifiant certains axiomes. || « La… …   Encyclopédie Universelle

  • Matroïde — 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éjà au niveau du vocabulaire : indépendant, base …   Wikipédia en Français

  • Matroide — La combinatoria, una rama de las matemáticas, llama matroide a una estructura que representa la esencia de independencia que generaliza la independencia lineal en vectores espaciales. Hay muchas maneras equivalentes de definir a una matroide y… …   Wikipedia Español

  • Matroid — Ein Matroid (n.) ist eine mathematische Struktur mit deren Hilfe der Begriff der (linearen) Unabhängigkeit verallgemeinert wird. Matroide sind in vielen Bereichen der Kombinatorik (z. B. kombinatorischen Optimierung, diskrete kombinatorische… …   Deutsch Wikipedia

  • Unabhängigkeitssystem — Ein Unabhängigkeitssystem ist in der Kombinatorik eine Verallgemeinerung der mathematische Struktur des Matroides. Ein Unabhängigkeitssystem (E,U) besteht aus einer endlichen Grundmenge E und einem darüber definierten nicht leeren Mengensystem U …   Deutsch Wikipedia

  • Kombinatorik — Die Kombinatorik ist eine Teildisziplin der Mathematik, die sich mit endlichen oder abzählbar unendlichen diskreten Strukturen beschäftigt und deshalb auch dem Oberbegriff Diskrete Mathematik zugerechnet wird. Beispiele sind Graphen… …   Deutsch Wikipedia

  • Martin Aigner — (2004) Martin Aigner (* 28. Februar 1942 in Linz) ist ein österreichischer Mathematiker. Aigner legte in seiner Heimatstadt Linz die Matura ab. Nach dem Studium der Mathematik mit den Nebenfächern Physik und Philosophie an der Universität Wien …   Deutsch Wikipedia

  • Richard Rado — 1976 Richard Rado (* 28. April 1906 in Berlin; † 23. Dezember 1989 in Reading) war ein deutscher Mathematiker, der sich vor allem mit Kombinatorik beschäftigte. Er ist nicht mit dem ungarischen Mathematiker Tibor Radó verwandt. R …   Deutsch Wikipedia

  • Acyclique — Graphe acyclique Un graphe acyclique est un graphe ne contenant aucun cycle. Ce terme concerne les graphes orientés puisque les graphes non orienté sans cycle sont les forêts (chaque composante connexe est un arbre). Afin de distinguer les cycles …   Wikipédia en Français

  • Cryptomorphisme — En mathématiques, deux objets, et plus spécialement deux systèmes d axiomes ou leurs sémantiques sont dits cryptomorphes en français[réf. nécessaire] (cryptomorphic en anglais) s ils sont équivalents mais pas de manière évidente. C est une… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”