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

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

Определение:

Матроид — пара [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