Storia delle matroidi
# 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.

