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 $M$ är ett par $(E,ℐ)$ där $E$ är en ändlig mängd (kallad grundmängden) och $ℐ$ är en familj av delmängder (kallade de oberoende mängderna) till $E$ som uppfyller följande krav:

1. $ℐ\ne \mathrm{\varnothing }$
2. Varje delmängd av en oberoende mängd är oberoende, det vill säga om $A\in ℐ$ och $A^{\prime }\subset A\subset E$ så är $A^{\prime }\in ℐ$
3. Om $A,B\in ℐ$ är två oberoende mängder och $\left|A\right|>\left|B\right|$, så finns $x\in A\setminus B$ sådant att $B\cup \left\{x\right\}\in ℐ$

Kretsar

En krets är en minimal beroende mängd till en matroid. Mängden $𝒞$ som består av samlingen kretsar till en matroid $M$ har följande egenskaper:

1. $𝒞\ne \mathrm{\varnothing }$
2. Om $C_1,C_2\in 𝒞$ och $C_1\ne C_2$ så är $C_1\subset ̸C_2$
3. Om $C_1,C_2\in 𝒞$ och $C_1\ne C_2$ och $e\in C_1\cap C_2$ innehåller $(C_1\cup C_2)\setminus e$ en krets till $M$

Exempel

Linjär Algebra

Låt matrisen

$A=\left(\stackrel{1}{\overbrace{\begin{array}{c}1\\ 0\end{array}}}\stackrel{2}{\overbrace{\begin{array}{c}0\\ 1\end{array}}}\stackrel{3}{\overbrace{\begin{array}{c}1\\ 1\end{array}}}\stackrel{4}{\overbrace{\begin{array}{c}0\\ 0\end{array}}}\right)$

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

Grafteori

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.

$𝒞=\{\mathrm{\varnothing },\{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 $𝒞$ innehåller samtliga kretsar till $M$.

Typer av matroider

Isomorfa matroider

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

$E=\{1,2\}$

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

${ℐ}_1=\{\mathrm{\varnothing }\}$

${ℐ}_2=\{\mathrm{\varnothing },\{1\}\}$

${ℐ}_3=\{\mathrm{\varnothing },\{2\}\}$

${ℐ}_4=\{\mathrm{\varnothing },\{1\},\{2\}\}$

${ℐ}_5=\{\mathrm{\varnothing },\{1\},\{2\},\{1,2\}\}$

Om man jämför $M_1=(E,{ℐ}_2)$ och $M_2=(E,{ℐ}_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

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.