Matroide

In matematica, e in particolare in combinatoria, il termine matroide si applica a strutture che consentono di trattare una nozione di "indipendenza" che generalizza la indipendenza lineare degli spazi vettoriali. In effetti per talune di queste strutture è stato usato anche il termine struttura di indipendenza. Queste strutture riguardano, direttamente o indirettamente, collezioni di sottoinsiemi di un dato insieme ambiente le quali posseggono proprietà particolari.

Le matroidi si possono definire in una varietà sorprendentemente ampia di modi, ciascuno corrispondente a un tipo di entità (insiemi indipendenti, insiemi dipendenti, basi, insiemi chiusi o flats, operatore di chiusura, circuiti (insiemi dipendenti minimali), funzione rango, iperpiani, reticoli geometrici). Volendo essere formalmente più precisi, si individua una dozzina di specie di strutture che risultano criptomorfe; inoltre ciascuna di queste specie di strutture può essere definita servendosi di numerosi sistemi di assiomi. Questo fa supporre che nella teoria delle matroidi confluiscono molti concetti dotati di rilevante importanza.

Si deve inoltre segnalare subito che si trovano numerosi e svariati esempi di matroidi. Quindi la teoria delle matroidi permette di inquadrare in modo unitario una grandissima varietà di fatti matematici. In effetti il suo sviluppo ha contribuito in misura notevolissima a dare organicità alla combinatoria e a farla diventare un settore della matematica solidamente strutturato. Infine va segnalato che essa presenta collegamenti con numerosi settori della matematica, sia "pura" sia "applicata" (algebra, geometria, ottimizzazione, ricerca operativa, teoria e pratica degli algoritmi) e anche con discipline più applicative come l'ingegneria strutturale e la chimica molecolare.

In questo articolo capofila introduciamo le matroidi in due modi, fondati rispettivamente sulle nozioni di insieme indipendente e di operatore di chiusura. Si tratta di due definizioni relativamente semplici e in grado di dare buona evidenza ad alcuni dei tipi di entità che caratterizzano le matroidi.