Matroid

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

Ordbok

Definition

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

Oberoende mängder

En matroid ${\displaystyle M}$ är ett par ${\displaystyle (E,{\mathcal {I}})}$ där ${\displaystyle E}$ är en ändlig mängd (kallad grundmängden) och ${\displaystyle {\mathcal {I}}}$ är en familj av delmängder (kallade de oberoende mängderna) till ${\displaystyle E}$ som uppfyller följande krav:

1. ${\displaystyle {\mathcal {I}}\neq \emptyset }$
2. Varje delmängd av en oberoende mängd är oberoende, det vill säga om ${\displaystyle A\in {\mathcal {I}}}$ och ${\displaystyle A'\subset A\subset E}$ så är ${\displaystyle A'\in {\mathcal {I}}}$
3. Om ${\displaystyle A,B\in {\mathcal {I}}}$ är två oberoende mängder och ${\displaystyle \left\vert A\right\vert >\left\vert B\right\vert }$, så finns ${\displaystyle x\in A\setminus B}$ sådant att ${\displaystyle B\cup \left\{x\right\}\in {\mathcal {I}}}$

Kretsar

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

1. ${\displaystyle {\mathcal {C}}\neq \emptyset }$
2. Om ${\displaystyle C_{1},C_{2}\in {\mathcal {C}}}$ och ${\displaystyle C_{1}\neq C_{2}}$ så är ${\displaystyle C_{1}\not \subset C_{2}}$
3. Om ${\displaystyle C_{1},C_{2}\in {\mathcal {C}}}$ och ${\displaystyle C_{1}\neq C_{2}}$ och ${\displaystyle e\in C_{1}\cap C_{2}}$ innehåller ${\displaystyle (C_{1}\cup C_{2})\setminus e}$ en krets till ${\displaystyle M}$

Exempel

Linjär Algebra

Låt matrisen

${\displaystyle 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 ${\displaystyle E=\{1,2,3,4\}}$ där 1, 2, 3, 4 syftar på kolonnerna till ${\displaystyle A}$.
Bilda sedan ${\displaystyle {\mathcal {I}}}$ av alla delmängder till ${\displaystyle E}$ som inte är linjärt beroende.
Då fås att ${\displaystyle {\mathcal {I}}=\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}\}.}$
${\displaystyle (E,{\mathcal {I}})}$ är då en matroid som speciellt kallas för en vektormatroid till ${\displaystyle A}$

Grafteori

En sammanhängde graf ${\displaystyle 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 ${\displaystyle G}$

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

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

${\displaystyle {\mathcal {C}}=\{\emptyset ,\{7\},\{1,2\},\{4,5,6\},\{2,3,4\},\{1,3,4\},\{2,3,6,5\},\{1,3,6,5\}\}}$

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

Typer av matroider

Isomorfa matroider

En matroid ${\displaystyle M}$ med en grundmängd innehållande två distinkta element

${\displaystyle E=\{1,2\}}$

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

${\displaystyle {\mathcal {I}}_{1}=\{\emptyset \}}$

${\displaystyle {\mathcal {I}}_{2}=\{\emptyset ,\{1\}\}}$

${\displaystyle {\mathcal {I}}_{3}=\{\emptyset ,\{2\}\}}$

${\displaystyle {\mathcal {I}}_{4}=\{\emptyset ,\{1\},\{2\}\}}$

${\displaystyle {\mathcal {I}}_{5}=\{\emptyset ,\{1\},\{2\},\{1,2\}\}}$

Om man jämför ${\displaystyle M_{1}=(E,{\mathcal {I}}_{2})}$ och ${\displaystyle M_{2}=(E,{\mathcal {I}}_{3})}$ ser man att dessa matroider har samma struktur. ${\displaystyle M_{1}}$ och ${\displaystyle M_{2}}$ kallas isomorfa och skrivs ${\displaystyle 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.