Matroid

Från Wikipedia
Hoppa till: navigering, sök

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

Definition[redigera | redigera wikitext]

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

Oberoende mängder[redigera | redigera wikitext]

En matroid är ett par som består av en ändlig mängd och en mängd bestående av delmängder till som uppfyller följande krav:

  1. Om och är
  2. Om samt att finns det så att

kallas grundmängd och element i kallas oberoende mängder.

Kretsar[redigera | redigera wikitext]

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:

  1. Om och är
  2. Om och och innehåller en krets till

Exempel[redigera | redigera wikitext]

Linjär Algebra[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Isomorfa matroider[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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

Ternära matroider[redigera | redigera wikitext]

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

Regelbundna matroid[redigera | redigera wikitext]

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

Referenser[redigera | redigera wikitext]

  • Oxley, James, What is a matroid?, 2007, Department of Mathematics, Louisiana State University.