Öppna huvudmenyn

DefinitionRedigera

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

Oberoende mängderRedigera

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:

  1.  
  2. Varje delmängd av en oberoende mängd är oberoende, det vill säga om   och   så är  
  3. Om   är två oberoende mängder och  , så finns   sådant att  


KretsarRedigera

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.  
  2. Om   och   så är  
  3. Om   och   och   innehåller   en krets till  

ExempelRedigera

Linjär AlgebraRedigera

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  

GrafteoriRedigera

 
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 matroiderRedigera

Isomorfa matroiderRedigera

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 matroiderRedigera

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

Ternära matroiderRedigera

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

Regelbundna matroidRedigera

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

ReferenserRedigera

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