Изменения
Нет описания правки
{{Определение
|definition=
'''Матроид''' — пара <tex>(X,I)</tex>, где <tex>X</tex> — конечное множество, называемое '''носителемматроида''', а <tex>I</tex> — некоторое множество подмножеств <tex>X</tex>, называемоесемейством '''независимыхмножеств''' множеств , то есть <tex>I \subset 2^X </tex>. При этом должнывыполняться следующие условия:
# <tex>\varnothing \in I</tex>
# Если <tex>A \in I </tex> и <tex> B \subset A</tex>, то <tex>B \in I</tex>
{{Определение
|definition=
'''База матроида''' - — максимальное по включению независимое множество.
}}
{{Определение
|definition=
'''Зависимое множество''' - — подмножество носителя матроида, не являющееся независимым.
}}
{{Определение
|definition=
'''Цикл матроида''' - — минимальное по включению зависимое множество.
}}
==Определение в терминах баз==
{{Определение
|definition=
'''Ранг Матроид''' — пара <tex>(X, B)</tex>, где <tex>X</tex> — конечное множество, называемое '''носителем матроида''' - мощность , <tex>B</tex> — семейство подмножеств <tex>X</tex>, называемое множеством '''баз данного матроида.''', для которых выполняются условия:#<tex>B \ne \varnothing</tex>#Если <tex>B_1, B_2 \in B</tex> и <tex>B_1 \ne B_2</tex>, то <tex>B_1 \not\subset B_2</tex> и <tex>B_2 \not\subset B_1</tex>#Если <tex>B_1, B_2 \in B</tex>, то <tex>\forall \, b_1 \in B_1 \: \exists \, b_2 \in B_2 : (B_1 \setminus b_1) \cup b_2 \in B</tex>
}}
{{Определение
|definition=
'''Матроид''' - — пара <tex>(X, C)</tex>, где <tex>X</tex> - носитель — конечное множество, называемое '''носителем матроида''', <tex>C</tex> - — семейство подмножеств <tex>X</tex>, называемое множеством '''циклов матроида''', для которых выполняются условия:
#<tex>\varnothing \notin C</tex>
#Если <tex>C_1, C_2 \in C</tex> и <tex>C_1 \subset C_2</tex>, то <tex>C_1 = C_2</tex>
}}
==Определение в терминах базСм. также=={{Определение* [[Примеры матроидов|Примеры матроидов]]* [[Аксиоматизация матроида базами|definition=Аксиоматизация матроида базами]]'''Матроид''' - пара <tex>(X, B)</tex>, где <tex>X</tex> - носитель * [[Аксиоматизация матроида, <tex>B</tex> - семейство подмножеств <tex>X</tex>, называемое множеством '''баз циклами|Аксиоматизация матроида''', для которых выполняются условия:#<tex>B \ne \varnothing</tex>#Если <tex>B_1, B_2 \in B</tex> и <tex>B_1 \ne B_2</tex>, то <tex>B_1 \not\subset B_2</tex> и <tex>B_2 \not\subset B_1</tex>#Если <tex>B_1, B_2 \in B</tex>, то <tex>\forall \, b_1 \in B_1 \: \exists \, b_2 \in B_2 : (B_1 \setminus b_1) \cup b_2 \in B</tex>}}циклами]]
== Литература ==
''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
