Matroide del rango
In combinatorica si dice matroide del rango una struttura della forma (E,r), dove E è un insieme ed r una funzione che ha come dominio l'insieme delle parti P(E), come codominio un insieme della forma {0,1,2,...,k} e gode delle seguenti proprietà
- r(A) ≤ |A| per tutti i sottoinsiemi A di E.
- Se A e B sono sottoinsiemi di E con A ⊆ B, allora r(A) ≤ r(B) (proprietà di isotonia).
- Per ogni coppia di sottoinsiemi di E A e B, abbiamo r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B).
Diciamo insieme indipendente di una matroide del rango (E,r) ogni J sottoinsieme di E tale che sia r(J) = |J|. Se I denota la collezione di tali insiemi, si dimostra che (E,I) è una matroide degli indipendenti.