Матроид

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

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

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

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

Примеры.

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

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

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

Матроид можно задать также множеством ${\displaystyle V}$ элементов и семейством ${\displaystyle {\mathcal {C}}=\{C_{1},{\text{С}}_{2},\ldots \}}$ непустых подмножеств ${\displaystyle C_{i}\subseteq V}$, называемых циклами и удовлетворяющих следующим аксиомам:

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

если ${\displaystyle v\in C_{i}\cap C_{j}}$, то ${\displaystyle C_{i}\cup C_{j}\setminus \{v\}}$ содержит цикл.

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

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