Matroïde

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een matroïde is een eindige verzameling met een 'onafhankelijkheidsstructuur', die bepaalt welke deelverzamelingen onafhankelijk zijn, en welke niet.

Geschiedenis[bewerken]

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 om in een willekeurige (eindige) verzameling vast te stellen, waarvan de deelverzamelingen uit elementen bestaan, die 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 veralgemenen de open verzamelingen van de reële rechte naar willekeurige verzamelingen door de eigenschappen hiervan als axioma’s aan te nemen.

Definities[bewerken]

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

Onafhankelijkheidsaxioma's[bewerken]

Een matroïde is een geordend paar (E,\mathcal{I}), waarbij E een eindige verzameling is, en \mathcal{I} een collectie is van deelverzamelingen van E, die voldoet aan de volgende axioma's:

  • \empty \in \mathcal{I}.
  • Als J \in \mathcal{I} en I \subset J, dan I \in \mathcal{I}.
  • Als I,J \in \mathcal{I} en |I| < |J|, dan \exists e \in J: I \cup \{ e \} \in \mathcal{I}.

Een element van \mathcal{I} noemen we een onafhankelijke deelverzameling van E.

Basisaxioma’s[bewerken]

Laat E een eindige verzameling zijn, en \mathcal{B} een collectie van deelverzamelingen van E, die voldoet aan:

  • \mathcal{B} is niet leeg.
  • Als B_{1}, B_{2} \in \mathcal{B}, dan bestaat er voor alle e \in B_{1} een f \in B_{2}, zodat (B_{1}\setminus e) \cup f \in \mathcal{B}.

Dan noemen we \mathcal{B} en verzameling van bases van E. Laat dan \mathcal{I} bestaan uit alle deelverzamelingen die bevat zijn in een basis. Dan is (E,\mathcal{I}) een matroïde. De elementen van \mathcal{B} zijn dan de maximaal onafhankelijke deelverzamelingen van E.

Circuitaxioma’s[bewerken]

Laat E een eindige verzameling zijn, en \mathcal{C} een collectie van deelverzamelingen van E, die voldoet aan:

  • \empty \not\in \mathcal{C}.
  • Als C_{1}, C_{2} \in \mathcal{C}, en C_{1}\subset C_{2}, dan C_{1} = C_{2}.
  • Als C_{1},C_{2} \in \mathcal{C} en C_{1} \not= C_{2}, en e \in C_{1} \cap C_{2}, dan bestaat er eenC_{3}\in \mathcal{C}, zodat C_{3} \subset (C_{1}\cup C_{2}) \setminus e.

Dan noemen we \mathcal{C} en verzameling van circuits van E. Laat dan \mathcal{I} bestaan uit alle deelverzamelingen die geen enkel circuit bevatten. Dan is (E,\mathcal{I}) een matroïde. De elementen van \mathcal{C} zijn dan de minimaal afhankelijke deelverzamelingen van E.

Voorbeelden[bewerken]

Lineaire matroïden[bewerken]

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 E een eindige verzameling vectoren zijn uit een vectorruimte over een willekeurig lichaam. Laat dan \mathcal{I} bestaan uit alle deelverzamelingen van E die een onafhankelijk stel vectoren vormen. Dan is (E, \mathcal{I}) een lineaire matroïde.

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

Fano-matroïde[bewerken]

Beschouw de lineaire matroïde op E = \mathbb{F}_{2}^{3} - 0. Deze matroïde wordt naar de Italiaanse wiskundige Gino Fano de Fano-matroïde genoemd.

Grafische matroïden[bewerken]

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

Uniforme matroïden[bewerken]

Neem E = \{1, 2, \ldots, n \}, en laat \mathcal{I} bestaan uit deelverzamelingen van E met maximaal k \leq n elementen. \mathcal{I} voldoet duidelijk aan de onafhankelijkheidsaxioma’s, en dus is (E, \mathcal{I}) een matroïde, die we een uniforme matroïde noemen. Een uniforme matroïde wordt meestal genoteerd als U_{k,n}.

Referenties[bewerken]

  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.