Изменения

'''Матроид''' — (англ. ''matroid'') {{---}} пара <tex>(\langle X,I)\rangle</tex>, где <tex>X</tex> — {{---}} конечное множество, называемое '''носителемматроида''' (англ. ''ground'' ''set''), а <tex>I</tex> — {{---}} некоторое множество подмножеств <tex>X</tex>, называемоесемейством '''независимыхмножеств'' множеств ' (англ. ''independent'' ''sets''), то есть <tex>I \subset 2^X </tex>. При этом должнывыполняться следующие условия:

# Если если <tex>A \in I </tex> и <tex> B \subset A</tex>, то <tex>B \in I</tex># Если если <tex>A,B \in I</tex> и <tex>|A| > |B|</tex>, то <tex> \exists \, x \in A \setminus B</tex> такой, что <tex>\mid B \cup \{x\} \in I</tex>

'''База матроида''' (англ. ''base'') {{- --}} максимальное по включению независимое множество.

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

'''Цикл матроидаЗависимое множество''' (англ. ''dependent'' ''set'' ) {{- минимальное по включению зависимое множество--}} подмножество носителя матроида, не являющееся независимым.

'''Ранг Цикл матроида''' (англ. ''cicruit'') {{- мощность баз данного матроида--}} минимальное по включению зависимое множество.

'''Матроид''' - пара Матроиды <tex>(XM_1 = \langle X_1, C)I_1 \rangle</tex>, где и <tex>X</tex> - носитель матроидаM_2 = \langle X_2, <tex>CI_2 \rangle</tex> - семейство подмножеств <tex>X</tex>, называемое множеством называются '''изоморфными'''(англ. 'циклов матроида'isomorphic matroids''), для которых выполняются условия:#если существует биекция (взаммно-однозначное отображение) <tex>\varnothing varphi\notin Ccolon \ X_1 \rightarrow X_2</tex>#Если <tex>C_1, C_2 \in Cсохраняющая независимость, то есть множество </tex> и <tex>C_1 A \subset C_2I_1</tex>, то является независимым в матроиде <tex>C_1 = C_2M_1</tex>#Если тогда и только тогда, когда образ этого множества при заданном отображении <tex>C_1, C_2 \in C, \, C_1 \ne C_2, \, x \in C_1 \cap C_2varphi(A)</tex>, то есть независимое множество в матроиде <tex>\exists \, C_3 \in C : C_3 \subset (C_1 \cup C_3 \setminus x)M_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 />*[[wikipedia:Matroid | Wikipedia {{---}} Matroid]]*[[wikipedia:ru:Матроид | Википедия {{---}} Матроид]] [[Категория:Алгоритмы и структуры данных]][[Категория:Матроиды]][[Категория:Основные факты теории матроидов]]