Изменения

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

'''Матроид''' — пара <math>(X,I)</math>, где <math>X</math> — конечное множество, называемое носителем

матроида, а <math>I</math> — некоторое множество подмножеств <math>X</math>, называемое

семейством ''независимых'' множеств , то есть <math>I \subset 2^X </math>. При этом должны

выполняться следующие условия:

# <math>\varnothing \in I</math>

# Если <math>A \in I </math> и <math> B \subset A</math>, то <math>B \in I</math>

# Если <math>A,B \in I</math> и мощность A больше мощности B, то существует <math>x \in A \setminus B</math> такой, что <math>B \cup \{x\} \in I</math>

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

'''Матроидом''' называется непустое множество <math>E</math> вместе с [[Оператор_замыкания_для_матроидов | оператором замыкания]]<math>A \to \langle A \rangle</math> такое, что

#<math>\forall p,q \in E</math> и <math>A \subset E</math> из <math>q \notin \langle A \rangle</math> и <math> q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</math>

#<math>\forall A \subset E</math> существует такое множество <math>B \subset A</math>, что <math>\langle A \rangle = \langle B \rangle </math>

== Дополнительные понятия ==

*'''Базами''' матроида называются максимальные по включению независимые множества.

*'''Рангом''' матроида называется мощность его баз. Ранг тривиального матроида равен нулю.

== Литература ==

''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />