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 miniatyr|höger|En sammanhängde graf med fyra noder, betecknade A, B, C och D, och sju noder, betecknade 1-7. 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. Kategori:Kombinatorik