Matroide: differenze tra le versioni

Versione delle 10:54, 1 set 2015

Versione attuale delle 16:52, 7 ago 2023

(16 versioni intermedie di 11 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.

== Matroide degli indipendenti ==

Si definisce '''matroide degli indipendenti''' una coppia ''M'' = (''E'', ''I''), [[sistema di indipendenza]], nella quale ''E'' è un insieme detto '''insieme ambiente''' o '''insieme sostegno''' della matroide e ''I'' è una collezione di sottoinsiemi di ''E'' chiamati '''insiemi indipendenti''' della ''M'', i quali soddisfano le seguenti proprietà:

# L'[[insieme vuoto]] è indipendente.

Riga 24 ⟶ 23:

== Matroide della chiusura ==

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 40 ⟶ 38:

== Esempi ==

* Una matroide si dice '''semplice''' se ciascuno dei suoi sottoinsiemi di due elementi è indipendente.

Riga 53 ⟶ 50:

** Proprietà di scambio. se ''A'' e ''B'' sono insiemi di vettori linearmente indipendenti, essi sottendono sottospazi di ''V'' aventi rispettivamente dimensioni |''A''| e |''B''|. Se ogni vettore in ''A'' dipende linearmente dai vettori in ''B'', allora ogni vettore in ''A'' appartiene al sottospazio |''B''|-dimensionale generato dai vettori in ''B''. Quindi i vettori di ''A'' generano uno spazio di dimensione al più |''B''|, fatto che implica |''A''| ≤ |''B''|. Si osservi che ogni insieme di vettori di uno spazio vettoriale costituisce una matroide finitaria e che essa è finito-dimensionale se lo spazio vettoriale ha dimensioni finite.

* 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'' := (''AC'',''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.

* 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 [[Albero (grafo)|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.

Riga 71 ⟶ 68:

== Ulteriori definizioni e proprietà ==

Facciamo riferimento a una matroide degli indipendenti (''E'',''I''). Un sottoinsieme di ''E'' viene detto '''dipendente''' se non è indipendente. Un insieme dipendente minimale, cioè tale che ogni suo sottoinsieme proprio è indipendente viene chiamato '''circuito''' (questo termine proviene dall'esempio precedente della matroide grafica).

Riga 82 ⟶ 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.

== Ulteriori esempi ==

Poco dopo l'articolo fondante di Witney, si è scoperto che l'indipendenza algebrica è una indipendenza di matroide. Consideriamo un campo ''K'' e un suo [[campo di estensione]] ''L''. Un sottoinsieme finito ''x''₁, ..., ''x''_k di ''L'' si dice '''algebricamente indipendente''' se non esiste alcun polinomio non nullo ''f''(''t''₁, ..., ''t''_k), con coefficienti in ''K'', tale che ''f''(''x''₁, ..., ''x''_k) = 0. La coppia costituita dall'insieme ambiente ''L'' e dalla indipendenza algebrica è una matroide finitaria che viene chiamata '''matroide algebrica piena''' di ambiente ''L'' su ''K''. Il rango di tale matroide è uguale al [[grado di trascendenza]] di ''L'' su ''K''.

Si dice poi '''matroide algebrica''' ogni sottomatroide di una matroide algebrica piena.

Poco più tardiSuccessivamente si è trovato che la [[teoria dei trasversali]] fornisce un altro genere di matroide che ora viene chiamato '''[[matroide trasversale]]'''.

== Bibliografia ==

<!--

: ''Vedi anche in [[Storia delle matroidi]]''

== Cenni storici ==

* [[Neil White]] cur. (1986): ''Theory of matroids'', Cambridge University Press

:''Vedi anche articolo principale [[Storia delle matroidi]]''

* T. Cormen, C. Leiserson, R. Rivest (1990): ''Introduction to Algorithms''. Section 16.4, ''Theoretical foundations for greedy methods''. MIT Press, ISBN 0-262-03293-7.

-->

* [[Neil White]] cur. (1992): ''Matroid applications'', Cambridge University Press

* James G. Oxley. ''[https://web.archive.org/web/20070304044603/http://www.oup.com/us/catalog/general/subject/Mathematics/PureMathematics/?ci=0198535635 Matroid Theory]''. Oxford University Press, New York, 1992. ISBN 0-19-853563-5.

* [[Anders Björner]], [[Michel Las Vergnas]], [[Bernd Sturmfels]], [[Neil White]], [[Günter M.Ziegler]] (1993): ''Oriented matroids'', Cambridge University Press

* [[Joseph Kung]] (1996): ''Matroids'', pp. 157-184 in Michael Hazewinkel ed.: ''Handbook of Algebra'' vol. I, North Holland

== Voci correlate ==

* [[Matroide dei dipendenti]]

* [[Matroide delle basi]]

Riga 125 ⟶ 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).

{{Combinatoria}}

== Bibliografia ==

{{Controllo di autorità}}

: ''Vedi anche in [[Storia delle matroidi]]''

{{Portale|matematica}}

* [[Neil White]] cur. (1986): ''Theory of matroids'', Cambridge University Press

* T. Cormen, C. Leiserson, R. Rivest (1990): ''Introduction to Algorithms''. Section 16.4, ''Theoretical foundations for greedy methods''. MIT Press, ISBN 0-262-03293-7.

* [[Neil White]] cur. (1992): ''Matroid applications'', Cambridge University Press

* James G. Oxley. ''[http://www.oup.com/us/catalog/general/subject/Mathematics/PureMathematics/?ci=0198535635 Matroid Theory]''. Oxford University Press, New York, 1992. ISBN 0-19-853563-5.

* [[Anders Björner]], [[Michel Las Vergnas]], [[Bernd Sturmfels]], [[Neil White]], [[Günter M.Ziegler]] (1993): ''Oriented matroids'', Cambridge University Press

* [[Joseph Kung]] (1996): ''Matroids'', pp. 157-184 in Michael Hazewinkel ed.: ''Handbook of Algebra'' vol. I, North Holland

{{Portale|matematica}}

[[Categoria:Combinatoria]]

[[Categoria:Teoria delle matroidi| ]]