Matroide: differenze tra le versioni

Versione delle 23:22, 19 apr 2020

Versione attuale delle 16:52, 7 ago 2023

(4 versioni intermedie di 3 utenti non mostrate)

Riga 1:

In [[matematica]], e in particolare in [[combinatoria]], il termine '''matroide''' si applica a strutture, soprattutto finite, che consentono di trattare una nozione di "indipendenza" che generalizza la [[indipendenza lineare]] degli [[spazio vettoriale|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 [[criptomorfismo|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. <!-- (that is one way we know the concept is important!); -->

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.

Riga 25:

Definiamo ora le matroidi mediante un operatore di chiusura, cioè considerando un insieme ambiente e una [[funzione di chiusura|funzioni di chiusura]] su di esso che possiede particolari proprietà.

Definiamo come ''matroide della chiusura'' ununa coppia (''E'',cl) dove ''E'' è un [[insieme finito]] e cl una funzione del tipo '''P'''(''E'') ^mapsto; '''P'''(''E'') che soddisfa le seguenti condizioni, per arbitrari elementi ''a'', ''b'' di ''E'' e per arbitrari sottoinsiemi ''Y'', ''Z'' di ''E'':

# cl è un [[operatore di chiusura]] su ''E''. <!--is an [[abstract closure]] operator.-->

Riga 52:

* Consideriamo una [[matrice]] ''A'' con entrate in un [[campo (matematica)|campo]], l'insieme delle sue colonne ''C'' e la collezione ''D'' degli insiemi di colonne che costituiscono insiemi di vettori linearmente dipendenti. La struttura ''M'' := (''C'',''D'') è una matroide chiamata '''matroide delle colonne''' di ''A''; a sua volta ''A'' si dice '''rappresentare''' ''M''. Le matroidi di colonne sono le rappresentazioni delle matroidi vettoriali, sono in tutto equivalenti a esse e possono risultare utili per calcoli effettivi.

* In una [[geometria proiettiva]] si scelga un arbitrario insieme ''E'' di punti e lo si munisca della funzione di chiusura costituita dalla chiusura proiettiva ristretta a ''E''. In tal modo si ottiene una matroide. Come caso particolare si può prendere per ''E'' un sottoinsieme di una geometria affine e ancora più in particolare un sottoinsieme di uno [[spazio euclideo]].

* 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.

Riga 78:

Se ''A'' è un sottoinsieme di ''E'', allora si può definire una matroide degli indipendenti su ''A'' assumendo come suoi insiemi indipendenti i sottoinsiemi indipendenti nella ''M'' che sono contenuti nella ''A''. Questo consente di parlare di '''sottomatroidi''' e di assegnare un rango a ogni sottoinsieme di ''E''.

Se ''M''=(''E'',''I'') è una matroide finita e ''B'' denota la collezione delle sue basi, cioè dei suoi insiemi indipendenti massimali, si dice ''matroide duale''' della ''M'' e si denota con ''M''*, la matroide che ha come insieme ambiente lo stesso ''E'' e come collezione delle basi la collezione dei sottoinsiemi che sono complemetaricomplementari di qualche base in ''B''. Un sottoinsieme di ''E'' è indipendente in ''M''* se e solo se è incluso nel complemento di qualche base di ''M'', o equivalentemente se e solo se il suo complemento genera ''M''. Si verifica facilmente che ''M''* è proprio una matroide.

Vengono anche proposte le duali di matroidi infinite, ma le loro definizioni incontrano delle difficoltà e il problema della dualità tra queste matroidi non è ancora stato risolto in modo soddisfacente.

Riga 123:

== Collegamenti esterni ==

* [http://mathworld.wolfram.com/Matroid.html Matroid] in [[MathWorld]]

* [http://planetmath.org/encyclopedia/Matroid.html Matroids] {{Webarchive|url=https://web.archive.org/web/20051103012545/http://planetmath.org/encyclopedia/Matroid.html |date=3 novembre 2005 }} in [[PlanetMath]]. Presenta molte altre equivalenti definizioni di matroide.

* [https://web.archive.org/web/20060202005537/http://www.ms.uky.edu/~pagano/Matridx.htm Matroids and Signed Graphs] di Steven R. Pagano

*[https://web.archive.org/web/20060211053237/http://members.aol.com/matroids/ Matroid theory] di Sandra Kingan (ampia sitografia).