Storia delle matroidi
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 1971 Jack 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.
Bibliografia[modifica | modifica wikitesto]
- 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.
