Matroïde uniforme

On considère un ensemble ${\displaystyle E}$ = {1, 2, 3, 4} à quatre éléments. En prenant ${\displaystyle r}$=2, on obtient un matroïde uniforme si on déclare que les ensembles indépendants sont les sous-ensembles à au plus 2 éléments, à savoir : l'ensemble vide, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

Le matroïde uniforme ${\displaystyle U_{n}^{r}}$ est défini comme un ensemble ${\displaystyle E}$ à ${\displaystyle n}$ éléments. Un sous-ensemble de ${\displaystyle E}$ est indépendant si et seulement s'il contient au plus ${\displaystyle r}$ éléments. ${\displaystyle r}$ est appelé le rang du matroïde.

Un sous-ensemble de ${\displaystyle E}$ est une base s'il a exactement ${\displaystyle r}$ éléments. Un sous-ensemble de ${\displaystyle E}$ est un circuit s'il a exactement ${\displaystyle r+1}$ éléments. Le rang d'un sous-ensemble ${\displaystyle X}$ est ${\displaystyle \min(\mathrm {card} (X),r)}$.

• Portail des mathématiques