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  M är ett par  ( E, \mathcal{I}) som består av en ändlig mängd  E och en mängd  I bestående av delmängder till  E som uppfyller följande krav:

  1.  \mathcal{I} \neq \empty
  2. Om  A \in \mathcal{I} och  A' \subset A \subset E är  A' \in \mathcal{I}
  3. Om  A, B \in \mathcal{I} samt att  \left\vert A \right\vert > \left\vert B \right\vert finns det   x \in (A \setminus B) så att  (B \cup x) \in \mathcal{I}

 E kallas grundmängd och element i  \mathcal{I} kallas oberoende mängder.

Kretsar[redigera | redigera wikitext]

En krets är en minimal beroende mängd till en matroid. Mängden  \mathcal{C} som består av samlingen kretsar till en matroid  M har följande egenskaper:

  1.  \mathcal{C} \neq \empty
  2. Om  C_1, C_2 \in \mathcal{C} och  C_1 \neq C_2 är  C_1 \not \subset C_2
  3. Om  C_1, C_2 \in \mathcal{C} och  C_1 \neq C_2 och  e \in C_1 \cap C_2 innehåller  ( C_1 \cup C_2) \setminus e en krets till  M

Exempel[redigera | redigera wikitext]

Linjär Algebra[redigera | redigera wikitext]

Låt matrisen


A =
\Bigl(
\overbrace {
\begin{matrix}
1  \\
0 
\end{matrix}}^{1}
\overbrace {
\begin{matrix}
0  \\
1 
\end{matrix}}^{2}
\overbrace {
\begin{matrix}
1  \\
1 
\end{matrix}}^{3}
\overbrace {
\begin{matrix}
0  \\
0 
\end{matrix}}^{4} \Bigr)

Låt sedan  E = \{ 1, 2, 3, 4 \} där 1, 2, 3, 4 syftar på kolonnerna till  A .
Bilda sedan  \mathcal{I} av alla delmängder till  E som inte är linjärt beroende.
Då fås att  \mathcal{I} = \{ \empty, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\} \}.
 (E, \mathcal{I}) är då en matroid som speciellt kallas för en vektormatroid till  A

Grafteori[redigera | redigera wikitext]

En sammanhängde graf  G med fyra noder, betecknade A, B, C och D, och sju noder, betecknade 1-7.

Bilda en mängd av samtliga bågar i  G

 E = \{1 ,2 ,3 ,4 ,5 ,6 ,7 \}

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

 \mathcal{C} = \{ \empty, \{7\},  \{1,2\}, \{4, 5, 6\}, \{2, 3 , 4\}, \{1, 3, 4\}, \{2, 3, 6, 5\}, \{1, 3, 6 ,5\} \}

Då kan  G beskrivas med en kretsmatroid  M som har grundmängd  E och där  \mathcal{C} innehåller samtliga kretsar till  M .

Typer av matroider[redigera | redigera wikitext]

Isomorfa matroider[redigera | redigera wikitext]

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

 E = \{ 1, 2\}

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

  \mathcal{I}_1 = \{\empty \}
 \mathcal{I}_2 = \{\empty, \{1\} \}
  \mathcal{I}_3 = \{\empty, \{2\} \}
 \mathcal{I}_4 = \{\empty, \{1\}, \{2\} \}
 \mathcal{I}_5 = \{\empty, \{1\}, \{2\}, \{1 , 2\} \}

Om man jämför  M_1  = (E, \mathcal{I}_2) och  M_2  = (E, \mathcal{I}_3) ser man att dessa matroider har samma struktur.  M_1 och  M_2 kallas isomorfa och skrivs  M_1 \cong M_2 .

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.