Matroid
En matroid är inom kombinatoriken en struktur som abstraherar grunddragen hos begreppet linjärt oberoende.

Definition 
Det finns flera ekvivalenta sätt att definiera en matroid.

Oberoende mängder 
En matroid  är ett par  där  är en ändlig mängd (kallad grundmängden) och  är en familj av delmängder (kallade de oberoende mängderna) till  som uppfyller följande krav:
 
 Varje delmängd av en oberoende mängd är oberoende, det vill säga om  och  så är 
 Om  är två oberoende mängder och , så finns  sådant att

Kretsar 
En krets är en minimal beroende mängd till en matroid. 
Mängden  som består av samlingen kretsar till en matroid  har följande egenskaper: 
 
 Om   och  så är  
 Om   och  och  innehåller  en krets till

Exempel

Linjär Algebra
Låt matrisen

Låt sedan  där 1, 2, 3, 4 syftar på kolonnerna till .
Bilda sedan  av alla delmängder till  som inte är linjärt beroende.
Då fås att 
 är då en matroid som speciellt kallas för en vektormatroid till

Grafteori

Bilda en mängd av samtliga bågar i 

Bilda sedan en mängd av alla cykler i  , det vill säga vägar från en nod som återgår till noden.

Då kan  beskrivas med en kretsmatroid  som har grundmängd  och där  innehåller samtliga kretsar till .

Typer av matroider

Isomorfa matroider
En matroid  med en grundmängd innehållande två distinkta element 

kan ha följande samlingar av oberoende mängder:

Om man jämför  och  ser man att dessa matroider har samma struktur.  och  kallas isomorfa och skrivs .

Binära matroider
En matroid som kan representeras över en ändlig kropp med två element kallas för en binär matroid.

Ternära matroider
En matroid som kan representeras över en ändlig kropp med tre element kallas för en ternär matroid.

Regelbundna matroid
En matroid som kan representeras över alla kroppar kallas för en regelbunden matroid.

Referenser
 Oxley, James, What is a matroid?, 2007, Department of Mathematics, Louisiana State University.
Kombinatorik
En matroid är inom kombinatoriken en struktur som abstraherar grunddragen hos begreppet linjärt oberoende . Definition Det finns flera ekvivalenta sätt att definiera en matroid . Oberoende mängder En matroid är ett par där är en ändlig mängd ( kallad grundmängden ) och är en familj av delmängder ( kallade de oberoende mängderna ) till som uppfyller följande krav : Varje delmängd av en oberoende mängd är oberoende , det vill säga om och så är Om är två oberoende mängder och , så finns sådant att Kretsar En krets är en minimal beroende mängd till en matroid . Mängden som består av samlingen kretsar till en matroid har följande egenskaper : Om och så är Om och och innehåller en krets till Exempel Linjär Algebra Låt matrisen Låt sedan därsyftar på kolonnerna till \ . Bilda sedan av alla delmängder till som inte är linjärt beroende . Då fås att är då en matroid som speciellt kallas för en vektormatroid till Grafteori Bilda en mängd av samtliga bågar i Bilda sedan en mängd av alla cykler i , det vill säga vägar från en nod som återgår till noden . Då kan beskrivas med en kretsmatroid som har grundmängd och där innehåller samtliga kretsar till \ . Typer av matroider Isomorfa matroider En matroid med en grundmängd innehållande två distinkta element kan ha följande samlingar av oberoende mängder : Om man jämför och ser man att dessa matroider har samma struktur . och kallas isomorfa och skrivs \. Binära matroider En matroid som kan representeras över en ändlig kropp med två element kallas för en binär matroid . Ternära matroider En matroid som kan representeras över en ändlig kropp med tre element kallas för en ternär matroid . Regelbundna matroid En matroid som kan representeras över alla kroppar kallas för en regelbunden matroid . Referenser Oxley , James , What is a matroid ? , Department of Mathematics , Louisiana State University . Kombinatorik