Matroide: differenze tra le versioni

Versione delle 14:23, 5 ott 2010

Versione attuale delle 16:52, 7 ago 2023

(27 versioni intermedie di 21 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]] ede a farla diventare un settore della matematica solidamente strutturato. Infine va segnalato che essa presenta collegamenti con numerosi settori della matematica, sia "pura" chesia "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.

# Ogni sottoinsieme di un indipendente è indipendente; in altre parole ''I'' è una collezione chiusa rispetto alla inclusione; questa proprietà talora è detta '''ereditarietà dell'indipendenza'''.

# SaSe ''A'' e ''B'' sono due insiemi indipendenti e ''A'' possiede più elementi di ''B'', allora esiste un elemento in ''A'' ma non in ''B'' tale che aggiunto a ''B'' porta a un altro insieme indipendente; questa proprietà è detta '''proprietà di scambio'''.

Se l'ambiente è finito, le richieste precedenti bastano per la definizione, ma se è infinito servono altre condizioni piuttosto complesse; qui non affrontiamo questi problemi, ma ci limitiamo a menzionare la proprietà che caratterizza una '''matroide finitaria''':

* Un sottoinsieme infinito di ''E'' è indipendente se ogni suo sottoinsieme finito è indipendente; questa proprietà è detta '''carattere finito'''.

Una matroide è detta '''finito dimensionale''' o di '''rango finito''' se esiste un numero naturale tale che non esiste alcun insieme indipendente con cardinalità superiore ada esso.

Le prime due proprietà richieste per le matroidi degli indipendenti sono molto semplici, ma la motivazione della terza proprietà non è tanto evidente. Essa implica che, dati due insiemi indipendenti della stessa cardinalità, ogni elemento di uno dei due si può sostituire con qualche elemento dell'altro in modo da ottenere un altro insieme indipendente: questa conseguenza giustifica il termine "scambio". Per chiarire meglio la portata del terzo assioma è opportuno esaminare qualche esempio significativo.

Riga 21 ⟶ 20:

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'' ede {''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 ==

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 51 ⟶ 48:

** L'insieme vuoto è vacuamente un insieme di vettori linearmente indipendenti.

** Un sottoinsieme di un insieme di vettori linearmente indipendenti non può presentare una dipendenza lineare.

** Proprietà di scambio. se ''A'' e ''B'' sono insiemi di vettori linearmente indipendenti, essi sottendono sottospazi di ''V'' aventirispettivamenteaventi 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 delladelle 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 ada 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 66 ⟶ 63:

Si osservi che in questo modo si ottiene una matroide anche da un multigrafo infinito; una tale matroide è finitaria perché tutti i cicli sono finiti; inoltre essa è finito-dimensionale se il numero dei vertici è finito, anche se il numero degli spigoli è infinito).

[[File:Maximal_three-colorable.pngsvg|right|frame|Due tricolorazioni massimali con diversi numeri di nodi. Quella a sinistra non può essere ampliata perché il solo vertice rimanente è adiacente a nodi di tutti i tre colori.]]

Consideriamo, all'opposto, una situazione che non porta ada una matroide. Sia ''E'' l'insieme dei nodi di un grafo e chiamiamo insiemi di nodi indipendenti quelli che possono essere colorati con non più di tre colori senza coincidenze fra nodi adiacenti. L'insieme vuoto soddisfa alla condizione e ogni sottoinsieme di nodi tricolorabile è tricolorabile; non vale invece la proprietà di scambio, in quanto si possono avere due sottografi massimali tricolorabili con diversi numeri di nodi, come mostrato nella figura alla destra.

== 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).

Diciamo che un sottoinsieme ''A'' di ''E'', '''genera''' (''spans'') ''M'' se la sua chiusura è l'intero ''E''.

Un insieme indipendente massimale, cioè che non è propriamente contenuto in alcun altro independenteindipendente, viene chiamato '''base''' (questo termine proviene dal precedente esempio sullo spazio vettoriale). Un fatto importante è che tutte le basi di una matroide hanno lo stesso numero di elementi; tale numero viene detto '''rango''' della ''M''. In generale, invece, i circuiti di ''M'' possono avere cardinalità differenti.

Nel precedente esempio della matroide dell'algebra lineare, una base è anche una [[base (algebra lineare)|base nel senso dell'algebra lineare]] del sottospazio generato da ''E'' e un circuito è un insieme minimale di vettori dipendenti di ''E''. Nella matroide dei cicli una base corrisponde a una [[sottoalbero massimale|sottoforesta massimale]] del grafo ''G'' e i circuiti sono cicli semplici del grafo. Nell'esempio nel quale gli insiemi di al più ''k'' elementi sono gli indipendenti, base è ogni sottoinsieme di ''E'' con ''k'' elementi e circuito ogni sottoinsieme di ''k'' + 1 elementi.

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 ada 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| ]]

[[ca:Matroide]]

[[de:Matroid]]

[[en:Matroid]]

[[es:Matroide]]

[[fr:Matroïde]]

[[hu:Matroid]]

[[nl:Matroïde]]

[[pl:Matroid]]

[[ru:Матроид]]

[[sk:Matroid]]

[[sr:Matroid]]

[[zh:拟阵]]