En matroid är inom kombinatoriken en struktur som abstraherar grunddragen hos begreppet linjärt oberoende .
Det finns flera ekvivalenta sätt att definiera en matroid.
En matroid
M
{\displaystyle M}
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
E
{\displaystyle E}
ändlig mängd (kallad grundmängden) och
I
{\displaystyle {\mathcal {I}}}
E
{\displaystyle E}
I
≠
∅
{\displaystyle {\mathcal {I}}\neq \emptyset }
Varje delmängd av en oberoende mängd är oberoende, det vill säga om
A
∈
I
{\displaystyle A\in {\mathcal {I}}}
A
′
⊂
A
⊂
E
{\displaystyle A'\subset A\subset E}
A
′
∈
I
{\displaystyle A'\in {\mathcal {I}}}
Om
A
,
B
∈
I
{\displaystyle A,B\in {\mathcal {I}}}
|
A
|
>
|
B
|
{\displaystyle \left\vert A\right\vert >\left\vert B\right\vert }
x
∈
A
∖
B
{\displaystyle x\in A\setminus B}
B
∪
{
x
}
∈
I
{\displaystyle B\cup \left\{x\right\}\in {\mathcal {I}}}
En krets är en minimal beroende mängd till en matroid.
Mängden
C
{\displaystyle {\mathcal {C}}}
M
{\displaystyle M}
C
≠
∅
{\displaystyle {\mathcal {C}}\neq \emptyset }
Om
C
1
,
C
2
∈
C
{\displaystyle C_{1},C_{2}\in {\mathcal {C}}}
C
1
≠
C
2
{\displaystyle C_{1}\neq C_{2}}
C
1
⊄
C
2
{\displaystyle C_{1}\not \subset C_{2}}
Om
C
1
,
C
2
∈
C
{\displaystyle C_{1},C_{2}\in {\mathcal {C}}}
C
1
≠
C
2
{\displaystyle C_{1}\neq C_{2}}
e
∈
C
1
∩
C
2
{\displaystyle e\in C_{1}\cap C_{2}}
(
C
1
∪
C
2
)
∖
e
{\displaystyle (C_{1}\cup C_{2})\setminus e}
M
{\displaystyle M}
Låt matrisen
A
=
(
1
0
⏞
1
0
1
⏞
2
1
1
⏞
3
0
0
⏞
4
)
{\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
E
=
{
1
,
2
,
3
,
4
}
{\displaystyle E=\{1,2,3,4\}}
A
{\displaystyle A}
I
{\displaystyle {\mathcal {I}}}
E
{\displaystyle E}
I
=
{
∅
,
{
1
}
,
{
2
}
,
{
3
}
,
{
1
,
2
}
,
{
1
,
3
}
,
{
2
,
3
}
}
.
{\displaystyle {\mathcal {I}}=\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}\}.}
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
A
{\displaystyle A}
En sammanhängde graf
G
{\displaystyle G}
A , B , C och D , och sju noder, betecknade 1-7 . Bilda en mängd av samtliga bågar i
G
{\displaystyle G}
E
=
{
1
,
2
,
3
,
4
,
5
,
6
,
7
}
{\displaystyle E=\{1,2,3,4,5,6,7\}}
Bilda sedan en mängd av alla cykler i
G
{\displaystyle G}
C
=
{
∅
,
{
7
}
,
{
1
,
2
}
,
{
4
,
5
,
6
}
,
{
2
,
3
,
4
}
,
{
1
,
3
,
4
}
,
{
2
,
3
,
6
,
5
}
,
{
1
,
3
,
6
,
5
}
}
{\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
G
{\displaystyle G}
M
{\displaystyle M}
E
{\displaystyle E}
C
{\displaystyle {\mathcal {C}}}
M
{\displaystyle M}
En matroid
M
{\displaystyle M}
E
=
{
1
,
2
}
{\displaystyle E=\{1,2\}}
kan ha följande samlingar av oberoende mängder:
I
1
=
{
∅
}
{\displaystyle {\mathcal {I}}_{1}=\{\emptyset \}}
I
2
=
{
∅
,
{
1
}
}
{\displaystyle {\mathcal {I}}_{2}=\{\emptyset ,\{1\}\}}
I
3
=
{
∅
,
{
2
}
}
{\displaystyle {\mathcal {I}}_{3}=\{\emptyset ,\{2\}\}}
I
4
=
{
∅
,
{
1
}
,
{
2
}
}
{\displaystyle {\mathcal {I}}_{4}=\{\emptyset ,\{1\},\{2\}\}}
I
5
=
{
∅
,
{
1
}
,
{
2
}
,
{
1
,
2
}
}
{\displaystyle {\mathcal {I}}_{5}=\{\emptyset ,\{1\},\{2\},\{1,2\}\}}
Om man jämför
M
1
=
(
E
,
I
2
)
{\displaystyle M_{1}=(E,{\mathcal {I}}_{2})}
M
2
=
(
E
,
I
3
)
{\displaystyle M_{2}=(E,{\mathcal {I}}_{3})}
M
1
{\displaystyle M_{1}}
M
2
{\displaystyle M_{2}}
isomorfa och skrivs
M
1
≅
M
2
{\displaystyle M_{1}\cong M_{2}}
En matroid som kan representeras över en ändlig kropp med två element kallas för en binär matroid .
En matroid som kan representeras över en ändlig kropp med tre element kallas för en ternär matroid .
En matroid som kan representeras över alla kroppar kallas för en regelbunden matroid .
Oxley, James, What is a matroid? , 2007, Department of Mathematics, Louisiana State University. 
