Матро́ид, гиперграф специального вида. Матроид определяется заданием множества $V$ элементов и семейства $\mathscr{E}= \{E_1, E_2, \ldots\}$ подмножеств множества $V$, называемых независимыми множествами, для которых выполняются следующие аксиомы:

1) пустое множество независимо;

2) каждое подмножество независимого множества независимо;

3) для всякого подмножества $A\subseteq E$ все независимые множества матроида, содержащиеся в $A$ и являющиеся максимальными по включению относительно $A$, имеют одинаковое число элементов.

Примеры.

1) Множество $V$ строк произвольной прямоугольной матрицы и семейство $\mathscr E$ всех подмножеств множества $V$, составленных из линейно независимых строк, образуют матроид.

2) Пусть $\mathscr L = \{L_1, L_2,\ldots \}$ – множество всех остовных лесов (см. Дерево в математике) графа $G$, а $R(L_i)$ – множество рёбер леса $L_i, i=1, 2, \ldots\;$. Тогда множество рёбер $V$ графа $G$ и семейство $\mathscr E=\{R(L_i), i=1, 2, \ldots\}$ образуют матроид.

3) Пусть $G$ – двудольный граф с долями $W'$, $W''$. Подмножество $V\subseteq W'$ вершин, для которого существует паросочетание $P$ графа $G$ такое, что каждая вершина $V$ инцидентна некоторому ребру паросочетания $P$, называется трансверсалью. Множество $V$ и множество всех трансверсалей графа $G$ образуют т. н. трансверсальный матроид.

Матроид можно задать также множеством $V$ элементов и семейством $\mathscr C=\{C_1, С_2,\ldots\}$ непустых подмножеств $C_i\subseteq V$, называемых циклами и удовлетворяющих следующим аксиомам:

никакое собственное подмножество цикла не является циклом;

если $v\in C_i\cap C_j$, то $C_i\cup C_j\setminus\{v\}$ содержит цикл.

Независимыми множествами этого матроида являются подмножества $E\subseteq V$, не содержащие циклов.

Если $G$ – граф, то множество его рёбер и семейство простых циклов образуют т. н. циклический матроид. Если в качестве циклов матроида взять коциклы (разрезы, см. Связность графа) графа $G$, то полученный таким образом матроид называется коциклическим. Матроиды двух последних типов называются графическими. Понятие «матроид» используется в теории графов и комбинаторике при доказательстве некоторых утверждений о покрытиях и упаковках, паросочетаниях.