Sistema di indipendenza

Un sistema di indipendenza è una famiglia non vuota di insiemi in cui, se A appartiene alla famiglia e B è sottoinsieme di A, allora anche B appartiene alla famiglia. Il nome suggerisce immediatamente di chiamare indipendenti gli insiemi della famiglia e, ovviamente, dipendenti gli altri.

Formalmente possiamo dire che:

$A\in F\land B\subset A\Rightarrow B\in F$

Un grafo può essere visto come un sistema d'indipendenza in cui solo lati e vertici costituiscono gli insiemi indipendenti.

Nello studio degli insiemi di indipendenza si introduce anche la nozione di rango ossia la cardinalità del massimo insieme di indipendenza contenuto in un insieme dipendente.

Se abbiamo un insieme F = {a,b,c,d,e} e poniamo che il sistema di indipendenza per ipotesi sia A = {a,d,e}, nell'insieme di dipendenza B = {b,d,e} abbiamo due elementi che fanno parte dell'insieme di indipendenza. La nozione di rango applicata all'insieme B, rango(B) restituisce il valore 2 che indica la cardinalità di due elementi presenti in B che fanno parte dell'insieme di indipendenza A.

Esistono molti algoritmi che studiano l'ottimizzazione del valore di cardinalità cercano di ottenere il numero massimo di elementi dell'insieme di indipendenza.