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

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

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

Матроид (англ. matroid) — пара [math]\langle X,I \rangle[/math], где [math]X[/math] — конечное множество, называемое носителем матроида (англ. ground set), а [math]I[/math] — некоторое множество подмножеств [math]X[/math], называемое семейством независимых множеств (англ. independent sets), то есть [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] и [math]|A| \gt |B|[/math], то [math] \exists \, x \in A \setminus B : B \cup \{x\} \in I[/math]

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

База матроида (англ. basis) — максимальное по включению независимое множество .

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

Зависимое множество (англ. dependent set) — подмножество носителя матроида, не являющееся независимым.

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

Цикл матроида (англ. circuit) — минимальное по включению зависимое множество.

См. также

• Примеры матроидов
• Аксиоматизация матроида базами
• Аксиоматизация матроида циклами

Источники информации

• Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
• Wikipedia — Matroid
• Википедия — Матроид