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.
Storia
Il concetto di matroide fu introdotto, per il caso finito, da Hassler Whitney nel 1935 con un articolo dal titolo On the abstract properties of linear dependence. Per questa nozione sono stati usati anche i termini "struttura di indipendenza" (da Richard Rado, nel caso di matroide finitaria) e di "pregeometria combinatoria" (da Gian-Carlo Rota), sebbene ora questi termini, soprattutto il secondo, sono poco usati. Rota inoltre chiamava "geometria combinatoria" quella che più comunemente viene detta matroide semplice.
Gli interessi che muovevano i primi studiosi delle matroidi riguardavano prevalentemente insiemi di vettori, grafi e matroidi algebriche; un po' più tardi è nato, soprattutto per merito di Richard Rado, l'interesse per le matroidi trasversali.
Solo nel 1971Jack Edmonds ha collegato le matroidi pesate con gli algoritmi greedy nel suo articolo dal titolo "Matroids and the greedy algorithm".
Bernhard Korte e Laszlo Lovász, a partire dal 1981, hanno generalizzato queste idee introducendo le strutture chiamate greedoids, che consentono di individuare classi di problemi più estese che si possono risolvere con algoritmi greedy.
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à:
Ogni sottoinsieme di un indipendente è indipendente; in altre parole I è una collezione chiusa rispetto alla inclusione; questa proprietà talora è detta ereditarietà dell'indipendenza.
Se 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 a 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).
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.
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 e {x}. Si vede facilmente che tale funzione è effettivamente una funzione di chiusura, cioè che si tratta di una endofunzione di booleanoampliante, monotona e idempotente.
Matroide della chiusura
Definiamo ora le matroidi mediante un operatore di chiusura, cioè considerando un insieme ambiente e una funzioni di chiusura su di esso che possiede particolari proprietà.
Definiamo come matroide della chiusura una 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:
gode della proprietà di scambio di Mac Lane-Steinitz: se a appartiene a cl()\cl(Y), allora b appartiene a cl().
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).
Si dimostra che una matroide di chiusura è logicamente equivalente a una matroide degli indipendenti finitaria il cui operatore di chiusura definito sugli insiemi indipendenti coincide con l'operatore di chiusura introdotto con la definizione.
A questo punto sappiamo che quando si deve trattare con una matroide, si ha la possibilità di scegliere se definirla precisando il suo operatore di chiusura, oppure mediante i suoi insiemi indipendenti; questa seconda possibilità è spesso desiderabile, specialmente in applicazioni di natura geometrica.
Osserviamo che, all'opposto, l'operatore di chiusura di uno spazio topologico tendenzialmente non possiede la proprietà di scambio (2), mentre possiede una diversa proprietà caratteristica.
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−1, aggiungendo x a B si mantiene la indipendenza.
Se E è un arbitrario sottoinsieme finito di uno spazio vettorialeV, allora si può definire una matroide M su E prendendo come insiemi indipendenti le collezioni di vettori in Elinearmente 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 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 matriceA con entrate in un 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 rappresentareM. 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 iperpianiH, 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 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|−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).
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 a 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 indipendente, 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 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 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 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 complementari 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 estensioneL. Un sottoinsieme finito x1, ..., xk di L si dice algebricamente indipendente se non esiste alcun polinomio non nullo f(t1, ..., tk), con coefficienti in K, tale che f(x1, ..., xk) = 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.
Hassley Whitney (1935): On the Abstract Properties of Linear Dependence. Amer. J. Math., 57 pp. 509-533.
Saunders Mac Lane (1936): Some interpretation of abstract linear dependence in terms of projective geometry, Amer. J. Math., 58 pp. 236-240
Richard Rado (1942): A theoren on independence relations, Quart. J. Math. Oxford, 42 pp. 107-109.
Robert Dilworth (1944): Dependence relations in a semimodular lattice, 11 pp. 575-587
Joseph Bernard Kruskal (1956): On the shortest spanning tree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc., 7, pp. 48-50
Jack Edmonds (1971): Matroids and the Greedy Algorithm, Mathematical Programming, 1 pp. 125-136.
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
