Matroide: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
CruccoBot (discussione | contributi)
m Bot: Aggiungo: sr:Matroid
IagaBot (discussione | contributi)
m Bot: Correzione di uno o più errori comuni
Riga 21:
Procediamo ora a definire alcuni oggetti con proprietà specifiche in una matroide degli indipendenti ''M'' = (''E'', ''I'').
<br/>Un sottoinsieme indipendente massimale viene detto '''base''' della ''M''. Un sottoinsieme di ''E'' che non è indipendente viene detto '''dipendente'''. Un sottoinsieme dipendente minimale viene chiamato '''circuito'''.
<br/>Si definisce inoltre come '''operatore di chiusura''' di una matroide finitaria come la funzione del tipo cl : '''P'''(''E'') &mapsto: '''P'''(''E'')''M'' la quale applicata a un generico sottoinsieme ''A'' di ''E'' lo amplia aggiungendogli tutti gli elementi ''x'' in ''E'' ma non in ''A'' tali che esiste un circuito ''C'' di ''M'' che contiene ''x'' ed è contenuto nell'unione di ''A'' ed {''x''}. Si vede facilmente che tale funzione è effettivamente una [[funzione di chiusura]], cioè che si tratta di una [[endofunzione di booleano]] [[funzione ampliante|ampliante]], [[endofunzione di booleano monotona|monotona]] e [[endofunzione idempotente|idempotente]].
 
== Matroide della chiusura ==