Matroide: differenze tra le versioni

Versione delle 17:06, 20 giu 2009

Versione attuale delle 16:52, 7 ago 2023

(32 versioni intermedie di 25 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.

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

# gode della '''proprietà di scambio di Mac Lane-Steinitz''': se ''a'' appartiene a cl(<math>Y \cup b</math>)\cl(Y) , allora b appartiene a cl(<math>Y \cup a</math>).

# Se ''E'' è infinito, si aggiunge la richiesta di '''carattere finito''': se ''a'' è in cl(''Y''), allora esiste un sottoinsieme finito ''X'' di ''Y'' tale che ''a'' è in cl(''X'').

Riga 40 ⟶ 38:

== Esempi ==

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

* Sia ''E'' un insieme e ''k'' un [[numero naturale]]. I sottoinsiemi di ''E'' con al più ''k'' elementi costituiscono gli insiemi indipendenti di una matroide su ''E''. Dimostriamo che valgono le proprietà degli insiemi indipendenti.

** Per qualsiasi scelta dell'intero naturale ''k'' l'insieme vuoto ha non più di ''k'' elementi;

** Ogni sottoinsieme di un insieme con al più ''k'' elementi contiene non più di ''k'' elementi;

** Se un sottoinsieme ''A'' ha cardinalità maggiore di quella di ''B'', allora ''A'' deve contenere qualche elemento ''x'' non contenuto in ''B''. Dato che ''B'' ha cardinalità al più ''k''&nbsp;&minus;−&nbsp;1, aggiungendo ''x''[ a ''B'' si mantiene la indipendenza.

* Se ''E'' è un arbitrario sottoinsieme finito di uno [[spazio vettoriale]] ''V'', allora si può definire una matroide ''M'' su ''E'' prendendo come insiemi indipendenti le collezioni di vettori in ''E'' [[indipendenza lineare|linearmente indipendenti]]. Vediamo che le proprietà delle matroidi degli indipendenti valgono.

** 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''| &le;≤ |''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.

** Consideriamo le basi della matroide, cioè le sottoforeste di ''G'' che contengono tutti i vertici del grafo e ricordiamo che un nodo isolato va considerato un albero. Una foresta con ''k'' è l'unione di |V|&nbsp;&minus;−&nbsp;''k'' alberi. Quindi una foresta con più spigoli ha meno alberi di una foresta con pochi spigoli. Ma qualche albero nella foresta più estesa deve contenere due vertici di due alberi diversi (e sconnessi) nella foresta più piccola. Dato che i due vertici fanno parte dell'albero nella foresta più estesa, entro questa foresta vi è un unico cammino che unisce i due vertici. Questo cammino deve contenere uno spigolo che non fa parte di nessuno dei due alberi della foresta più piccola; questo è lo spigolo che si può aggiungere alla foresta più ridotta.

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

[[ImmagineFile:Maximal_three-colorable.pngsvg|right|frame|Due tricolorazioni massimali con diversi numeri di nodi. Quella a sinistra non può essere ampliata perché il soloverticesolo 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''.

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 02620329370-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 01985356350-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 rappresentabiledei dipendenti]]

* [[Matroide deidelle dipendentibasi]]

* [[Matroide delledei basicircuiti]]

* [[Matroide dei circuitiflat]]

* [[Matroide deidegli flatiperpiani]]

* [[Matroide degli iperpianiinvadenti]]

* [[Matroide deglidei invadentinoninvadenti]]

* [[Matroide deidel noninvadentirango]]

* [[Matroide dele reticolo rangogeometrico]]

* [[Matroide e reticolo geometricoorientata]]

* [[Matroide orientatabinaria]]

* [[Matroide binariagrafica]]

* [[Matroide graficaregolare]]

* [[Matroide regolarerappresentabile]]

* [[Algoritmo greedy]]

*[[Matroide rappresentabile]]

* [[AlgoritmoDualità fra greedymatroidi]]

* [[DualitàConnettività fra matroidi]]

* [[ConnettivitàMinore di frauna matroidimatroide]]

* [[MinoreQuoziente di una matroidematroidi]]

* [[QuozienteConnessione in serie e parallelo di matroidi]]

* [[Connessione in serie e paralleloGlossario didelle matroidi]]

* [[GlossarioStoria delle matroidi]]

*[[Storia delle matroidi]]

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

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

*[[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:Matroid]]

[[de:Matroid]]

[[en:Matroid]]

[[es:Matroide]]

[[fr:Matroïde]]

[[hu:Matroid]]

[[nl:Matroïde]]

[[pl:Matroid]]

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

[[sr:Matroid]]

[[zh:拟阵]]