Matroide: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Esempi |
|||
Riga 56:
* In uno [[spazio vettoriale]] o in una [[geometria proiettiva]] consideriamo un arbitrario [[arrangiamento di iperpiani]] ''H'', cioè un insieme finito di sottospazi di [[codimensione]] 1. Diciamo indipendente una collezione ''J'' di iperpiani di ''H'' tale che la intersezione dei suoi membri ha codimensione |''J''|, cioè uguale al numero degli iperpiani in ''J''. Denotiamo poi con ''I'' l'insieme delle collezioni indipendenti. La struttura (''H'',''I'') costituisce una matroide. La funzione di chiusura di tale matroide amplia una collezione ''A'' di iperpiani con tutti gli iperpiani che contengono l'intersezione degli iperpiani in ''A''. Queste matroidi sono linearmente o proiettivamente duali di quelle viste nei precedenti esempi concernenti rispettivamente vettori e punti proiettivi.
* Ricaviamo ora una matroide da un arbitrario [[multigrafo]] finito ''G'' = (''V'',''E'') (o più in particolare da un [[grafo]] finito). Diciamo indipendente ogni insieme di spigoli che non contiene alcun ciclo; nella [[teoria dei grafi]] un tale insieme di spigoli costituisce una cosiddetta [[Foresta (teoria dei grafi)|foresta]]. Se denotiamo con ''I'' la collezione di questi insiemi di spigoli, (''E'',''I'') forma una matroide degli indipendenti che viene chiamata '''matroide di cicli''' o anche '''matroide grafica'''. Le proprietà delle matroidi sono garantite dai seguenti fatti:
** L'insieme vuoto non consente di ottenere un ciclo.
** Togliendo spigoli da un insieme indipendente non si possono ottenere cicli.
| |||