Matroïde

Een matroïde is een eindige verzameling met een 'onafhankelijkheidsstructuur' die bepaalt welke deelverzamelingen van elkaar onafhankelijk zijn.

GeschiedenisBewerken

Een belangrijk begrip uit de lineaire algebra is lineaire onafhankelijkheid. Intuïtief is een vector in een vectorruimte onafhankelijk van andere vectoren, als deze vector niet in het opspansel van deze andere vectoren ligt.

In de jaren 30 werd het idee van onafhankelijkheid gegeneraliseerd door Hassler Whitney[1]. Hij bepaalde de belangrijkste eigenschappen van een verzameling onafhankelijke vectoren, en nam deze vervolgens als axioma’s. Hierdoor was hij in staat in een willekeurige (eindige) verzameling de deelverzamelingen vast te stellen, waarvan de elementen onafhankelijk van elkaar zijn. De complexe structuur van een vectorruimte had hij hiervoor niet meer nodig.

Zijn idee is vergelijkbaar met het idee achter een topologische ruimte. Deze generaliseren de open verzamelingen van de reële rechte naar willekeurige verzamelingen door de eigenschappen hiervan als axioma’s aan te nemen.

DefinitiesBewerken

Een matroïde kan op verschillende manier worden gedefinieerd. Alle onderstaande definities zijn equivalent met elkaar[2].

Onafhankelijkheidsaxioma'sBewerken

Een matroïde is een geordend paar  , met   een eindige verzameling en   een collectie deelverzamelingen van   die voldoet aan de volgende axioma's:

  •  
  • Als   en  , is  .
  • Als   en  , bestaat er een   waarvoor geldt:  .

Een element van   wordt een onafhankelijke deelverzameling van   genoemd.

Basisaxioma’sBewerken

Laat   een eindige verzameling zijn. Een collectie   van deelverzamelingen van   heet een verzameling van bases van E, als voldaan is aan:

  •   is niet leeg.
  • Als  , bestaat er voor alle   een  , zodat  .

Laat dan   bestaan uit alle deelverzamelingen die bevat zijn in een basis. Dan is   een matroïde. De elementen van   zijn dan de maximaal onafhankelijke deelverzamelingen van  .

Circuitaxioma’sBewerken

Laat   een eindige verzameling zijn. Een collectie   van deelverzamelingen van   heet een verzameling van circuits van E, als voldaan is aan:

  •  .
  • Als   en  , is  .
  • Als   en  , en  , dan bestaat er een  , zodat  .

Laat dan   bestaan uit alle deelverzamelingen die geen enkel circuit bevatten. Dan is   een matroïde. De elementen van   zijn dan de minimaal afhankelijke deelverzamelingen van  .

VoorbeeldenBewerken

Lineaire matroïdenBewerken

Zoals eerder vermeld, zijn matroïden ontwikkeld om lineaire onafhankelijkheid te veralgemenen. Het meest voor de hand liggende voorbeeld van een matroïde is daarom terug te vinden in de lineaire algebra.

Laat   een eindige verzameling vectoren zijn uit een vectorruimte over een willekeurig lichaam. Laat dan   bestaan uit alle deelverzamelingen van   die een onafhankelijk stel vectoren vormen. Dan is   een lineaire matroïde.

Matroïden zijn dus uitermate geschikt om onafhankelijkheid in lineaire ruimtes over eindige lichamen te bestuderen.

Fano-matroïdeBewerken

Beschouw de lineaire matroïde op  . Deze matroïde wordt naar de Italiaanse wiskundige Gino Fano de Fano-matroïde genoemd.

Grafische matroïdenBewerken

Laat   een (eindige) graaf zijn, en laat   bestaan uit verzamelingen kanten, die samen een cykel vormen. Er kan aangetoond worden dat   voldoet aan de circuitaxioma’s. De matroïde die zo ontstaat noemen we een grafische matroïde.

Uniforme matroïdenBewerken

Neem  , en laat   bestaan uit deelverzamelingen van   met maximaal   elementen.   voldoet duidelijk aan de onafhankelijkheidsaxioma’s, en dus is   een matroïde, die we een uniforme matroïde noemen. Een uniforme matroïde wordt meestal genoteerd als  .

ReferentiesBewerken

  1. Whitney, H. (1935). On the Abstract Properties of Linear Dependence. American Journal of Mathematics, 57(3), 509-533
  2. Oxley, J. (1992). Matroid Theory, New York: Oxford University Press.