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

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

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

Матроид — пара [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] и [math]|A| \gt |B|[/math], то [math] \exists \, x \in A \setminus B[/math] такой, что [math]B \cup \{x\} \in I[/math]

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

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

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

Зависимое множество - подмножество носителя матроида, не являющееся независимым.

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

Цикл матроида - минимальное по включению зависимое множество.

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

Ранг матроида - мощность баз данного матроида.

Определение в терминах циклов

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

Матроид - пара [math](X, C)[/math], где [math]X[/math] - носитель матроида, [math]C[/math] - семейство подмножеств [math]X[/math], называемое множеством циклов матроида, для которых выполняются условия: [math]\varnothing \notin C[/math] Если [math]C_1, C_2 \in C[/math] и [math]C_1 \subset C_2[/math], то [math]C_1 = C_2[/math] Если [math]C_1, C_2 \in C, \, C_1 \ne C_2, \, x \in C_1 \cap C_2[/math], то [math]\exists \, C_3 \in C : C_3 \subset (C_1 \cup C_3 \setminus x)[/math]

Определение в терминах баз

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

Матроид - пара [math](X, B)[/math], где [math]X[/math] - носитель матроида, [math]B[/math] - семейство подмножеств [math]X[/math], называемое множеством баз матроида, для которых выполняются условия: [math]B \ne \varnothing[/math] Если [math]B_1, B_2 \in B[/math] и [math]B_1 \ne B_2[/math], то [math]B_1 \not\subset B_2[/math] и [math]B_2 \not\subset B_1[/math] Если [math]B_1, B_2 \in B[/math], то [math]\forall \, b_1 \in B_1 \: \exists \, b_2 \in B_2 : (B_1 \setminus b_1) \cup b_2 \in B[/math]

Литература

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