Определение матроида

Аксиоматическое определение

Матроид — пара [math](X,I)[/math], где [math]X[/math] — конечное множество, называемое носителем матроида, а [math]I[/math] — некоторое множество подмножеств [math]X[/math], называемое семейством независимых множеств , то есть [math]I \subset 2^X [/math]. При этом должны выполняться следующие условия:

1. [math]\varnothing \in I[/math]
2. Если [math]A \in I [/math] и [math] B \subset A[/math], то [math]B \in I[/math]
3. Если [math]A,B \in I[/math] и мощность A больше мощности B, то существует [math]x \in A \setminus B[/math] такой, что [math]B \cup \{x\} \in I[/math]

Базами матроида называются максимальные по включению независимые множества. Подмножества [math]X \notin I[/math] называются зависимыми множествами. Минимальные по включению зависимые множества называются циклами матроида, это понятие используется в альтернативном определении матроида.

Определение в терминах правильного замыкания

Матроид — пара [math](X, A\to H(A))[/math], где [math]X[/math] — конечное множество, называемое носителем матроида, а [math]A \to H(A)[/math] — правильное замыкание на [math](2^X,\le)[/math]