![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Cube-maximal-independence.svg/langit-640px-Cube-maximal-independence.svg.png&w=640&q=50)
Insieme indipendente massimale
Da Wikipedia, l'enciclopedia encyclopedia
Nella teoria dei grafi, un insieme indipendente massimale o insieme stabile massimale è un insieme indipendente che non è un sottoinsieme di nessun altro insieme indipendente. Cioè, è un insieme S tale che ogni spigolo del grafo ha almeno un estremo non in S e ogni vertice non in S ha almeno un vicino in S. Un insieme indipendente massimale è anche un insieme dominante nel grafo, e ogni insieme dominante che è indipendente deve essere indipendente massimale, così gli insiemi massimali indipendenti sono chiamati anche insiemi dominanti indipendenti. Un grafo può avere molti insiemi indipendenti massimali di dimensioni ampiamente variabili;[1] un insieme indipendente massimale più grande è chiamato insieme indipendente massimo.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Cube-maximal-independence.svg/320px-Cube-maximal-independence.svg.png)
Per esempio, nel grafo P3, un cammino con tre vertici a, b e c e due spigoli ab e bc, gli insiemi {b} e {a,c} sono entrambi massimamente indipendenti. L'insieme {a} è indipendente, ma non è massimamente indipendente, perché è un sottoinsieme dell'insieme indipendente più grande {a,c}. In questo stesso grafo, le cricche massimali sono gli insiemi {a,b} e {b,c}.
La locuzione "insieme indipendente massimale" si usa anche per descrivere sottoinsiemi massimali di elementi indipendenti in strutture matematiche diverse dai grafi, e in particolare negli spazi vettoriali e nei matroidi.